※ 引述《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)