Cash

US coins

要解决的问题

假设你在商店工作，一位顾客给了你 $1.00（100 美分）来购买一颗价格为 $0.50（50 美分）的糖果。你需要找给顾客“零钱”，也就是扣除糖果价格后剩下的金额。找零时，你很可能希望尽量减少给每位顾客的硬币数量，以免硬币用完（或惹恼顾客！）。请在名为 cash 的文件夹中创建 cash.c，并用 C 实现一个程序，打印给定找零金额所需的最少硬币数，金额单位为美分，如下所示：

Change owed: 25
1

不过，程序应提示用户输入一个大于等于 0 的 int，这样它就能处理任意找零金额：

Change owed: 70
4

如果用户输入的值不是大于等于 0（或者根本不是 int！），请根据需要反复重新提示用户。

演示

贪心算法

幸运的是，计算机科学为各地收银员提供了一种尽量减少找零硬币数量的方法：贪心算法。

根据美国国家标准与技术研究院（NIST）的说法，贪心算法是在寻找答案时“总是选择当前立即可得的最佳解，或局部最优解”的算法。贪心算法能为某些优化问题找到整体或全局最优解，但在其他一些问题实例中，也可能得到并非最优的解。

这是什么意思呢？假设收银员需要给顾客找一些零钱，而抽屉里有 25 美分、10 美分、5 美分和 1 美分的硬币。要解决的问题是：应该给顾客哪些硬币，以及每种给多少枚。可以把“贪心”的收银员理解为：每次从抽屉里拿硬币时，都希望尽可能大幅度地缩小这个问题。例如，如果要找给顾客 41 美分，第一步能拿的最大一口（也就是当前最佳或局部最佳选择）是 25 美分。（之所以说它“最佳”，是因为它比任何其他硬币都更快让剩余金额接近 0 美分。）注意，这一口会把 41 美分的问题缩小成 16 美分的问题，因为 41 - 25 = 16。也就是说，剩余部分是一个类似但更小的问题。显然，再拿一枚 25 美分就太多了（假设收银员不想亏钱），所以贪心收银员会转而拿 10 美分，剩下 6 美分。此时，贪心选择会先拿 5 美分，再拿 1 美分，问题就解决了。顾客收到一枚 25 美分、一枚 10 美分、一枚 5 美分和一枚 1 美分：总共四枚硬币。

事实证明，对于美国货币（以及欧元货币）来说，这种贪心方法不仅局部最优，也能达到全局最优。也就是说，只要收银员每种硬币都有足够数量，从大到小找零就能得到最少的硬币数。到底有多少？这就由你来告诉我们了！

建议

先写一些确定能编译的代码

即使这个程序暂时什么也不做，它至少应该能用 make 编译！

#include <cs50.h>
#include <stdio.h>

int main(void)
{

}

注意，你现在已经包含了 cs50.h 和 stdio.h 这两个“头文件”，它们会让你能够使用可能有助于解决本题的函数。

在继续写更多代码前，先写一些伪代码

如果你还不确定如何解决问题本身，可以先把它拆成几个更小、你大概能先解决的问题。例如，这个问题其实只包含少数几个步骤：

提示用户输入应找零金额，单位为美分。
计算应给顾客多少枚 quarters（25 美分）。从美分总额中减去这些 quarters 的金额。
计算应给顾客多少枚 dimes（10 美分）。从剩余美分中减去这些 dimes 的金额。
计算应给顾客多少枚 nickels（5 美分）。从剩余美分中减去这些 nickels 的金额。
计算应给顾客多少枚 pennies（1 美分）。从剩余美分中减去这些 pennies 的金额。
把用到的 quarters、dimes、nickels 和 pennies 数量相加。
打印这个总数。

这就是可以用来解决本题的贪心算法，所以我们先把伪代码写成注释，提醒自己完成这些步骤：

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Prompt the user for change owed, in cents

    // Calculate how many quarters you should give customer
    // Subtract the value of those quarters from cents

    // Calculate how many dimes you should give customer
    // Subtract the value of those dimes from remaining cents

    // Calculate how many nickels you should give customer
    // Subtract the value of those nickels from remaining cents

    // Calculate how many pennies you should give customer
    // Subtract the value of those pennies from remaining cents

    // Sum the number of quarters, dimes, nickels, and pennies used
    // Print that sum
}

