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.

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

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.