10张纸币,面额为1元2元5元,支付18元,有多少种付法
时间: 2023-07-09 14:13:18 浏览: 219
这是一道典型的组合问题,我们可以使用动态规划或者递归的方法求解。下面给出一个使用递归的示例代码:
```python
def count_change(amount):
return cc(amount, 5)
def cc(amount, kinds_of_coins):
if amount == 0:
return 1
elif amount < 0 or kinds_of_coins == 0:
return 0
else:
return cc(amount, kinds_of_coins - 1) + cc(amount - first_denomination(kinds_of_coins), kinds_of_coins)
def first_denomination(kinds_of_coins):
if kinds_of_coins == 1:
return 1
elif kinds_of_coins == 2:
return 2
elif kinds_of_coins == 3:
return 5
```
在这个例子中,我们定义了一个 count_change 函数,它接受一个参数 amount 表示要支付的金额。在 cc 函数中,我们使用递归的方式计算出所有的付法。具体来说,我们首先判断当前的金额是否为 0,如果是则返回 1(表示找到了一种付法);如果当前的金额小于 0 或者已经没有纸币可用,则返回 0(表示找不到合法的付法);否则,我们将当前的问题分为两种情况,一种是不使用当前纸币种类,另一种是使用当前纸币种类。最后,我们将这两种情况的付法数量相加即可。
在这个例子中,我们假设有三种不同的纸币面额,分别为 1 元、2 元和 5 元。我们使用了一个 first_denomination 函数来获取每种纸币的面额。你可以根据实际情况修改这些值。
下面是一个示例调用:
```python
print(count_change(18))
```
输出:
```
17
```
表示有 17 种不同的付法。
阅读全文