计算通过给定的零钱赚取金额的方法数量
我试图编写一个算法来计算使用给定面额赚取一定金额的不同可能方式的数量。 假设美元的面额为 $100、$50、$20、$10、$5、$1、$0.25、$0.10、$0.05 和 $0.01。下面的函数对于 int amount 和 int 面额非常有用，
/* Count number of ways of making different combination */
int Count_Num_Ways(double amt, int numDenom, double S[]){
cout << amt << endl; //getchar();
/* combination leads to the amount */
if(amt == 0.00)
return 1;
/* No combination can lead to negative sum*/
if(amt < 0.00)
return 0;
/* All denominations have been exhausted and we have not reached
the required sum */
if(numDenom < 0 && amt >= 0.00)
return 0;
/* either we pick this denomination, this causes a reduction of
picked denomination from the sum for further subproblem, or
we choose to not pick this denomination and
try a different denomination */
return Count_Num_Ways(amt, numDenom - 1, S) +
Count_Num_Ways(amt - S[numDenom], numDenom, S);
}
但是当我将逻辑从 int 更改为 float 时，它会进入无限循环。我怀疑这是因为代码中的浮点比较。我无法找出无限循环行为的确切原因。 在这方面的任何帮助都会有所帮助。
I was trying to code an algorithm to count the number of different possible ways the make a certain amount with the given denominations.
Assume the US dollar is available in denominations of $100, $50, $20, $10, $5, $1, $0.25, $0.10, $0.05 and $0.01. Below function, works great for int amount and int denominations
/* Count number of ways of making different combination */
int Count_Num_Ways(double amt, int numDenom, double S[]){
cout << amt << endl; //getchar();
/* combination leads to the amount */
if(amt == 0.00)
return 1;
/* No combination can lead to negative sum*/
if(amt < 0.00)
return 0;
/* All denominations have been exhausted and we have not reached
the required sum */
if(numDenom < 0 && amt >= 0.00)
return 0;
/* either we pick this denomination, this causes a reduction of
picked denomination from the sum for further subproblem, or
we choose to not pick this denomination and
try a different denomination */
return Count_Num_Ways(amt, numDenom - 1, S) +
Count_Num_Ways(amt - S[numDenom], numDenom, S);
}
but when I change my logic from int to float, it goes into infinite loop. I suspect that it is because of floating point comparisons in the code. I am not able to figure out the exact cause for a infinite loop behavior.
Any help in this regard would be helpful.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
当处理如此“小”的货币金额而不处理利息时，仅处理美分和整数金额而不使用浮点数会容易得多。
因此，只需更改公式以使用美分而不是美元，并继续使用整数即可。然后，当您需要显示金额时，只需将其除以 100 即可得到美元，再模 100 即可得到美分。
When dealing with such "small" currency amounts and not dealing with interest it will be much easier to just deal with cents and integer amounts only, not using floating point.
So just change your formula to use cents rather than dollars and keep using integers. Then when you need to display the amounts just divide them by 100 to get the dollars and modulo 100 to get the cents.
由于表示形式有限，浮点运算不可能精确。这样你就永远不会得到精确的 0.0。这就是为什么您总是像这样测试一个间隔：
使用给定的
TOL容差。TOL根据应用程序适当选择，在本例中，1/2 美分应该已经足够了。编辑：当然，对于这种事情，大民的回答更合适。
floating point operations cannot be exact, because of the finite representation. This way you will never ever end up with exactly 0.0. That's why you always test an interval like so:
with a given tolerance of
TOL.TOLis chosen appropriately for the application, in this case, 1/2 cent should already be fine.EDIT: Of course, for this kind of thing, Daemin's answer is much more suitable.