编译器:C++ (g++) 编写一个C++风格的程序,解决百钱问题:将一元人民币兑换成1、2、5分的硬币,有多少种换法?
时间: 2024-09-09 13:01:52 浏览: 61
在C++中,我们可以编写一个函数来解决百钱问题,通过动态规划的方法计算出不同金额下的换法数。以下是一个简单的示例:
```cpp
#include <iostream>
using namespace std;
int change(int money, int coins[3]) {
// 创建一个二维数组 dp,其中 dp[i] 存储的是 i 分的硬币组合数
int dp[money + 1];
for (int i = 0; i <= money; ++i) {
dp[i] = 0;
}
// 初始化基础情况,没有硬币时只能换0种
dp[0] = 1;
// 遍历所有可能的硬币面额,更新dp数组
for (int coin : coins) {
for (int i = coin; i <= money; ++i) {
dp[i] += dp[i - coin]; // 加上当前硬币可以增加的所有组合
}
}
return dp[money];
}
int main() {
int coins[] = {1, 2, 5}; // 1分、2分、5分硬币
int totalCoins = change(100, coins); // 要求兑换100分
cout << "有 " << totalCoins << " 种换法." << endl;
return 0;
}
```
在这个程序中,`change` 函数通过遍历每种硬币并更新状态数组,最终返回了指定金额下换法的数量。在主函数中,我们传入1分、2分、5分的硬币数组和目标金额100分。
阅读全文