硬币找零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++ 完整版

根据提供的引用内容，这里提供一个硬币找零问题的贪心算法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为硬币的种类数。

c++最少 硬币数的找零

这是一个经典的动态规划问题。假设有一个长度为 n 的数组 coins，表示所有可用的硬币面额，还有一个整数 amount，表示需要找零的总金额。我们需要计算出最少需要多少个硬币才能凑出总金额。

我们可以用一个长度为 amount+1 的数组 dp 来记录每个金额所需的最少硬币数。初始时，将 dp 数组全部赋值为 amount+1，因为无论如何，最多只能用 amount 个硬币凑出总金额，超过这个数量就没有意义了。

然后，我们依次对每个金额进行遍历，对于每个金额 i，我们从所有可用的硬币面额中选择一个硬币 j，如果 j 小于等于 i，说明这个硬币可以用来凑出金额 i。我们可以用一个状态转移方程来更新 dp[i] 的值：

dp[i] = min(dp[i], dp[i-j]+1)

其中 dp[i-j]+1 表示用一个硬币 j 凑出金额 i-j，并且需要再加上一个硬币 j 才能凑出金额 i。我们需要在所有可用的硬币面额中找到一个能够凑出金额 i 的最小值，这就是 dp[i] 的最终值。

最后，如果 dp[amount] 的值仍然是 amount+1，说明无法用给定的硬币凑出总金额，返回 -1；否则返回 dp[amount]。

下面是 C++ 的代码实现：

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount+1, amount+1);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < coins.size(); j++) {
            if (coins[j] <= i) {
                dp[i] = min(dp[i], dp[i-coins[j]]+1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}