## Program: Algorithms_5_coinchanging.py

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