作者mpyh12345 (嘉义金城武)
看板C_and_CPP
标题[问题] 大一程式设计作业请教
时间Thu Nov 22 01:29:04 2018
不好意思，作业应该要自己做的，
但是有笔测资输出了我怎麽想都想不出来的结果。
https://i.imgur.com/vYuDM5e.png
怕格式乱掉 贴截图。
题目是要算组合 C n取k。
我一开始是先把分子跟分母分别算出来之後在相除，但这题有限制不能overflow。
於是图片上的做法我的想法就是假设C5取2，就是1*(5/2*4/1)，但是因为只能够改函式部分
，cin的n,k,m一开始就是int，所以我在函式计算里面强制把n以及k转换成double。
问题来了，输入了一堆测资大部分都正确，结果C 8取3出错，正确应该是56，但是输出结果
跑出了55这样的奇妙结果，百思不得其解这个数字到底怎麽跑出来的，所以想请各位帮我看
哪里出了问题。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.143.164.143
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1542821346.A.FFC.html
1F：推 alan23273850: 真神奇，我自己试出来也是 55，很肯定是从 double 11/22 01:40
2F：→ alan23273850: 转成 long long 的问题，但是解释不出理由 11/22 01:40
3F：→ alan23273850: 用 float 的话就没错11/22 01:43
4F：推 TMDTMD2487: 浮点数的运算都是有误差的，不然你把每一轮的c用doubl11/22 01:45
5F：→ TMDTMD2487: e型态印出来看11/22 01:45
7F：推 oToToT: return c+0.5应该就好了11/22 01:47
8F：→ alan23273850: 建议问问题前先喂狗 不过新手可能也不知道怎喂就是11/22 01:47
9F：→ alan23273850: 给的小知识，新手都以为 double 的范围很大，所以只11/22 01:48
10F：→ alan23273850: 要不 overflow 就很安全，事实上不然，因为根据IEEE11/22 01:48
了解你的意思，所以是浮点数的误差无关overflow对吧，就我这题来看，误差累积到一定程
度就会少进位对吧？
11F：→ alan23273850: 754 标准，浮点数是采用科学记号表示法，既然是科学 11/22 01:48
12F：→ alan23273850: 记号，在 a*10^e 的 a 那边位数一旦不够就会产生11/22 01:49
13F：推 ckc1ark: c会是55.9999999999999928945711/22 01:49
14F：→ alan23273850: rounding error，所以有没有误差跟数字大小未必有关 11/22 01:49
15F：→ alan23273850: 那 rounding error 会愈运算差愈多，所谓的误差传递11/22 01:50
16F：→ ckc1ark: 建议用8/1*7/2*6/3 这样整数除法不会出问题 只怕太大而已11/22 01:50
好的 我明天试看看
17F：→ alan23273850: 这也就是为什麽你直接把 56.0 转过去会对，但用运算11/22 01:50
18F：→ alan23273850: 的方式会错就是。11/22 01:50
19F：→ alan23273850: clark大指的是 8*7*6/1/2/3 吧11/22 01:52
我一开始就是用这个方法，只是我猜教学平台用的测资很大会overflow，所以这方法过不了
。
20F：推 TMDTMD2487: 请问一下为什麽不用递回做top down, 怕太慢就从下buil11/22 01:53
当下感觉离答案很接近就被这个方法绑住了。
21F：→ TMDTMD2487: d up起来就好了11/22 01:53
22F：→ TMDTMD2487: C(n, m) = C(n – 1, m – 1) + C(n – 1, m)11/22 01:53
23F：→ alan23273850: 他马的大大说的就是 dynamic programming 解11/22 01:55
24F：→ TMDTMD2487: 这公式高中就交过了吧 这样不会超过ㄅ 11/22 01:56
25F：→ TMDTMD2487: DP难的地方是从问题找递回11/22 01:57
26F：推 ckc1ark: 8/1*7/2*6/3没错 过程中都会是整数11/22 01:57
27F：→ TMDTMD2487: n*m的阵列从0,0开始算到n,m 作业试试这样写 不行的话11/22 01:59
28F：→ TMDTMD2487: 递回慢慢做也行11/22 01:59
※ 编辑: mpyh12345 (220.143.164.143), 11/22/2018 02:00:04
※ 编辑: mpyh12345 (220.143.164.143), 11/22/2018 02:02:57
29F：→ alan23273850: 喔喔 是我误会clark大的意思ㄌ 11/22 02:54
30F：→ alan23273850: 顺便提醒一下这种题目测资范围会影响解法的一定要 11/22 02:55
31F：→ alan23273850: 给，不然就不是好题目 11/22 02:55
32F：→ IcecreamHsu: for i=1; i<=n; p *= (m-i+1)/i; Cm取n的话这样就好 11/23 02:08
33F：→ IcecreamHsu: 噢抱歉推文有写了 请忽略 11/23 02:09
34F：推 bigpigbigpig: 可以考虑用质因数分解法，应该就不会 overflow 了。 06/24 22:39