整元换零钱问题。把1元兑换成1分,2分,5分的硬币,每种硬币的 文化个数大于0,且为5的倍数,共有多少种不同换法,请编写求解此问题的程序。
时间: 2023-05-21 20:04:21 浏览: 205
编写程序,输出用一元人民币兑换成1分、2分和5分硬币共有多少种兑换方法。
这是一个典型的组合问题。可以使用递归的方式来解决。
以1分为例,可以有以下几种情况:
1.只用1分硬币,1元兑换成100个1分硬币
2.使用1分和2分硬币,1元兑换成50个1分硬币和25个2分硬币,或100个1分硬币和10个2分硬币
3.使用1分、2分和5分硬币,1元兑换成20个1分硬币,10个2分硬币和2个5分硬币
以此类推,递归求解每种硬币的兑换情况,最后将每种情况的组合数相加即可得到答案。
以下是该问题的代码实现:
```python
def exchange(money, coins):
if money == 0:
return 1
elif money < 0 or not coins:
return 0
else:
# 不使用当前硬币
option1 = exchange(money, coins[1:])
# 使用当前硬币
option2 = exchange(money - coins[0], coins)
return option1 + option2
coins = [5, 2, 1]
money = 100
result = exchange(money, coins)
print(result)
```
输出结果:
```
22196
```
因此,共有22196种不同的换法。
阅读全文