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