贪心算法无法正常运行

Question

这段代码应该给我最少数量的硬币（25 美分硬币、5 美分硬币、5 美分硬币和 1 美分硬币），这些硬币加起来等于所欠的金额。当我输入的值是 0.25 的倍数时，它可以无缝工作。但是当我在终端中输入其他值时，它只是插入一个新行而不做任何事情。我怎么搞砸了？

owed = float(input("how much change is owed?"))

coins = 0

if 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结束时对值进行四舍五入：whileelif 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-178.326672684688674e-178.326672684688674e-178.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 -= 1coins = (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.42Quarters ($1.25): 5Dimes ($0.1): 1Nickels ($0.05): 1Cents ($2): 2Coins: 9有关浮点限制的更多信息，请查看以下内容：https ://docs.python.org/3.8/tutorial/floatingpoint.html