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