C - 我的贪心算法不工作 CS50x

Question

我正在做 cs50x，运行在我的工作中遇到了麻烦。我应该创建一个算法来输出最少数量的硬币来找回零钱。例如 0.41 美元将是 4 个硬币、四分之一 (0.25)、两角硬币 (0.10) 和一美分 (0.01)。由于某种原因，这个算法不起作用（它投入了不正确数量的硬币），我无法计算为什么：

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

int Coins;
float Owed;

int main(void)
{
    printf("How much is owed?\n");
    Owed = GetFloat();
    while (Owed < 0)
    {
        printf("A positive number please");
        Owed = GetFloat();
    }
    if (Owed >= 0.25)
    {
        while (Owed >=0.25)
        {
            Owed = Owed - 0.25;
            Coins++;
        }
    }

     if (Owed >= 0.1)
    {
        while (Owed >=0.1)
        {
            Owed = Owed - 0.1;
            Coins++;
        }

    }

       if (Owed >= 0.05)
    {
        while (Owed >=0.05)
        {
            Owed = Owed - 0.05;
            Coins++;
        }

    }

       if (Owed >= 0.01)
    {
        while (Owed >= 0.01)
        {
            Owed = Owed - 0.01;
            Coins++;
        }

    }
    printf("%d",Coins);
}

当我运行代码并使用 0.41 作为欠款时，我得到了 3 个硬币，而答案应该是 4:

GreedyNotWorkTerminalPage

Answer 1

当您使用float时，您需要注意在这种操作中可能会失去准确性。看看这个：Floating point inaccuracy examples

我建议您使用美分，而不是使用 int。

Coliru example

Answer 2

您使用的数字 (0.1, 0.05, 0.01) 没有精确表示为浮点数，就像 2/3 没有精确表示为 4 位小数一样。 C 将使用最接近的浮点值，因此错误非常小，但这足以使您的比较意外失败。

想象一下，如果浮点数是 4 位小数，而您有 2/3 美元硬币：

从欠款开始 = 2.0000
Owed >= 0.6667，所以Owed-=0.6667。现在欠款 = 1.3333
1.3333 >= 0.6667，所以欠-=0.6667。现在欠款 = 0.6666
糟糕！欠款 = 0.6666，但这不是 >= 0.6667

您可以通过更改比较以允许小的舍入误差来解决此问题。不要说 >=0.25、>=0.1 和 >=0.01，而是使用 >=0.245、>=0.095 和 >=0.005

不过，通常情况下，最好使用可以准确表示您要使用的值的类型。使用 int 美分，而不是 float 美元。

C - 我的贪心算法不工作 CS50x

C - My greedy algorithm is not working CS50x

c

algorithm

cs50