[問題] 大一程式設計作業請教

[mpyh12345 (嘉義金城武)]

不好意思，作業應該要自己做的，
但是有筆測資輸出了我怎麼想都想不出來的結果。

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://www.ptt.cc/bbs/C_and_CPP/M.1542821346.A.FFC.html
推 alan23273850: 真神奇，我自己試出來也是 55，很肯定是從 double
→ alan23273850: 轉成 long long 的問題，但是解釋不出理由
→ alan23273850: 用 float 的話就沒錯
推 TMDTMD2487: 浮點數的運算都是有誤差的，不然你把每一輪的c用doubl
→ TMDTMD2487: e型態印出來看
→ alan23273850: https://goo.gl/5vCq8X 這邊有人有嘗試過
推 oToToT: return c+0.5應該就好了
→ alan23273850: 建議問問題前先餵狗 不過新手可能也不知道怎餵就是
→ alan23273850: 給的小知識，新手都以為 double 的範圍很大，所以只
→ alan23273850: 要不 overflow 就很安全，事實上不然，因為根據IEEE
瞭解你的意思，所以是浮點數的誤差無關overflow對吧，就我這題來看，誤差累積到一定程
度就會少進位對吧？
→ alan23273850: 754 標準，浮點數是採用科學記號表示法，既然是科學
→ alan23273850: 記號，在 a*10^e 的 a 那邊位數一旦不夠就會產生
推 ckc1ark: c會是55.99999999999999289457
→ alan23273850: rounding error，所以有沒有誤差跟數字大小未必有關
→ alan23273850: 那 rounding error 會愈運算差愈多，所謂的誤差傳遞
→ ckc1ark: 建議用8/1*7/2*6/3 這樣整數除法不會出問題 只怕太大而已
好的 我明天試看看
→ alan23273850: 這也就是為什麼你直接把 56.0 轉過去會對，但用運算
→ alan23273850: 的方式會錯就是。
→ alan23273850: clark大指的是 8*7*6/1/2/3 吧
我一開始就是用這個方法，只是我猜教學平台用的測資很大會overflow，所以這方法過不了
。
推 TMDTMD2487: 請問一下為什麼不用遞迴做top down, 怕太慢就從下buil
當下感覺離答案很接近就被這個方法綁住了。
→ TMDTMD2487: d up起來就好了
→ TMDTMD2487: C(n, m) = C(n – 1, m – 1) + C(n – 1, m)
→ alan23273850: 他馬的大大說的就是 dynamic programming 解
→ TMDTMD2487: 這公式高中就交過了吧 這樣不會超過ㄅ
→ TMDTMD2487: DP難的地方是從問題找遞迴
推 ckc1ark: 8/1*7/2*6/3沒錯 過程中都會是整數
→ TMDTMD2487: n*m的陣列從0,0開始算到n,m 作業試試這樣寫 不行的話
→ TMDTMD2487: 遞迴慢慢做也行
※ 編輯: mpyh12345 (220.143.164.143), 11/22/2018 02:00:04
※ 編輯: mpyh12345 (220.143.164.143), 11/22/2018 02:02:57
→ alan23273850: 喔喔 是我誤會clark大的意思ㄌ
→ alan23273850: 順便提醒一下這種題目測資範圍會影響解法的一定要
→ alan23273850: 給，不然就不是好題目
→ IcecreamHsu: for i=1; i<=n; p *= (m-i+1)/i; Cm取n的話這樣就好
→ IcecreamHsu: 噢抱歉推文有寫了 請忽略
推 bigpigbigpig: 可以考慮用質因數分解法，應該就不會 overflow 了。