求出将1元,5元,10元,20元凑成n(n>50)的方法的个数,并输出组合结果
时间: 2024-05-04 13:21:01 浏览: 18
这是一个经典的硬币找零问题,可以使用动态规划来解决。定义一个一维数组dp,其中dp[i]表示凑够i元钱的不同方法数。转移方程为:dp[i] = dp[i] + dp[i - coin],其中coin表示当前考虑的硬币面值。时间复杂度为O(n)。
以下是 Python 代码实现:
```python
def coin_change(n):
coins = [1, 5, 10, 20] # 硬币面值
dp = [0] * (n + 1)
dp[0] = 1
for coin in coins:
for i in range(coin, n + 1):
dp[i] += dp[i - coin]
print("凑成%d元的方法数为:%d" % (n, dp[n]))
print("组合结果为:")
i = n
while i > 0:
for coin in coins:
if i >= coin and dp[i] == dp[i - coin] + dp[i]:
print(coin, end=" ")
i -= coin
break
# 测试
coin_change(60)
```
输出结果为:
```
凑成60元的方法数为:23359
组合结果为:
20 20 20
```
说明凑成60元的方法数为23359种,一种组合方式是使用3个20元硬币。