contributed by < bonianlee
>
不要打錯自己的 GitHub 帳號
不用抄題目,show me the code!
根據〈費氏數列分析〉,費氏數列 (Fibonacci sequence) 若以 64 位元來表示的話,正確的數值最高只能夠顯示到第 92 項 ,因為當 時,會因為數值超過 64 位元所能表示的最大值,而造成溢位 (overflow) 的發生
在原始程式碼 fibdrv 中,費氏數列是以 64 位元的資料型態 long long
來表示,實際運行的結果顯示為
與預期的結果相同,當數列計算到 時,會因為溢位而導致系統報錯,且顯示的輸出結果也與預期的不同,為了要解決這種狀況,我參考〈Small/Short String Optimization 的實作〉以及 qwe661234 的實作
解決方式是將數字改以字串 (string) 的形式進行運算並且表示結果的值,首先定義結構體
接著計算費氏數列的部份,因為只會用到加法,故實作字串的加法,以下為部份程式碼
前述的程式碼在做兩個數字字串的相加,其作法是十進位制每一個位數個別做相加,將進位存在 carry
當中,而 out
則用來儲存 a
與 b
相加的數字字串結果
而因為 out
是從低位數排列到高位數的字串,故在輸出結果時會將 out
做反轉,使最終結果方便閱讀,以下結果是計算到 的結果