编写一个C++风格的程序,解决百钱问题:将一元人民币兑换成1角、2角、5角的硬币,有多少种换法
时间: 2024-09-23 18:01:57 浏览: 6
在C++中,解决百钱问题可以使用回溯法或者动态规划。下面是一个使用动态规划的解决方案,因为这个问题可以用一个二维数组记录每种组合情况:
```cpp
#include <iostream>
using namespace std;
// 定义状态转移方程
int change(int money, int coins[], int coinValues[], int n, bool dp[]) {
if (money == 0)
return 1;
if (money < 0 || dp[money])
return 0;
dp[money] = 1;
for (int i = 0; i < n; ++i) {
int subMoney = money - coinValues[i];
if (subMoney >= 0)
dp[money] += change(subMoney, coins, coinValues, n, dp);
}
return dp[money];
}
int main() {
int totalMoney = 100; // 百元总金额
int coins[] = {1, 2, 5}; // 可用硬币面额
int coinValues[] = {1, 2, 5}; // 硬币价值
int numCoins = sizeof(coins) / sizeof(coins[0]); // 面额种类数
bool dp[totalMoney + 1]; // 初始化动态规划数组
memset(dp, false, sizeof(dp));
cout << "Number of ways to make change using " << numCoins << " types of coins: " << change(totalMoney, coins, coinValues, numCoins, dp) << endl;
return 0;
}
```
在这个程序中,`change`函数通过动态规划解决了问题,dp数组的每个元素表示从0元到当前钱数的钱币组合总数。