C中的贪婪算法（带硬币）

Question

在我的代码中，我使用贪心算法来使用最少数量的硬币。例如：我必须return$0.41，我可以使用的最低硬币数量是4:

1 - 0,25;
1 - 0.10;
1 - 0.05;
1 - 0.01;

硬币有4种：0.25,0.10,0.05,0.01。

这是我的代码：

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

int main(void)
{
    printf("Enter the sum, that you want to return you:");
    float sum = GetFloat();
    float quaters = 0.25;
    float dime = 0.10;
    float nickel = 0.05;
    float penny = 0.01;
    int count_q = 0,count_d = 0,count_n = 0,count_p = 0;


    while(sum<0){
        printf("Incorrect, enter the positive float number");
        sum = GetFloat();
    }

    while(sum > 0){
        if(sum - quaters >=0){
            sum -=quaters;
            count_q +=1;
        }
        else if((sum -quaters <0) && (sum -dime>=0)){
            sum -= dime;
            count_d +=1;
        }
        else if((sum - dime <0) &&(sum - nickel>=0) ){
            sum -= nickel;
            count_n +=1;
        }
        else if(sum - nickel <0){
            sum -= penny;
            count_p +=1;
        }
    }
    printf("The number of quaters: %i\n",count_q);
    printf("The number of dimes: %i\n",count_d);
    printf("The number of nickels: %i\n",count_n);
    printf("The number of pennies: %i\n",count_p);
}

此代码计算每种类型的硬币数量用于 return 总和。在大多数情况下它工作正常。

但有时，例如，当我输入数字 1.12 时，它会给出错误的结果：

Enter the sum, that you want to return you:1.12
The number of quaters: 4
The number of dimes: 1
The number of nickels: 0
The number of pennies: 3

我认为，问题出在最后的 else if 语句中。但是不知道怎么修改。

Answer 1

据我了解，从最严格的意义上说，您的代码中没有 bug，因为实现所依据的推理（贪心算法）是正确的。由于重复减法，您很可能遇到舍入错误，因为您使用 float，单精度浮点类型来表示您的值。也许，如果您在代码中将 float 更改为 double，则输出将与示例输入的预期一致。

然而，这只是突破了限制的界限。或许在内部将以便士为单位的金额表示为 int.

会更好

请注意，当第一次面对浮点表示不准确的事实时，我认为只有当您绝对进行一些火箭科学计算时，无法表示某些值和舍入误差的累积才会成为问题，但是永远不会 与我认为是外行的计算相关。然而，事实并非如此。

Answer 2

按照其他人的说法，这可能会完成工作：用下面的代码替换现有代码中的变量声明。计算循环不需要更改，因为您明智地使用了命名量而不是硬编码常量。

float dollars = GetFloat();
int sum = (int)(dollars*100.0 + 0.5);
int quaters = 25;
int dime = 10;
int nickel = 5;
int penny = 1;

编辑：

上述更改必须在输入发生的任何地方进行。例如：

while(dollars<0){                      /***/
    printf("Incorrect, enter the positive float number");
    dollars = GetFloat();              /***/
    sum = (int)(dollars*100.0 + 0.5);  /***/
}
printf("%d pennies\n", sum);           /* For debugging */

我将 +0.5 添加到最近舍入而不是截断 - 这可能会修复 1.13 和 1.14 的情况。如果没有，我建议您查看调试器告诉您的内容。如果在那之后您仍然遇到困难，请务必 post 另一个关于您最新的、更新的代码和测试用例的问题。

C中的贪婪算法（带硬币）

greedy algorithm (with coins) in C

c

if-statement

greedy

cs50