Greedy algorithm Python - code hitting infinite loop

Question

I am trying to write a greedy algorithm in python 3.

The premise is to take change, owed by user, as input and them give them as few coins as possible.

Available coins are: Quarters (0.25); Dimes(0.1); Nickels (0.05); and Pennies (0.01).

My code currently ends up in an infinite loop and i don't know what i am doing wrong.

Can anyone see where i am going wrong with the following code?

Code:

validacion = False
pennies = 0.01
nickels = 0.05
dimes = 0.1
quarters = 0.25
coinCounter = 0
penniesCounter = 0
nickelsCounter = 0
dimesCounters = 0
quartersCounter = 0 
cambio = False

while validacion is False:
    changeOwed = float(input("Change owed: "))
    if changeOwed > 0:
        validacion = True
    else:
        validacion = False
while cambio is False:
    if changeOwed > dimes and changeOwed <= quarters:
        coinCounter += 1
        quartersCounter += 1
        changeOwed -= quarters
        if changeOwed == 0.0:
            cambio = True
    elif changeOwed > nickels and changeOwed <= dimes:
        coinCounter += 1
        nickelsCounter += 1
        changeOwed -= nickels
        if changeOwed == 0.0:
            cambio = True
    elif changeOwed > pennies and changeOwed <= nickels:
        coinCounter += 1
        dimesCounters += 1
        changeOwed -= dimes
        if changeOwed == 0.0:
            cambio = True
    else:
        coinCounter += 1
        penniesCounter += 1
        changeOwed -= pennies
        if changeOwed == 0.0:
            cambio = True

print(coinCounter)

No is not, this is a for a course than I am doing at my own pace, not sure why you bother to answer just to say that. — David Salas Boscan, Dec 21 '17 at 03:01
Questions about homework are perfectly okay as long as an effort is made and a description of the problem that is occuring is stated. — Sebastian Mendez, Dec 21 '17 at 03:01
You should read this for a start: [Why Are Floating Point Numbers Inaccurate?](https://stackoverflow.com/q/21895756/1679849) — r3mainer, Dec 21 '17 at 03:04
@squeamishossifrage is correct, this is your problem: as for a possible option to counteract this, see [`decimal`](https://docs.python.org/2/library/decimal.html) — Sebastian Mendez, Dec 21 '17 at 03:06

score 0 · Answer 1 · answered Dec 21 '17 at 03:09

0

Following squeamish ossifrage's advice, rephrase your assignments as:

    pennies = 1
    nickels = 5

and so on. Then test your code using integer cents, rather than IEEE-754 binary FP dollars.

answered Dec 21 '17 at 03:09

J_H

17,926
4
24
44

MultiSkill · Answer 2 · 2017-12-21T03:44:00.603

Let us say that you owe 0.46 in change. So you should give: 1 quarter, 2 dimes and a penny:

>>> 0.46 - 0.25 - 0.1 - 0.1 -0.01
8.673617379884035e-18

As you can see it is not 0. Computers deal in binary and not all decimal fractions translate well to binary. The short solution would be to multiply all by 100 and deal with integers:

>>> 46 - 25 - 10 - 10 -1
0

For the input you would multiply it like this:

changeOwed = int(round(changeOwed * 100)) # 0.58*100 == 57.99999999

The next problem are your conditions where you give out a quarter if you owe less than a quarter. It should be:

if changeOwed >= quarters:
    # the quarter process
elif changeOwed >= dimes:
    # the dime process
#etc...

Also instead of doing the while cambio == False, it would make more sense to do:

while changeOwed >= pennies: # the smallest coin you can give out

Good luck!

Greedy algorithm Python - code hitting infinite loop

2 Answers2