编写一个C++风格的程序,解决百钱问题:将一元人民币兑换成1、2、5分的硬币,有多少种换法?
时间: 2024-09-12 18:08:23 浏览: 50
在C++中解决百钱问题,可以使用回溯算法。这个问题通常被称为“零钱兑换”问题,目标是找到所有可能的组合,使得总金额等于给定的目标值。下面是一个简单的C++函数来计算兑换100分(即1元)的不同方案数:
```cpp
#include <iostream>
using namespace std;
void change(int coins[], int m, int n, int target) {
if (target == 0) {
cout << "Solution found: " << n << endl;
return;
}
for (int i = 0; i <= m && coins[i] <= target; ++i) {
// 尝试用当前硬币
change(coins, m, n + 1, target - coins[i]);
// 如果还有剩余,继续尝试其他硬币
// 这里为了避免重复计数,当i再次取值时需要更新目标
if (target >= coins[i]) {
change(coins, m, n, target);
}
}
}
// 主函数中初始化硬币数组
int main() {
int coins[] = {1, 2, 5}; // 1分、2分、5分硬币
int m = sizeof(coins) / sizeof(coins[0]); // 硬币种类数
int target = 100; // 目标金额1元
change(coins, m, 0, target);
return 0;
}
```
这个程序会输出100分的所有可能兑换方案数。运行这个程序后,如果存在解,你会看到相应的输出。
阅读全文