Apr 262008

Noah Gift over on O’Reilly OnLamp Blog has an article on building a greedy coin changer. That is, given a value, say 71 cents, calculate the fewest coins needed to make the amount. He had listed a number of solutions, but I felt I could do it a bit more pythonic. 😉

#!/usr/bin/env python
"""implement a greedy coin changer, returning the
fewest coins to make the change requested."""
#coin_list can be expanded to include silver dollars 
# and 50 cent pieces by just expanding the coin list
# to [100,50,25,10,5,1] the reulting answer 
#structure will modify itself to reflect 

coin_list = [25,10,5,1]
change_requested = .71
remaining = change_requested * 100 
change_returned = []    #result structure

for coin in coin_list:
    num_coins,remaining =  divmod(remaining,coin)
print change_returned
print remaining

The benefits of this version, are no conditional logic is needed, the coin structure can be modified and the answer will modify itself accordingly.

Sorry, the comment form is closed at this time.