作者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/cn.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