C中的贪婪算法(含硬币)
C中的贪婪算法(含硬币)
提问于 2016-09-01 14:21:47
在我的代码中，我使用贪婪的算法来使用最小的硬币。例如:我必须退还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);
}此代码计算用于返回和的每种类型的硬币的数量。在大多数情况下，它可以正常工作。
但有时，例如，当我输入数字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我认为，问题是在最后的如果声明。但我不知道该怎么纠正。
回答 2
Stack Overflow用户
回答已采纳
发布于 2016-09-01 14:29:01
据我理解，在最严格的意义上，您的代码中没有错误，因为实现所基于的推理(贪婪的算法)是正确的。由于重复减法，您很可能会遇到舍入错误，因为您使用float来表示您的值。也许，如果您在代码中将float更改为double，则示例输入的输出将与预期的一样。
然而，这只会突破限制的界限。也许最好在内部代表以便士为单位的int金额。
请注意，当第一次面对浮点表示是不准确的事实时，我认为不可能表示一些值和累加舍入误差是一个问题，只有当你绝对做一些火箭科学计算，但永远不会与我认为是外行的计算。然而，情况并非如此。
Stack Overflow用户
发布于 2016-09-01 14:30:31
按照其他人的说法，这可能会完成以下工作:用下面的代码替换现有代码中的变量声明。计算循环不需要更改，因为您明智地使用了命名的数量，而不是硬编码的常量。
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的情况。如果没有，我建议查看调试器告诉您的内容。如果你在那之后仍然被困住了，请用最新更新的代码和测试用例发布另一个问题。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/39274114
复制相关文章
相似问题
腾讯云开发者
