学习 C，需要 "Greedy" CS50 解决方案的帮助

Question

我是 C 的新手。我来自 python 背景。我想知道我的代码哪里出了问题。

我在做cs50的贪心题。我的代码有什么问题？它适用于某些数字，但其他数字不起作用。我试图从用户那里得到一个输入，询问要返还多少零钱，然后计算我可以仅使用 $.25、$.10、$.05、$.01[=13= 返还的最少硬币数量]

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


int main(void)
{
    float n;
    do
    {
        n = get_float("How much change is owed?\n");
    }
    while(n == EOF); 
    int minimumamountofcoins = 0;
    if (n/.25 >=1){
        do 
        {
            n -= .25;
            minimumamountofcoins++;
        }
        while (n/.25 >= 1);
    }
    if (n/.1 >=1){
        do
        {
            n -= .1;
            minimumamountofcoins++;
        }
        while (n/.1 >=1);
    }
    if(n/.05 >=1){
        do
        {
            n -= .05;
            minimumamountofcoins++;
        }
        while (n/.05 >=1);
    }
    if (n/.01 >=1){
        do
        {
            n -= .01;
            minimumamountofcoins++;
        }
        while (n/.01 >=1);
    }
    printf("The minimum amount of coins is %d\n", minimumamountofcoins);
}

新代码：（除了输入 4.2 外都完美运行）

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


int main(void)
{
    float n;
    do
    {
        n = get_float("How much change is owed?\n");
    }
    while(n == EOF);

    int cents = (int)(n * 100);
    int minimumamountofcoins = 0;
    if (cents/25 >= 1){
        while (cents/25 >= 1)
        {
            cents -= 25;
            minimumamountofcoins++;
        }

    }
    if (cents/10 >= 1){
        while (cents/10 >= 1)
        {
            cents -= 10;
            minimumamountofcoins++;
        }
    }
    if(cents/5 >= 1){
        while (cents/5 >= 1)
        {
            cents -= 5;
            minimumamountofcoins++;
        }
    }
    if (cents/1 >= 1){
        while (cents/1 >= 1)
        {
            cents -= 1;
            minimumamountofcoins++;
        }
    }
    printf("The minimum amount of coins is %d\n", minimumamountofcoins);
}

Answer 1

因为你没有包含测试用例，所以我自己做了。以下是您的算法无法 return 正确答案的一些情况：

.04, .11, .17, .19, .21, .26, .32, etc.

这些情况在计算硬币数量时都失败了（在最后的 do-while 循环中），并且它们都 return 比他们应该少一枚硬币。这是因为浮点数错误。通过打印语句，我发现在计算最后一分钱的除法时，每次都会发生同样的事情：

n/.01 = 0.99999999

这显然不是故意的，因为这应该等于 1，最后一分钱应该加到总数上。因此，您的代码在理论上可行，但由于浮点数而被破坏。

为避免这种情况，您可以做任何事情，例如将美元和美分分别作为整数跟踪，将条件更改为 n/.01 >= .9999 而不是 n/.01 >= 1，处理金额您正在计算的钱的整数美分，或任何其他数量的东西。

就我个人而言，我更喜欢最后一个选项，将金额视为美分的整数。这很容易做到，因为从美元转换为美分所需要做的就是乘以 100。因此，最简单的做法是使用相同的算法，除了使用整数。

因此，代码看起来像这样：

int main(){
    float n;
    //code that parses in the amount of money, n now stores that amount
    int cents = (int)(n * 100);
    int minimumamountofcoins = 0;
    if (cents/25 >= 1){
        while (cents/25 >= 1)
        {
            cents -= 25;
            minimumamountofcoins++;
        }

    }
    if (cents/10 >= 1){
        while (cents/10 >= 1)
        {
            cents -= 10;
            minimumamountofcoins++;
        }
    }
    if(cents/5 >= 1){
        while (cents/5 >= 1)
        {
            cents -= 5;
            minimumamountofcoins++;
        }
    }
    if (cents/1 >= 1){
        while (cents/1 >= 1)
        {
            cents -= 1;
            minimumamountofcoins++;
        }
    }
    printf("The minimum amount of coins is %d\n", minimumamountofcoins);
}

学习 C，需要 "Greedy" CS50 解决方案的帮助

Learning C, need some assistance with "Greedy" CS50 solution

c

cs50