用C++编写以下程序：设有50、20、10、5、1面额的零钱，假设各种面额的零钱数量足够多。若顾客购物花了n元，在支付大于等于n的整百元后，收银员应如何找零，才能使找回的钱数最少。 所谓大于等于n的整百元，是指这样，如购物花了201元，则需支付300元，如花了200元，即支付200元。 输入 测试数据有多组，每组占一行，仅包含一个正整数n（0＜n≤2^31-1）。 输出 对于每组输入数据，输出结果单独占一行，为找回的零钱张数。 样例输入 复制 201 100 样例输出 复制 8 0

好的，下面是代码实现：

#include <iostream>
using namespace std;

int main() {
    int n;
    while(cin >> n) {
        int m = n % 100; // 求出需要找的零钱数
        int cnt = 0; // 零钱张数计数器
        cnt += m / 50; // 先找50元的
        m %= 50;
        cnt += m / 20; // 再找20元的
        m %= 20;
        cnt += m / 10; // 再找10元的
        m %= 10;
        cnt += m / 5; // 再找5元的
        m %= 5;
        cnt += m; // 最后找1元的
        cout << cnt << endl;
    }
    return 0;
}

我们可以通过循环输入的方式处理多组数据，每次读入一个数n，然后通过取模运算求出需要找的零钱数m。接着，我们按照从大到小的顺序，依次找50元、20元、10元、5元和1元的零钱，并将每种零钱的张数加起来，即为最终的答案。最后输出答案即可。

相关问题

用c++编写程序：将一面额为10元倍数的整钱（<=100元）换成1元、2元和5元的零钱组合（每种面值都要有）。输入要换的面额（如10元），输出所有可能的换法（如2种）。

好的，这是一个比较简单的问题，以下是C++的代码实现：

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入要换的面额：";
    cin >> n;
    if (n % 10 != 0 || n > 100) {
        cout << "输入错误，面额必须是10的倍数且小于等于100。" << endl;
        return 0;
    }
    int count = 0;
    for (int i = 0; i <= n / 5; i++) {
        for (int j = 0; j <= n / 2; j++) {
            int k = n - i * 5 - j * 2;
            if (k >= 0 && k % 1 == 0) {
                count++;
                cout << "第" << count << "种换法：";
                cout << i << "张5元，" << j << "张2元，" << k << "张1元。" << endl;
            }
        }
    }
    cout << "一共有" << count << "种换法。" << endl;
    return 0;
}

以上代码中，我们首先输入要换的面额，然后判断是否符合条件（即10的倍数且小于等于100），然后使用两层循环分别枚举5元和2元的张数，再根据总面额计算出1元的张数，最后输出所有可能的换法和总数。

将一张100 元的钞票换成1 元、2元、5 元和10 元的零钱，每种零钞至少一张，编写程序输出所有的换法，尽可能地提高算法效率。（c++）

为了实现这个需求，你可以使用回溯算法（Backtracking）。下面是一个简单的C++程序示例，它会递归地遍历所有可能的组合，直到达到目标金额：

#include <iostream>
#include <vector>

void change(int money, std::vector<int>& coins, int index = 0) {
    if (money == 0) {  // 找到一种完全匹配的组合
        for (int coin : coins) {
            std::cout << coin << " ";
        }
        std::cout << "\n";
        return;
    }

    // 尝试将当前面值放入组合
    if (index < coins.size() && money >= coins[index]) {
        coins[index]++;
        change(money - coins[index], coins, index);
        coins[index]--;
    }

    // 如果当前面值不足以填充剩余金额，尝试下一个更大的面值
    if (index + 1 < coins.size()) {
        change(money, coins, index + 1);
    }
}

int main() {
    const int targetMoney = 100;  // 目标金额100元
    std::vector<int> coins = {1, 2, 5, 10};  // 零钞种类及面额

    std::cout << "All possible combinations to change " << targetMoney << " into smaller coins:\n";
    change(targetMoney, coins);

    return 0;
}

在这个程序中，`change`函数接受当前剩余的金额、零钞列表以及遍历的索引。当找到可行的组合时，就打印出来。如果没有更多的零钞可以使用，就会回到上一级去尝试其他组合。