编写一个C++风格的程序,解决百钱问题:将一元人民币兑换成1、2、5分的硬币,有多少种换法?
时间: 2024-09-21 18:04:43 浏览: 41
在C++中,解决“百钱问题”可以使用动态规划的方法,创建一个二维数组来存储每个金额兑换成1分、2分和5分硬币的不同组合数。以下是简单的C++代码示例:
```cpp
#include <iostream>
using namespace std;
int change(int money, int coins[3]) {
// 初始化状态数组,对于0元的情况,有1种换法(不用换)
static const int dp[101] = {0};
if (money == 0) return 1;
// 如果已经计算过这个金额,直接返回结果
if (dp[money] != 0) return dp[money];
// 对于1分、2分、5分,分别尝试添加到当前金额,并更新总换法数
dp[money] = 0;
for (int i = 0; i <= coins[2]; i++) {
if (i * 5 <= money) {
dp[money] += change(money - i * 5, coins);
}
if (i * 2 <= money && i * 5 + coins[1] * 2 <= money) {
dp[money] += change(money - i * 2, coins);
}
if (coins[0] * 1 <= money && i * 2 + coins[1] * 2 + coins[0] * 5 <= money) {
dp[money] += change(money - coins[0], coins);
}
}
return dp[money];
}
int main() {
int coins[] = {1, 2, 5}; // 分别代表1分、2分和5分硬币
int total_ways = change(100, coins); // 求100分的换法总数
cout << "将100元兑换成" << coins[0] << "分、" << coins[1] << "分和" << coins[2] << "分硬币的换法共有 " << total_ways << " 种。\n";
return 0;
}
```
在这个代码中,`change`函数通过递归遍历所有可能的组合,计算出给定金额的不同兑换方式。主函数最后打印出100分的换法总数。
阅读全文