作者joshua049 (qwertyuiop)
看板C_and_CPP
標題[問題] 關於overflow
時間Wed Oct 12 22:57:41 2016
小弟我今天碰到一個題目
假如輸入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://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1476284266.A.7CE.html
1F：→ pttworld: * 10/12 23:22
2F：推 steve1012: 乘法長很快 10/12 23:57
什麼意思??
※ 編輯: joshua049 (140.114.221.131), 10/13/2016 00:02:21
※ 編輯: joshua049 (140.114.221.131), 10/13/2016 00:03:28
3F：推 Raymond0710: 13! 算算看是多少 int 界線又是多少 10/13 00:12
摁摁 那為甚麼用遞迴的方式就不會爆呢
※ 編輯: joshua049 (140.114.221.131), 10/13/2016 00:17:52
4F：→ pttworld: + 10/13 00:29
5F：推 a27417332: 推同學，看題目就在猜ip是不是114 XD 10/13 00:56
6F：推 LPH66: 主要其實不是乘跟加, 而是組合數做法的中間結果 10/13 01:35
7F：→ LPH66: 會先變大再變小, 變大的過程中間就有可能溢位 10/13 01:35
8F：→ Chikei: 因為遞迴不用很大的數字除很大的數字，一路小數字加上去 10/13 01:36
9F：→ LPH66: 只是乘法的這個過程加速很快而已 10/13 01:36
10F：→ LPH66: 事實上組合數做法也是有不溢位的算法的 10/13 01:36
11F：→ LPH66: 只是相對的就複雜很多 10/13 01:36
12F：→ LPH66: 遞迴的做法只有加沒有減, 所以如果溢位就是結果真的太大 10/13 01:37
歐歐我想通了 感謝各位!!!!
13F：→ Schottky: 認親 XD 10/13 02:10
14F：推 Sylveon: 114來競程玩R,有Cn取m的強化版 10/13 04:54
我開學去聽過了，聽到崩潰XDDDD
15F：→ pttworld: 實際是結果不破，怎麼加都可以。乘配合除縮小則爆。 10/13 08:44
16F：→ pttworld: 硬要寫乘，可以是迴圈內每乘一個數字就判斷是否可除。 10/13 08:47
※ 編輯: joshua049 (140.114.221.131), 10/13/2016 09:32:48