硬币找零c++代码
时间: 2023-07-09 18:21:38 浏览: 129
以下是一个简单的硬币找零的 C++ 代码示例:
```c++
#include <iostream>
using namespace std;
int main() {
int total, coin, num, count = 0;
int coins[] = {50, 20, 10, 5, 1}; // 硬币面值
cout << "请输入总金额:";
cin >> total;
for (int i = 0; i < 5; i++) {
coin = coins[i]; // 当前硬币面值
num = total / coin; // 当前硬币数量
total -= num * coin; // 更新总金额
count += num; // 累计硬币数量
if (num > 0) {
cout << "找到" << num << "个" << coin << "分硬币" << endl;
}
}
cout << "总共找零" << count << "个硬币" << endl;
return 0;
}
```
输入总金额后,程序会依次计算每种硬币的数量,并输出找到的硬币数量和面值。最后,输出总共找到的硬币数量。
相关问题
贪心算法实现硬币找零问题C++
贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择,希望导致结果是全局最好或最优的策略。在硬币找零问题(Coin Change Problem)中,给定一组面额,我们要找出最小的硬币组合来凑够一个目标金额。
在C++中,可以使用动态规划结合贪心思想解决这个问题。首先定义一个二维数组dp,其中dp[i]表示找零i所需的最小硬币数。然后按照从大到小的面额顺序遍历:
1. 初始化所有dp值为无穷大,除了dp[0]=0,因为0元不需要硬币。
2. 对于每个面额j,如果目标金额i大于等于j,则更新dp[i],取dp[i]和dp[i-j]+1中的较小者,即保留原有的方案或是加上一枚面额j的硬币。
3. 当遍历完所有面额后,dp[target]就是最小的硬币组合数。
以下是简单的C++代码示例:
```cpp
#include <vector>
using namespace std;
int coinChange(vector<int>& coins, int target) {
vector<int> dp(target + 1, INT_MAX); // dp数组初始化为无穷大
dp[0] = 0; // 目标金额为0的情况,无需硬币
for (int i = 1; i <= target; ++i) { // 遍历目标金额
for (int j : coins) { // 遍历硬币面额
if (j <= i && dp[i - j] != INT_MAX) { // 如果足够支付,尝试减去并更新dp
dp[i] = min(dp[i], dp[i - j] + 1);
}
}
}
return dp[target] == INT_MAX ? -1 : dp[target]; // 返回最小硬币数,找不到组合则返回-1
}
硬币找零问题贪心算法c++ 完整版
根据提供的引用内容,这里提供一个硬币找零问题的贪心算法C++完整版的示例代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
vector<int> coinChange(int amount, vector<int>& coins) {
vector<int> res(coins.size(), 0);
for (int i = coins.size() - 1; i >= 0; i--) {
res[i] = amount / coins[i];
amount %= coins[i];
}
if (amount != 0) {
res.clear();
res.push_back(-1);
}
return res;
}
int main() {
int amount = 123;
vector<int> coins = {1, 5, 10, 20, 50, 100};
vector<int> res = coinChange(amount, coins);
if (res.size() == 1 && res[0] == -1) {
cout << "No solution" << endl;
} else {
int sum = 0;
for (int i = 0; i < res.size(); i++) {
sum += res[i];
cout << coins[i] << " yuan: " << res[i] << endl;
}
cout << "Total number of coins: " << sum << endl;
}
return 0;
}
```
该算法的思路是:从面值最大的硬币开始,尽可能多地使用该硬币,直到无法再使用为止,然后再使用面值次大的硬币,以此类推,直到找零金额为0或者无法找零为止。该算法的时间复杂度为O(nlogn),其中n为硬币的种类数。
阅读全文