Жадный алгоритм не работает должным образом - PullRequest
Новая
       2

Жадный алгоритм не работает должным образом

1 голос
/ 21 апреля 2020

Предполагается, что этот код даст мне наименьшее количество монет (четверти, десять центов, никелей и пенни), которые составляют сумму, причитающуюся. когда я ввожу значения, кратные 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()

Ответы [ 2 ]

1 голос
/ 21 апреля 2020

Ваша программа работает бесконечно while l oop из-за некоторых ошибок округления, связанных со значениями с плавающей запятой, вызванных внутренним представлением чисел с плавающей запятой. Таким образом, чтобы исправить эти ошибки, мы можем использовать функцию round() для округления значения owed в конце каждой while l oop итерации: 

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()

, и это прекрасно работает.

Надеюсь, это поможет:)

1 голос
/ 21 апреля 2020

Ваша программа застряла в while l oop из-за ошибок с плавающей запятой. Попробуйте добавить следующий код прямо внутри while l oop, и вы увидите, что, хотя owed становится бесконечно малым, оно никогда не становится равным нулю: 

...
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

...