作者ddchris (克里斯)
看板C_and_CPP
標題[問題] 大數問題(費氏數列計算) 利用陣列
時間Tue Jul 18 17:49:33 2017
開發平台(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://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1500371377.A.283.html
1F：推 Zero0910: stack空間不夠你放這麼大的陣列啦 請用new/delete去配置 07/18 17:57
2F：→ Zero0910: 記憶體空間 07/18 17:57
3F：推 Zero0910: 置底十三誡第10點 07/18 18:00
感謝! 雖然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
4F：推 Yshuan: 你只需要N-2跟N-1去算第N項 從0到N-3的空間根本不用 07/18 19:37
5F：推 remizu: bad_alloc exception是new失敗所產生的 通常是要太多 07/18 19:41
6F：→ remizu: 記憶體 改用Y大的方法就可以解決 07/18 19:42
7F：推 moebear: 我建議做二維動態陣列new一次 然後把它截成二維的樣子 07/18 19:43
感謝幾位熱心的回復! 但小弟資質駑鈍一時還無法了解 Orz
像Y大說 只利用 N-2跟N-1項去算第N項? 但不是還得先算出 N-1跟 N-2項?
然要算 N-1項又要先算 N-2 N-3,不是等於全部都要算一次嗎XD
看來我需要冷靜一下 先吃個飯 晚點繼續研究~
9F：→ moebear: 前面的丟掉會算太久吧 07/18 20:25
10F：→ Littlechozy: F20000不超過6000位，如果用1個int表示10000，一個數 07/18 21:09
11F：→ Littlechozy: 要1200個int，以記憶體有500MB來看，可以算看看 07/18 21:11
最後試了以下幾點修正:
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