c - 为什么 while 循环中的条件语句会导致程序选择性地永远暂停？

Question

我试图通过使用“贪婪算法”来计算偿还找零所需的最小硬币数量是多少。如果用户输入仅一个常量整数的倍数，我在下面编写的程序将按预期工作。然而，当涉及到处理多个硬币时，程序就会永远暂停。

我认为问题出在我的 CountGreed 函数的条件语句的 while 循环中。我尝试过寻找答案，但我遇到的一切似乎都没有给我洞察力来指导我理解我的逻辑出了什么问题。

我知道这是微不足道的，并且在条件语句的循环中存在重复，然后将我带到所陈述的问题。如果用户输入 0.25、0.10、0.05 和 0.01 的倍数，则效果很好。例如，1.00、1.25、0.20，但不是 0.30、1.13、0.26 等。

#include "cs50.h" // Contains declaration for GetFloat()
#include <stdio.h>
#include <math.h>

float PromptChange(void); // Returns customer change in dollars
int ConvertToCents(float); // Returns a conversion from dollars to cents
int CountGreed(int); // Returns the minimum number of coins for which change can be made

int main (void)
{
    float Dollars = PromptChange();
    int Cents = ConvertToCents(Dollars);
    int CoinCount = CountGreed(Cents);
    printf("The minimum number of coins required to give back change is %i.\n", CoinCount);
    return 0;
}

float PromptChange(void)
{
    float Dollars;
    do {
        printf ("Owed change: $");
        Dollars = GetFloat ();
    } while (Dollars < 0);
    return Dollars;
}

int ConvertToCents(float Dollars)
{
    float Cents = Dollars * 100;
    int IntCents = (int)roundf(Cents);
    return IntCents;
}

int CountGreed(int IntCents)
{
    const int Quarter = 25, Dime = 10, Nickel = 5, Penny = 1;
    int SubCoinCount = 0;
    int CoinCount = 0;
    int Remainder = 0;
    while (IntCents) {
        if (IntCents >= Quarter) {
            SubCoinCount = IntCents / Quarter;
            CoinCount += SubCoinCount;
            Remainder += IntCents % Quarter;
            IntCents = Remainder;
        } else if (IntCents < Quarter && IntCents >= Dime) {
            SubCoinCount = IntCents / Dime;
            CoinCount += SubCoinCount;
            Remainder += IntCents % Dime;
            IntCents = Remainder;
        } else if (IntCents < Dime && IntCents >= Nickel) {
            SubCoinCount = IntCents / Nickel;
            CoinCount += SubCoinCount;
            Remainder += IntCents % Nickel;
            IntCents = Remainder;
        } else if (IntCents < Nickel && IntCents >= Penny) {
            SubCoinCount = IntCents / Nickel;
            CoinCount += SubCoinCount;
            Remainder += IntCents % Dime;
            IntCents = Remainder;
        }
    }
    return CoinCount;
}

我粘贴了整个 main.c 文件，以便可以清楚地看到整个程序的流程，尽管问题出在循环上。我在多个编译器上尝试过这个只是为了确保这是我的错。

Answer 1

这个:

else if (IntCents < Nickel && IntCents >= Penny) {
    SubCoinCount = IntCents / Nickel;
    CoinCount += SubCoinCount;
    Remainder += IntCents % Dime;
    IntCents = Remainder;
}

应该是这样的:

else if (IntCents < Nickel && IntCents >= Penny) {
    SubCoinCount = IntCents / Penny;   // <--- Change to Penny, or just remove
    CoinCount += SubCoinCount;
    Remainder += IntCents % Penny;     // <--- Change to Penny
    IntCents = Remainder;
}

你的四个if除了硬币的面额外，外壳都是相同的，这意味着它们迫切需要被放入一个单独的功能中。这样做是避免在一个或某些情况下出现此类错误的好方法，因为您只编写一次。

我也怀疑:

Remainder += IntCents % Dime;

应该是:

Remainder = IntCents % Dime;

否则Remainder将无限增加，并且IntCents永远不会归零。 Remainder实际上就没有必要了，在这种情况下，你可以将结果直接赋值给 IntCents .

但是有一种更简单的方法可以完全做到这一点。以下是建议的替代方案，供您仔细阅读:

#include <stdio.h>

//  This cries out to be its own function

int coin_count(int cents, int denomination, int * remainder)
{
    *remainder = cents % denomination;
    return cents / denomination;
}

//  Better way

int CountGreed(int IntCents)
{
    static const int Quarter = 25, Dime = 10, Nickel = 5, Penny = 1;
    int CoinCount = 0;

    while ( IntCents > 0 ) {
        if ( IntCents >= Quarter ) {
            CoinCount += coin_count(IntCents, Quarter, &IntCents);
        } else if ( IntCents >= Dime ) {
            CoinCount += coin_count(IntCents, Dime, &IntCents);
        } else if ( IntCents >= Nickel ) {
            CoinCount += coin_count(IntCents, Nickel, &IntCents);
        } else if ( IntCents >= Penny ) {
            CoinCount += coin_count(IntCents, Penny, &IntCents);
        }
    }

    return CoinCount;
}

//  Even better way

int CountGreed2(int IntCents)
{
    static const int coins[4] = {25, 10, 5, 1};
    int CoinCount = 0;

    for ( int i = 0; i < 4; ++i ) {
        if ( IntCents >= coins[i] ) {
            CoinCount += coin_count(IntCents, coins[i], &IntCents);
        }
    }

    return CoinCount;
}

int main(void) {
    printf("Coins for $1.25 (should be 5): (%d)\n", CountGreed(125));
    printf("Coins for $1.00 (should be 4): (%d)\n", CountGreed(100));
    printf("Coins for $0.96 (should be 6): (%d)\n", CountGreed(96));

    printf("Coins for $1.25 (should be 5): (%d)\n", CountGreed2(125));
    printf("Coins for $1.00 (should be 4): (%d)\n", CountGreed2(100));
    printf("Coins for $0.96 (should be 6): (%d)\n", CountGreed2(96));

    return 0; 
}

输出:

paul@local:~/Documents/src/sandbox$ ./coins
Coins for $1.25 (should be 5): (5)
Coins for $1.00 (should be 4): (4)
Coins for $0.96 (should be 6): (6)
Coins for $1.25 (should be 5): (5)
Coins for $1.00 (should be 4): (4)
Coins for $0.96 (should be 6): (6)
paul@local:~/Documents/src/sandbox$ 

CountGreed2() 中需要一个单独的函数不太明显，因为无论如何你只写一次，但口味不同。