把伪代码转换成代码

首先，思考如何提示用户输入应找零的美分数。回忆一下，当你希望某件事至少执行一次，并且可能反复执行时，do while 循环会很有帮助，如下所示：

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Prompt the user for change owed, in cents
    int cents;
    do
    {
        cents = get_int("Change owed: ");
    }
    while (cents < 0);
}

现在先停下来，对程序运行 make 是个好主意。测试并确认程序可以编译，并且当你输入小于 0 的美分数（或输入 “cat” 这样的内容）时会重新提示。

接下来，思考如何计算应给顾客多少枚 quarters。由于我们使用的是贪心算法，这个问题变成了“最多能给多少枚 quarters？”你可以直接在 main 函数中解决这个问题。不过，写一个新函数可能会让思路更清晰，例如命名为 calculate_quarters。这样你就能更专注于计算 quarters 的逻辑。之后，再把这个函数整合进更大的解法中。

int calculate_quarters(int cents)
{
    // Calculate how many quarters you should give customer
}

注意，这个函数确实命名为 calculate_quarters。括号中的 int cents 表示它接受一个名为 cents 的 int 作为输入。而函数名前面的 int 表示它也应该“返回”一个 int。也就是说，这个函数的输出是一个整数：能够放入 cents 金额中的 quarters 数量。

现在看看这种实现 calculate_quarters 的方法：不断增加 quarters 的数量，直到剩余美分不足以再转换成 quarter：

int calculate_quarters(int cents)
{
    // Calculate how many quarters you should give customer
    int quarters = 0;
    while (cents >= 25)
    {
        quarters++;
        cents = cents - 25;
    }
    return quarters;
}

当然，至少还有一种更简单的方法可以解决这个 calculate_quarters 问题。不过，这就留给你来思考了！

当 calculate_quarters 按预期工作后，你就可以把这个函数整合进程序中。注意要在 main 函数上方“声明”该函数的“签名”（即 int calculate_quarters(int cents)），这样你就能在 main 中使用 calculate_quarters，同时把函数定义放在 main 下方。

#include <cs50.h>
#include <stdio.h>

int calculate_quarters(int cents);

int main(void)
{
    // Prompt the user for change owed, in cents
    int cents;
    do
    {
        cents = get_int("Change owed: ");
    }
    while (cents < 0);

    // Calculate how many quarters you should give customer
    int quarters = calculate_quarters(cents);

    // Subtract the value of those quarters from cents
    cents = cents - (quarters * 25);
}

int calculate_quarters(int cents)
{
    // Calculate how many quarters you should give customer
    int quarters = 0;
    while (cents >= 25)
    {
        quarters++;
        cents = cents - 25;
    }
    return quarters;
}

已经解决了几个小问题，还剩几个要完成！有没有注意到这里可以复用的模式？

如何测试

对于这个程序，请尝试手动测试你的代码。这是很好的练习：

如果输入 -1，程序会再次提示你吗？
如果输入 0，程序会输出 0 吗？
如果输入 1，程序会输出 1（即一枚 penny）吗？
如果输入 4，程序会输出 4（即四枚 pennies）吗？
如果输入 5，程序会输出 1（即一枚 nickel）吗？
如果输入 24，程序会输出 6（即两枚 dimes 和四枚 pennies）吗？
如果输入 25，程序会输出 1（即一枚 quarter）吗？
如果输入 26，程序会输出 2（即一枚 quarter 和一枚 penny）吗？
如果输入 99，程序会输出 9（即三枚 quarters、两枚 dimes 和四枚 pennies）吗？

正确性

check50 cs50/problems/2026/x/cash

代码风格

style50 cash.c

在终端中执行以下命令提交你的作业，并按提示完成操作。

submit50 cs50/problems/2026/x/cash