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

看板C_and_CPP作者 (嘉義金城武)時間7年前 (2018/11/22 01:29), 7年前編輯推噓7(7推 0噓 27→)
留言34則, 6人參與, 7年前最新討論串1/1
不好意思，作業應該要自己做的， 但是有筆測資輸出了我怎麼想都想不出來的結果。 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
推
11/22 01:40, 7年前 , 1F
真神奇，我自己試出來也是 55，很肯定是從 double
11/22 01:40, 1F
→
11/22 01:40, 7年前 , 2F
轉成 long long 的問題，但是解釋不出理由
11/22 01:40, 2F
→
11/22 01:43, 7年前 , 3F
用 float 的話就沒錯
11/22 01:43, 3F
推
11/22 01:45, 7年前 , 4F
浮點數的運算都是有誤差的，不然你把每一輪的c用doubl
11/22 01:45, 4F
→
11/22 01:45, 7年前 , 5F
e型態印出來看
11/22 01:45, 5F
→
11/22 01:47, 7年前 , 6F
https://goo.gl/5vCq8X 這邊有人有嘗試過
11/22 01:47, 6F
推
11/22 01:47, 7年前 , 7F
return c+0.5應該就好了
11/22 01:47, 7F
→
11/22 01:47, 7年前 , 8F
建議問問題前先餵狗 不過新手可能也不知道怎餵就是
11/22 01:47, 8F
→
11/22 01:48, 7年前 , 9F
給的小知識，新手都以為 double 的範圍很大，所以只
11/22 01:48, 9F
→
11/22 01:48, 7年前 , 10F
要不 overflow 就很安全，事實上不然，因為根據IEEE
11/22 01:48, 10F
瞭解你的意思，所以是浮點數的誤差無關overflow對吧，就我這題來看，誤差累積到一定程 度就會少進位對吧？
→
11/22 01:48, 7年前 , 11F
754 標準，浮點數是採用科學記號表示法，既然是科學
11/22 01:48, 11F
→
11/22 01:49, 7年前 , 12F
記號，在 a*10^e 的 a 那邊位數一旦不夠就會產生
11/22 01:49, 12F
推
11/22 01:49, 7年前 , 13F
c會是55.99999999999999289457
11/22 01:49, 13F
→
11/22 01:49, 7年前 , 14F
rounding error，所以有沒有誤差跟數字大小未必有關
11/22 01:49, 14F
→
11/22 01:50, 7年前 , 15F
那 rounding error 會愈運算差愈多，所謂的誤差傳遞
11/22 01:50, 15F
→
11/22 01:50, 7年前 , 16F
建議用8/1*7/2*6/3 這樣整數除法不會出問題 只怕太大而已
11/22 01:50, 16F
好的 我明天試看看
→
11/22 01:50, 7年前 , 17F
這也就是為什麼你直接把 56.0 轉過去會對，但用運算
11/22 01:50, 17F
→
11/22 01:50, 7年前 , 18F
的方式會錯就是。
11/22 01:50, 18F
→
11/22 01:52, 7年前 , 19F
clark大指的是 8*7*6/1/2/3 吧
11/22 01:52, 19F
我一開始就是用這個方法，只是我猜教學平台用的測資很大會overflow，所以這方法過不了 。
推
11/22 01:53, 7年前 , 20F
請問一下為什麼不用遞迴做top down, 怕太慢就從下buil
11/22 01:53, 20F
當下感覺離答案很接近就被這個方法綁住了。
→
11/22 01:53, 7年前 , 21F
d up起來就好了
11/22 01:53, 21F
→
11/22 01:53, 7年前 , 22F
C(n, m) = C(n – 1, m – 1) + C(n – 1, m)
11/22 01:53, 22F
→
11/22 01:55, 7年前 , 23F
他馬的大大說的就是 dynamic programming 解
11/22 01:55, 23F
→
11/22 01:56, 7年前 , 24F
這公式高中就交過了吧 這樣不會超過ㄅ
11/22 01:56, 24F
→
11/22 01:57, 7年前 , 25F
DP難的地方是從問題找遞迴
11/22 01:57, 25F
推
11/22 01:57, 7年前 , 26F
8/1*7/2*6/3沒錯 過程中都會是整數
11/22 01:57, 26F
→
11/22 01:59, 7年前 , 27F
n*m的陣列從0,0開始算到n,m 作業試試這樣寫 不行的話
11/22 01:59, 27F
→
11/22 01:59, 7年前 , 28F
遞迴慢慢做也行
11/22 01:59, 28F
※ 編輯: mpyh12345 (220.143.164.143), 11/22/2018 02:00:04 ※ 編輯: mpyh12345 (220.143.164.143), 11/22/2018 02:02:57
→
11/22 02:54, 7年前 , 29F
喔喔 是我誤會clark大的意思ㄌ
11/22 02:54, 29F
→
11/22 02:55, 7年前 , 30F
順便提醒一下這種題目測資範圍會影響解法的一定要
11/22 02:55, 30F
→
11/22 02:55, 7年前 , 31F
給，不然就不是好題目
11/22 02:55, 31F
→
11/23 02:08, 7年前 , 32F
for i=1; i<=n; p *= (m-i+1)/i; Cm取n的話這樣就好
11/23 02:08, 32F
→
11/23 02:09, 7年前 , 33F
噢抱歉推文有寫了 請忽略
11/23 02:09, 33F
推
06/24 22:39, 7年前 , 34F
可以考慮用質因數分解法，應該就不會 overflow 了。
06/24 22:39, 34F
‣ 更多 mpyh12345 的文章
文章代碼(AID): #1RzPNY_y (C_and_CPP)