SICP- no. of ways to make change of $1by iterative algorithm

general
, ,
1

The following is an excerpt from Structure and Interpretation of Computer Programs:
How many different ways can we make change of 1, given coins of 0.5 ,0.25$,0.10$,0.05$,0.01$?
The book has the solution using a recursive algorithm … but asks to come up with an iterative algorithm for the same.
I have been unable to think iteratively. Please help me with the algorithm.
Thank you.

2

The solution is the no of integral solution of equation 50a+25b+10c+5d+e=100 .which is similar to problem
http://www.codechef.com/INVS2013/problems/CDZ1304 and iteratively increase value of a then b then c then d till the sum exceeds 100 for e the remaining money is the no. of ways. Look at iterative solution to the problem http://www.codechef.com/viewsolution/1952871

1 Like
3

@sparshgunner12 ,I would be grateful if you could explain the process in little greater detail.

4

first initialize a=0;b=0;c=0;d=0;e=100 is first solution
then a=0;b=0;c=0;d=1;e=95 is second solution
.
.
.
.
then a=0;b=0;c=0;d=20;e=0 is 20th solution
now increment c by one as d cannot be greater than 20
then find upto c=10
then increment b by one

pseudocode
for(a=0;(100-50a)>=0;a++)
for(b=0;(100-50a-25b)>=0;b++)
for(c=0;(100-50a-25b-10c)>=0;c++)
for(d=0;(100-50a-25b-10c-5d)>=0;d++)
sol++
Note:This is a brute force method other better solutions are possible.

1 Like