贪婪硬币计数中的整数溢出

Question

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

int main (void) { 

    printf ("Enter amount: ");
    float amount = GetFloat();
    int coins = 0;

    while (amount != 0) {

        if (fmod(amount, 0.25) == 0) {
            amount = amount - 0.25;
            coins += 1;
        }

        else if (fmod(amount, 0.10) == 0) {
            amount = amount - 0.10;
            coins += 1;
        }

        else if (fmod(amount, 0.05) == 0) {
            amount = amount - 0.05;
            coins += 1;
        }

        else {
            amount = amount - 0.01;
            coins += 1;
        }
    }

    printf ("Coins : %d\n", coins);
}

我正在尝试实现一个小的贪婪算法，在这个算法中，用户输入一定数量的钱（例如：9.25），我们输出的硬币数量最少，我们可以兑换（25美分、10美分、5美分和1美分）。

该算法适用于整数金额，如10或20，以及只需要程序使用25美分硬币的金额。

如果我尝试9.10或9.01这样的数值，就会得到一个运行时错误，即有符号整数溢出。我明白这意味着什么，但我不明白硬币的价值怎么会突然这么高。

Answer 1

这是因为计算机用二进制表示小数（2的幂）

对于0.25，计算机可以用二进制正确地表示它。这是因为我们可以精确地使用2的幂获得0.25。

但是，对于0.10（或提及的其他面额），它们不能精确表示为2的幂。

假设您尝试使用2的幂来获得0.1，您将无法准确地获得它。你可以走近它。

0.1 = 0.0625 ( 2^4 ) 0.03125 ( 2^5 ) 0.00390625 ( 2^-8) ...

你会接近0.1，但你永远不会准确地达到0.1。

浮点数，双数每个人都有一个固定的位数来表示小数。因此，它将只保留这些位，其总和将略小于0.1

如果你想遵循同样的方法，你可以有两种可能的解决方案：-

1. 使用（数量）

Answer 2

似乎没有人回答这个问题

如果我尝试像9.10或9.01这样的数量，我会得到一个运行时错误，有符号整数溢出，我理解它的意思，但我不明白硬币的价值怎么会突然变得这么高。

因此，为了完整性，部分作为练习：

您可以使用调试器找到原因。我复制了你的代码，发现它运行很长时间。在启动后中断它，显示代码冻结，重复此检查：

if (fmod(amount, 0.25) == 0) {
    amount = amount - 0.25;
    coins += 1;
}

在中断的那一刻金额约为-120万，硬币近500万。这清楚地表明了一件你没有检查的事情：消极性。浮点数很容易丢失精确的零，正如其他人正确推理的那样，无需重复。但是如果发生这种情况，您的程序应该在amount变为负值时感到担心。否则，在正确的条件下，它可能会继续向负无穷大方向减法，是的，硬币中会发生整数溢出。

Answer 3

正如Danial Tran所说，在执行逻辑操作时最好使用int。请阅读为什么不使用Double或Float来表示货币？也可以避免while循环。

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

int main (void) { 

    printf ("Enter amount: ");
    //float amount = GetFloat(); //Please refer to chqrlie's comments below.
    double amount  = 0.0;
    scanf("%lf",&amount); //I don't know GetFloat() equivalent for double. So using scanf().

    long long int amountInt = (long long int) (amount * 100.0);

    int coins = 0;

    if (25 <= amountInt) {
        coins += (amountInt/25);
        amountInt = amountInt % 25;
    }

    if (10 <= amountInt) {
        coins += (amountInt/10);
        amountInt = amountInt % 10;
    }

    if (5 <= amountInt) {
        coins += (amountInt/5);
        amountInt = amountInt % 5;
    }

    if (1 <= amountInt) {
        coins += amountInt;
    }

    printf ("Coins : %d\n", coins);
}