[問題] 大數問題(費氏數列計算) 利用陣列

[ddchris (克里斯)]

開發平台(Platform): (Ex: Win10, Linux, ...) 
Win10

編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)
Visual studio 2017

問題(Question)：
當測試值小時執行都蠻正常
但是當 N>650(第650項) 或 W>450(陣列數字位數)時會出現執行錯誤訊息(不知為何?)

錯誤結果(Wrong Output)：
發生未處理的例外狀況: 0xC00000FD: Stack overflow (參數: 0x00000000,
0x01202000)。

程式碼(Code)：(請善用置底文網頁, 記得排版) 
http://ideone.com/KqN9Qq

補充說明(Supplement)：

想法是利用二維矩陣紀錄每一個費氏數列的值(由左而右)

最後答案再由右而左反著印出來

自學C++的程式超新手
還請各位大神鞭小力一點... 感謝!!


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.166.238.99
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1500371377.A.283.html
推 Zero0910: stack空間不夠你放這麼大的陣列啦 請用new/delete去配置
→ Zero0910: 記憶體空間
推 Zero0910: 置底十三誡第10點
感謝! 雖然stack空間這詞對我很陌生,等會試試看利用動態陣列!
改正過後變成這樣 http://ideone.com/SFFUMe
編譯器可以過了~
但是ZeroJudge 還是過不了!! 是因為測資的記憶體限制嗎? 這又能如何克服?

錯誤訊息為:
系統呼叫了 abort 函式！
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
Aborted (core dumped)


補上題目:
https://zerojudge.tw/ShowProblem?problemid=d283
推 Yshuan: 你只需要N-2跟N-1去算第N項 從0到N-3的空間根本不用
推 remizu: bad_alloc exception是new失敗所產生的 通常是要太多
→ remizu: 記憶體 改用Y大的方法就可以解決
推 moebear: 我建議做二維動態陣列new一次 然後把它截成二維的樣子
→ moebear: https://goo.gl/WSbTH2 像是這個(三)
感謝幾位熱心的回復! 但小弟資質駑鈍一時還無法了解 Orz
像Y大說  只利用 N-2跟N-1項去算第N項? 但不是還得先算出 N-1跟 N-2項?
         然要算 N-1項又要先算 N-2 N-3,不是等於全部都要算一次嗎XD
看來我需要冷靜一下  先吃個飯  晚點繼續研究~
→ moebear: 前面的丟掉會算太久吧
→ Littlechozy: F20000不超過6000位，如果用1個int表示10000，一個數
→ Littlechozy: 要1200個int，以記憶體有500MB來看，可以算看看
最後試了以下幾點修正:

1.修改了陣列類型為long long (用10^18進位讓陣列能儲存更多位數減少宣告位數W?)
2.進位部分補上之前漏掉的等號(行31)
3.Output部分第二項開始加上數字前必須補'0'(行50)
題目:
https://zerojudge.tw/ShowProblem?problemid=d283
歷經千辛萬苦最終版本  http://ideone.com/qHosrs 終於通過測試!
這題讓我學到了不少觀念  謝謝各位指導~ 也歡迎提供更有效的做法 <(__)>
※ 編輯: ddchris (60.245.65.179), 07/19/2017 11:18:13