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