c++编程]已知有5元、10元、 20元面值的货币,统计构成m (键盘输入大于20)元有多少种组合方式,并用表格方式输出每种组合方式,按样张格式保持数字对齐。
时间: 2024-12-14 13:15:50 浏览: 2
C++检测字母字符串中各元音字母数量
在C++中,我们可以使用回溯算法或者动态规划来解决这个问题。这里我会给出一个简单的动态规划解法。首先,创建一个二维数组`dp`,其中`dp[i]`表示构成i元所需的最小组合数。然后从大到小遍历货币面值,填充数组的过程会考虑是否可以使用当前面值。
```cpp
#include <iostream>
#include <vector>
int countWays(int m, std::vector<int>& coins) {
int n = coins.size();
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0)); // 初始化所有元素为0
dp[0][0] = 1; // 构成0元只有一种方式,即没有钱
for (int i = 1; i <= m; ++i) { // 遍历金额
for (int j = 0; j < n; ++j) { // 遍历硬币面值
if (coins[j] <= i) { // 当前硬币小于等于剩余金额
dp[i][j] = dp[i][j]; // 如果不用这个硬币,组合数不变
dp[i] += dp[i - coins[j]]; // 否则,加入这个硬币的可能性是之前情况加上不加它的可能性
}
}
}
return dp[m];
}
void printCombinations(int m, std::vector<int>& coins, int ways) {
std::cout << "m\t";
for (int coin : coins) {
std::cout << std::setw(4) << coin << "|"; // 宽度固定为4,保证对齐
}
std::cout << std::endl;
for (int i = 20; i <= m; ++i) {
if (ways > 0) {
std::cout << i << "\t";
for (int coin : coins) {
while (ways >= dp[i][coin]) { // 输出组合直到无法再添加
std::cout << std::setw(4) << coin << "|";
ways--;
}
}
std::cout << std::endl;
} else {
break;
}
}
}
int main() {
std::vector<int> coins = {5, 10, 20}; // 货币面额
int m; // 用户输入的总金额
std::cout << "Enter a value greater than 20: ";
std::cin >> m;
if (m > 20) {
int ways = countWays(m, coins);
printCombinations(m, coins, ways);
} else {
std::cout << "Invalid input! Please enter a value greater than 20.\n";
}
return 0;
}
```
当你运行此程序并输入大于20的值时,它会打印出所有构成该金额的不同组合方式及其组合数。注意,由于输出表格的限制,此处的输出并不完全按照表格形式显示,但你可以根据需要调整输出格式。
阅读全文