整数溢出贪婪的硬币计数

#include  #include  #include  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之类的int金额，其金额仅需要程序使用25美分硬币。

如果我尝试9.10或9.01之类的数量，我会收到运行时错误，有符号整数溢出。 我理解这意味着什么，但我不明白硬币的价值怎么会突然变得如此之高。

Answer 1

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

 #include  #include  #include  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); } 

Answer 2

似乎没有人回答这个问题

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

所以为了完整起见，部分作为练习：

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

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

在中断的时刻， amount约为120万，硬币差不多有500万。 这清楚地表明了你未能检查的一件事：消极性。 它可以很容易地发生，你错过了正确的零，因为其他人已经正确推理，没有必要重复。 但如果发生这种情况，你的程序应该担心当下amount变为负数。 否则，在正确的条件下，它也可以继续向负无穷大减去它的方式，是的，整数溢出将发生在coins 。

Answer 3

这是因为计算机以二进制表示小数（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。

Float，double每个人都有一个固定的位数来表示小数。 所以它只保留那些多少位，其总和略小于0.1

如果您想采用相同的方法，您可以有两种可能的解决方案： –

1. 使用（金额> 0）代替（金额！= 0） ，或
2. 使用能够以2的幂表示的货币，例如0.25,0.125,0.375,0.06125。

Answer 4

您的算法不正确：

例如，30美分你可以用你的算法交换到：25 + 5（2个硬币）它将是10 + 10 + 10（3个硬币）。 所以贪婪意味着为什么它超过25美分然后交换到25美分。

 while (amount != 0) { if (amount >= 0.25) { amount = amount - 0.25; coins += 1; } else if (amount >= 0.10) { amount = amount - 0.10; coins += 1; } else if (amount >= 0.05) { amount = amount - 0.05; coins += 1; } else { amount = amount - 0.01; coins += 1; } } 

如果你想这样做。

更好的方法：

 int coinTypes[] = {0.25, 0.1, 0.05, 0.01}; for (int i = 0; i < 4; i++) { coins += floor(amount / coinTypes[i]; amount -= coins * coinsTypes[i]; } 

Answer 5

您的算法的主要问题是fmod函数的无效使用。 根据定义， fmod(num, denom)是

 fmod = num - floor(num/denom) * denom 

floor(num/denom)是整数。 因此， fmod(9.10, 0.25) == 0.1 ， fmod(9.10, 0.10) == 0.1 。

此外，使用浮点数的操作很少给出精确的结果。 所以amount永远不会是0 。

Answer 6

您无法使用float类型计算此值。 不是0.25的精确倍数的数量无法在float或double类型中精确表示。

您可以通过计算精确的分数来解决这个问题，并使用整数算术分派它：

 #include  #include  void print_coins(int coins, const char *singular, const char *plural) { if (coins > 0) printf(" %d %s", coins, coins > 1 ? plural : singular); } int main(void) { for (;;) { double amount; int amountInt, coins, quarters, dimes, nickels, pennies; printf("Enter amount: "); if (scanf("%lf", &amount) != 1 || amount <= 0) break; amountInt = (int)(amount * 100.0 + 0.5); quarters = amountInt / 25; amountInt %= 25; dimes = amountInt / 10; amountInt %= 10; nickels = amountInt / 5; amountInt %= 5; pennies = amountInt; amountInt = 0; coins = quarters + dimes + nickels + pennies; printf("coins returned: %d:", coins); print_coins(quarters, "quarter", "quarters"); print_coins(dimes, "dime", "dimes"); print_coins(nickels, "nickel", "nickels"); print_coins(pennies, "penny", "pennies"); printf("\n"); } return 0; } 

笔记：

• 使用不带+ 0.5 float ，只需100.10 ：一分钱短。
• 使用float ， 1000000.10 ：3额外便士的更改不正确。
• 要处理超过2000万美元的金额，您需要一个更大的整数类型，例如long long int 。 有了这个，你可以处理超过美国国债的金额。