PD4CS

Program:  Algorithms_5_coinchanging.py

#Algorithms and Computational Thinking
#Program for Example 5, coin changing
#
#define coin denominations
def defineDenoms():
    print("Enter denominations of the coins, one at a time, enter -l to end input ")
    denoms = []
    while True :
        value = int(raw_input("Enter next coin value: "))
        if value == -1:
            break
        denoms.append(value)

    return denoms

#find the least number of coins needed to represent the value amount
def changeCoins(denoms, amount):
    denoms.sort()
    denoms.reverse()
    output = []
    while (amount > 0):
        denomValue = denoms[0]
        if (amount >= denomValue):
            num = amount // denoms[0]
            amount = amount - (num * denoms[0])
            output.append([denoms[0], num])
        denoms.remove(denomValue)
    return output

my_denoms = defineDenoms()
my_amount = int(raw_input("Enter amount: "))
my_output = changeCoins(my_denoms, my_amount)

for i in range (len(my_output)):
    print my_output[i][0] , " x " , my_output[i][1]

# Questions:
# 1: If the coin set chosen does not contain 1 in the denomination, there may not be a solution
# what happens in the program if there is no solution?
# Answer: the code should test for whether or not a solution was found and
# print an appropriate message

# 2: what happens when the same coin denomination is input more than once?
# Answer: the output is still correct

Output

Enter denominations of the coins, one at a time, enter -l to end input 
Enter next coin value: 1
Enter next coin value: 2
Enter next coin value: 5
Enter next coin value: -1
Enter amount: 23
5  x  4
2  x  1
1  x  1