推 like9515:了解你的想法了，謝謝綠牡犡助教XDD!! 10/19 00:40
推 chhsiao:其實 使徒四也可以用類似的想法喔~ 10/19 00:44
推 greenoyster:被發現我講這個例子的用意了 XD 10/19 03:06
※ 引述《like9515 (包子小蕭)》之銘言：
: 有一題是用10、5、1來湊成10有幾種方法
: first try用的自訂函數寫法如下
: int count(int target){
: int total = 0;
: if(target == 0)
: return 1;
: if(target >= 10)
: total += count(target - 10);
: if(target >= 5)
: total += count(target - 5);
: if(target >= 1)
: total += count(target - 1);
: return total;
: }
: 但是會多算次數
: 後來助教有教怎麼改
: 我有點忘記了，有人還記得嗎?
: 懇請助教或強者解答~
我後來想了一下 應該用另一種講法比較好懂
原本 count(int target) 的涵意是
要湊成"target"這個數字有幾種湊法
我後來改成 count(int target, int allow) 意義是指
只使用小於等於 "allow" 的幣值 湊成 "target" 一共有幾種湊法
用遞迴的概念想就是 湊成 "target" 有三種可能的方式:
1. 使用 10 元 5元 1元 湊成 target-10 元 再加上一個 10 元
2. 使用 5元 1元 湊成 target-5 元 再加上一個 5 元
3. 使用 1元 湊成 target-1 元 再加上一個 1 元
明顯這三個 set 彼此間沒有交集 而且涵蓋了所有可能情況
因此遞迴式大約是長得像
count(target, allow) =
/ count(target-10, 10) + count(target-5, 5) + count(target-1, 1), if allow == 10
| count(target-5, 5) + count(target-1, 1), if allow == 5
\ count(target-1, 1), if allow == 1
不知道這樣說夠不夠清楚？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.53
※ 編輯: greenoyster 來自: 140.112.30.53 (10/19 00:31)