程序员的数学之递归下

发表于 | 分类于 | 阅读次数:
字数统计: 295 | 阅读时长 ≈ 1

假设有四种面额的钱币，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)