贪心算法无法正常运行

Question

这段代码应该给我最少数量的硬币（25 美分硬币、5 美分硬币、5 美分硬币和 1 美分硬币），这些硬币加起来等于所欠的金额。当我输入的值是 0.25 的倍数时，它可以无缝工作。但是当我在终端中输入其他值时，它只是插入一个新行而不做任何事情。我怎么搞砸了？owed = float(input("how much change is owed?"))coins = 0if owed % 0.25 == 0:    coins = owed / 0.25    print(int(coins))    exit()elif owed % 0.25 != 0:    while owed > 0:        if (owed - 0.25) >= 0:            coins += 1            owed -= 0.25        elif (owed - 0.10) >= 0:            coins += 1            owed -= 0.10        elif (owed - 0.05) >= 0:            coins += 1            owed -= 0.05        elif (owed - 0.01) >= 0:            coins += 1            owed -= 0.01    print(int(coins))    exit()

Answer 1

while由于浮点数的内部表示引起的与浮点值相关的一些舍入错误，您的程序正在运行无限循环。因此，要修复这些错误，我们可以使用round()函数在每次循环迭代owed结束时对值进行四舍五入：while

elif owed % 0.25 != 0:

    while owed > 0:

        if (owed - 0.25) >= 0:

            coins += 1

            owed -= 0.25

        elif (owed - 0.10) >= 0:

            coins += 1

            owed -= 0.10

        elif (owed - 0.05) >= 0:

            coins += 1

            owed -= 0.05

        elif (owed - 0.01) >= 0:

            coins += 1

            owed -= 0.01

        owed = round(owed, 3) # In this line, we roundoff the value of owed

    print(int(coins))

    exit()

这很好用。

希望这可以帮助 ：）

Answer 2

while由于浮点错误，您的程序卡在循环中。尝试在while循环中添加以下代码，您会看到 whileowed确实变得无限小，它永远不会变为零：

...

while owed > 0:

    print(owed)

    ...

输出：

...

8.326672684688674e-17

8.326672684688674e-17

8.326672684688674e-17

8.326672684688674e-17

...

考虑将输入乘以100然后将其作为整数处理：

owed = int(float(input("How much change is owed? $")) * 100)

quarters = int(owed / 25)

dimes = int((owed - quarters * 25) / 10)

nickels = int((owed - quarters * 25 - dimes * 10) / 5)

cents = int((owed - quarters * 25 - dimes * 10 - nickels * 5))

coins = (quarters + dimes + nickels + cents)

print('Quarters (${}): {}'.format(quarters*0.25, quarters))

print('Dimes (${}): {}'.format(dimes*0.1, dimes))

print('Nickels (${}): {}'.format(nickels*0.05, nickels))

print('Cents (${}): {}'.format(cents, cents))

print('Coins:', coins)

或者，如果您想坚持使用贪心算法：

owed = int(float(input("How much change is owed? $")) * 100)

while owed > 0:

    if (owed - 25) >= 0:

        coins += 1

        owed -= 25

    elif (owed - 10) >= 0:

        coins += 1

        owed -= 10

    elif (owed - 5) >= 0:

        coins += 1

        owed -= 5

    elif (owed - 1) >= 0:

        coins += 1

        owed -= 1

coins = (quarters + dimes + nickels + cents)

print('Quarters (${}): {}'.format(quarters*0.25, quarters))

print('Dimes (${}): {}'.format(dimes*0.1, dimes))

print('Nickels (${}): {}'.format(nickels*0.05, nickels))

print('Cents (${}): {}'.format(cents, cents))

print('Coins:', coins)

输出

>>> How much change is owed? $1.42

Quarters ($1.25): 5

Dimes ($0.1): 1

Nickels ($0.05): 1

Cents ($2): 2

Coins: 9

有关浮点限制的更多信息，请查看以下内容：https ://docs.python.org/3.8/tutorial/floatingpoint.html