学习C，需要一些“Greedy”CS50解决方案的帮助

我是C的新手。我来自python背景。 我想知道我的代码出错了。

我正在做cs50贪心的问题。 我的代码出了什么问题？ 它适用于某些数字，但其他数字不起作用。 我试图从用户那里得到一个输入，询问要回馈多少更改，然后使用$ .25，$ .10，$ .05，$ .01计算我可以回馈的最小硬币数量。

#include  #include  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  #include  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

由于您没有包含测试用例，我自己做了。 以下是您的算法未返回正确答案的一些情况：

.04，.11，.17，.19，.21，.26，.32等

这些情况在计算便士的数量时都是失败的（在最后的do-while循环中），并且它们都返回少一枚硬币。 这是因为浮点数的错误。 使用print语句，我发现当计算最终便士的分配时，每次都会发生同样的事情：

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