为什么我的2022 CS50现金贪婪算法会输出不同数量的硬币，然后手动计算？

Question

我要进行CS50X，而没有编码的事先了解，并将其陷入第二周问题集1。这是一个贪婪的算法问题，其中该程序计算了要偿还更改的硬币数量。该代码通过CS50自动检查，但在自我检查上存在问题。

例子： 如果我在提示中输入5更改，则应该给我2个硬币 - 一个镍和一分钱（5 + 1），但代码代替输出4个硬币。 如果我在提示上输入160更改（与CS50检查工具的用途相同），则应该给我7个硬币 - 六个季度和一个一角钱（6 + 1）。相反，此代码为我提供了9个硬币。

我挠头，因为如果我使用计算器并手动通过循环时进行操作，那么输出应该输出的内容是有意义的，但是显然，程序的工作方式不同。

有什么想法吗？

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

int get_cents(void);
int calculate_quarters(int cents);
int calculate_dimes(int cents);
int calculate_nickels(int cents);
int calculate_pennies(int cents);

int main(void)
{
    // Ask how many cents the customer is owed
    int cents = get_cents();

    // Calculate the number of quarters to give the customer
    int quarters = calculate_quarters(cents);
    cents = cents - quarters * 25;

    // Calculate the number of dimes to give the customer
    int dimes = calculate_dimes(cents);
    cents = cents - dimes * 10;

    // Calculate the number of nickels to give the customer
    int nickels = calculate_nickels(cents);
    cents = cents - nickels * 5;

    // Calculate the number of pennies to give the customer
    int pennies = calculate_pennies(cents);
    cents = cents - pennies * 1;

    // Sum coins
    int coins = quarters + dimes + nickels + pennies;

    // Print total number of coins to give the customer
    printf("%i\n", coins);
}

int get_cents(void)
{
    //Ask for how much change is owed
    int cents = 0;
    do
    {
        cents = get_int("Change owed: ");
    }
    while (cents <= 0);
    return cents;
}

int calculate_quarters(int cents)
{
    //Continue to check for how many quarters fit into input amout of change
    int quarters = 0;
    do
    {
        cents = cents - 25;
        quarters++;
    }
    while (cents >= 25);
    return quarters;
}

int calculate_dimes(int cents)
{
    //Continue to check for how many cents fit into input amout of change after subtracting quarters
    int dimes = 0;
    do
    {
        cents = cents - 10;
        dimes++;
    }
    while (cents >= 10);
    return dimes;
}

int calculate_nickels(int cents)
{
    int nickels = 0;
    do
    {
        cents = cents - 5;
        nickels++;
    }
    while (cents >= 5);
    return nickels;
}

int calculate_pennies(int cents)
{
    int pennies = 0;
    do
    {
        cents = cents - 1;
        pennies++;
    }
    while (cents >= 1);
    return pennies;
}

Answer 1

您使用do/而循环来计算每种硬币的数量，因此，您始终至少计算每种硬币的一枚硬币，这是不正确的。例如，如果您有2美分要分发，您将获得1季度，Cents将成为-3，然后1毛钱和Cents变成<代码> -13 等。产生4个需要2个硬币。

可以使用调试器诊断此问题，或者仅通过添加printf（“ QUARTER =％d，Cents =％d \ n”，季度，Cents）;语句在调用计算>计算> counculate_dimes（美分）。

您应该使用，而循环。更一般而言，您应该避免do/循环。它们很少是正确的工具。

这是一个修改版本：

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

int get_cents(void);
int calculate_quarters(int cents);
int calculate_dimes(int cents);
int calculate_nickels(int cents);
int calculate_pennies(int cents);

int main() {
    // Ask how many cents the customer is owed
    int cents = get_cents();

    // Calculate the number of quarters to give the customer
    int quarters = calculate_quarters(cents);
    cents = cents - quarters * 25;

    // Calculate the number of dimes to give the customer
    int dimes = calculate_dimes(cents);
    cents = cents - dimes * 10;

    // Calculate the number of nickels to give the customer
    int nickels = calculate_nickels(cents);
    cents = cents - nickels * 5;

    // Calculate the number of pennies to give the customer
    int pennies = calculate_pennies(cents);
    cents = cents - pennies * 1;

    // Sum coins
    int coins = quarters + dimes + nickels + pennies;

    // Print total number of coins to give the customer
    printf("%d\n", coins);
    return 0;
}

int get_cents(void) {
    //Ask for how much change is owed
    for (;;) {
        int cents = get_int("Change owed: ");
        if (cents > 0)
            return cents;
        printf("number must be positive\n");
    }
}

int calculate_quarters(int cents) {
    //Continue to check for how many quarters fit into input amout of change
    int quarters = 0;
    while (cents >= 25) {
        cents = cents - 25;
        quarters++;
    }
    return quarters;
}

int calculate_dimes(int cents) {
    //Continue to check for how many cents fit into input amout of change after subtracting quarters
    int dimes = 0;
    while (cents >= 10) {
        cents = cents - 10;
        dimes++;
    }
    return dimes;
}

int calculate_nickels(int cents) {
    int nickels = 0;
    while (cents >= 5) {
        cents = cents - 5;
        nickels++;
    }
    return nickels;
}

int calculate_pennies(int cents) {
    return cents;
}

但是，请注意，使用整数除法和剩余的方法有一个更简单的方法：

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

int get_cents(void);

int main() {
    // Ask how many cents the customer is owed
    int cents = get_cents();

    // Calculate the number of quarters to give the customer
    int quarters = cents / 25;
    cents = cents % 25;

    // Calculate the number of dimes to give the customer
    int dimes = cents / 10;
    cents = cents % 10;

    // Calculate the number of nickels to give the customer
    int nickels = cents / 5;
    cents = cents % 5;

    // Calculate the number of pennies to give the customer
    int pennies = cents;

    // Sum coins
    int coins = quarters + dimes + nickels + pennies;

    // Print total number of coins to give the customer
    printf("%d\n", coins);
    return 0;
}

int get_cents(void) {
    //Ask for how much change is owed
    for (;;) {
        int cents = get_int("Change owed: ");
        if (cents > 0)
            return cents;
        printf("number must be positive\n");
    }
}

上述功能是一个很好的折衷...下面是所有操作的替代方法，所有操作都合并为单个表达式。您可以将其研究以获取信息，这是一个较小的示例，即在制作与以前版​​本非常相似的代码时更难以理解。

int main() {
    // Ask how many cents the customer is owed
    int cents = get_cents();

    // Compute the number of coins
    int coins = cents / 25 + cents % 25 / 10 + cents % 25 % 10 / 5 + cents % 5;

    // Print total number of coins to give the customer
    printf("%d\n", coins);
    return 0;
}

Answer 2

您的计算_*功能都有一个错误。如果所提供的美分开始低于您在中测试的值{...}时（Cents＆Gt; = value）;'怎么办？功能将返回1。也就是说，他们总是会返回1太多。它们都应重写为，而（Cents＆Gt; = value）{...}

int calc(int cents, int val) {
    int result = 0;
    while(cents >= val) {
        ++result;
        cents -= val;
    }
    return result;
}

int calculate_quarters(int cents) {
    return calc(cents, 25);
}

int calculate_dimes(int cents) {
    return calc(cents, 10);
}

int calculate_nickels(int cents) {
    return calc(cents, 5);
}

int calculate_pennies(int cents) {
    return calc(cents, 1);
}