[問題] 關於overflow

看板C_and_CPP作者 (qwertyuiop)時間7年前 (2016/10/12 22:57), 7年前編輯推噓5(5推 0噓 11→)
留言16則, 8人參與, 最新討論串2/2 (看更多)
小弟我今天碰到一個題目 假如輸入n 要輸出(X+1)的n次方展開後的係數 例如： 3→1 3 3 1 4→1 4 6 4 1 那我看到這個題目的第一個反應就是Cn取k的公式 所以就是利用階乘的方式 寫出第一支程式碼 http://i.imgur.com/r5Z0AOR.jpg
前面幾筆測資都是正確的 但是到後面數字越來越大 就會出現overflow的情況(大概在13附近) 後來我改用Cn取k=C(n-1)取(k-1)+C(n-1)取k這個遞迴式 另外寫了一個函式 讓整個精簡一點 http://i.imgur.com/3Q56AGR.jpg
後來所有的測資就都通過了(1~30) 想請問像這種情況 明明數字大小都一樣 為甚麼第一種寫法會overflow呢？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.221.131 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1476284266.A.7CE.html
→
10/12 23:22, , 1F
*
10/12 23:22, 1F
推
10/12 23:57, , 2F
乘法長很快
10/12 23:57, 2F
什麼意思?? ※ 編輯: joshua049 (140.114.221.131), 10/13/2016 00:02:21 ※ 編輯: joshua049 (140.114.221.131), 10/13/2016 00:03:28
推
10/13 00:12, , 3F
13! 算算看是多少 int 界線又是多少
10/13 00:12, 3F
摁摁 那為甚麼用遞迴的方式就不會爆呢 ※ 編輯: joshua049 (140.114.221.131), 10/13/2016 00:17:52
→
10/13 00:29, , 4F
+
10/13 00:29, 4F
推
10/13 00:56, , 5F
推同學，看題目就在猜ip是不是114 XD
10/13 00:56, 5F
推
10/13 01:35, , 6F
主要其實不是乘跟加, 而是組合數做法的中間結果
10/13 01:35, 6F
→
10/13 01:35, , 7F
會先變大再變小, 變大的過程中間就有可能溢位
10/13 01:35, 7F
→
10/13 01:36, , 8F
因為遞迴不用很大的數字除很大的數字，一路小數字加上去
10/13 01:36, 8F
→
10/13 01:36, , 9F
只是乘法的這個過程加速很快而已
10/13 01:36, 9F
→
10/13 01:36, , 10F
事實上組合數做法也是有不溢位的算法的
10/13 01:36, 10F
→
10/13 01:36, , 11F
只是相對的就複雜很多
10/13 01:36, 11F
→
10/13 01:37, , 12F
遞迴的做法只有加沒有減, 所以如果溢位就是結果真的太大
10/13 01:37, 12F
歐歐我想通了 感謝各位!!!!
→
10/13 02:10, , 13F
認親 XD
10/13 02:10, 13F
推
10/13 04:54, , 14F
114來競程玩R,有Cn取m的強化版
10/13 04:54, 14F
我開學去聽過了，聽到崩潰XDDDD
→
10/13 08:44, , 15F
實際是結果不破，怎麼加都可以。乘配合除縮小則爆。
10/13 08:44, 15F
→
10/13 08:47, , 16F
硬要寫乘，可以是迴圈內每乘一個數字就判斷是否可除。
10/13 08:47, 16F
※ 編輯: joshua049 (140.114.221.131), 10/13/2016 09:32:48
‣ 更多 joshua049 的文章
文章代碼(AID): #1N_azgVE (C_and_CPP)
‣ 更多 joshua049 的文章
文章代碼(AID): #1N_azgVE (C_and_CPP)