程序员的数学之递归下

假设有四种面额的钱币,1 元、2 元、5 元和 10 元,而您一共给我 10 元,那您可以奖赏我 1 张 10 元,或者 10 张 1 元,或者 5 张 1 元外加 1 张 5 元等等。 如果考虑每次奖赏的金额和先后顺序,那么最终一共有多少种不同的奖赏方式呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
# coding=utf-8
import copy

rewards = [1, 2, 5, 10] # 四种面额的纸币


def get_all_components(total_rewards, result=None):
"""
使用函数的递归(嵌套调用),找出所有可能的奖赏组合
:param
total_rewards 奖赏总金额
result 保存当前的解
:return: None
"""
# 当 total_rewards=0 时,证明它是满足条件的解,结束嵌套调用,输出解
if result is None:
result = []
if total_rewards == 0:
print(result)
return
# 当 total_rewards<0 时,证明它不是满足条件的解,不输出
elif total_rewards < 0:
return
else:
for i, _ in enumerate(rewards):
new_result = copy.copy(result) # 由于有4种情况,需要 clone 当前的解并传入被调用的函数
new_result.append(rewards[i]) # 记录但当前但选择,解决一点问题
get_all_components(total_rewards-rewards[i], new_result) # 剩下但问题,留给嵌套调用去解决


if __name__ == '__main__':
total_reward = 10
get_all_components(total_reward)