0

是的，我知道有与此类似的帖子，但是在浏览完所有帖子后，我仍然被困住，因为我对编程很陌生，而且给出的答案都不足以针对我的问题提供帮助。

问题。编写一个有效的 ACL（算法计算机语言）算法，给定一件物品的成本（小于或等于 1 美元），给出购买者想要的 50 美分、20 美分、10 美分、5 美分和 1 美分硬币的数量如果他们交出一美元，就会收到。您必须尽量减少找零中的硬币数量。

该问题与任何特定的编程语言无关，答案只能使用简单的 ACL 语言，如 if、if-else、while 循环，不能使用数组或其他高级命令。

这是我所在的位置：

在此处输入代码算法最小更改量

{
    int cost, fifty, twenty, ten, five, one;

    fifty = 0;
    twenty = 0;
    ten = 0;
    five = 0;
    one = 0;

    read (cost);
    if (cost <= 50)
    {
        fifty = 1;

代码完成，感谢您的帮助！如果您发现任何歧义或可以帮助我简化代码，请告诉我。

Algorithm how much change
{
    int cost, change, fifty, twenty, ten, five, one;

    fifty = 0;
    twenty = 0;
    ten = 0;
    five = 0;
    one = 0;

    read (cost);
    change = 100 - cost;

    if (change >= 50)
    {
        fifty = fifty + 1;
        change = change - 50;
    }
    while (change >= 20)
    {
        twenty = twenty + 1;
        change = change - 20;
    }
    while (change >= 10)
    {
        ten = ten + 1;
        change = change - 10;
    }
    while (change >= 5)
    {
        five = five + 1;
        change = change - 5;
    }
    while (change >= 1)
    {
        one = one + 1;
        change = change - 1;
    }

    print(one, five, ten, twenty, fifty);
}
4

5 回答 5

2

实际上，cost >= 50 只需要检查一次，但这更通用（对于超过 1 美元的情况）

while (cost >= 50)
{
fifty++;
cost -= 50;
}
while (cost >= 20)
{
twenty++;
cost -=20;
}
...
于 2011-03-08T07:43:40.760 回答
2

对于您的特定更改金额，我相信一个简单的贪婪幼稚的“选择最大的直到我不能再”策略会起作用。

前任。：

  1. 在 50 的数量大于零钱之前，我可以挑选多少个 50？跟踪 50 的数量，从总数中减去该数量
  2. 重复20、10等。

然而，贪婪方法并不总是有效。对于“通用”解决方案，请参阅Coin Change - Algorithmist

于 2011-03-08T07:44:38.960 回答
1

由于这听起来像家庭作业，我不会马上给出答案，而是给你一个正确方向的提示。

假设你是你程序中的某个点。您还有一定的金额可以退还，比如说 80 美分。你将如何获得一枚你肯定必须归还的硬币？

于 2011-03-08T07:44:06.137 回答
1

提示：从最大的硬币开始，找出你可以使用的最大数量，然后转到第二大的硬币并重复。看起来他们用 20 个硬币而不是 25 个 lol 让你更轻松。

于 2011-03-08T07:45:42.513 回答
0

在此处输入图像描述

more detailed:

在此处输入图像描述

and even a brute force algorithm which is O(d M^d)

在此处输入图像描述
This is from 马克斯·阿列克谢耶夫, University of South Carolina cse。

于 2011-03-08T07:49:06.733 回答