Quote:

>Design a procedure that evolves an iterative process for solving a

>change counting problem.

It is not clear to me what is meant by "evolves an iterative process".

Are we being asked for a genetic programming system that by simulated

evolution in a population of Scheme programs comes up with one that

solves change counting?

For example:

Quote:

>(count-change amount)

>should return a value that represents the different number of ways

>that the amount can be composed of 5 different coins (50 cent piece,

>a quarter, dime, nickel, and penny).

Why 5 coins? What happened to US$1 coins?

Why those values? Here the values are

([1, 2, withdrawn from circulation] 5, 10, 20, 50, 100, 200)

In my childhood the values were

(1/2, 1, 3, 6, 12, 24, 30 [, 60, 120, 240 existed but were very rare])

How about

(make-change-counter Denomination-List)

; Denomination-List is a non-empty list of strictly DECREASING

; positive numbers (decreasing makes it much easier)

; The result is a function for counting the number of ways of

; making change, e.g.

; ((make-change-counter '(1 2 5 10 20 50)) 5) ==> 4

What I'm really suggesting here is that life will be simpler if you do

not rely on any specific arithmetic properties of the coins you happen

to be concerned with the moment.

Quote:

>Remember, the function must be iterative, not recursive.

Why?

In any case, the single most important thing to understand about this

homework assignment is that it has nothing to do with Scheme. The hard

part is not expressing the result in Scheme, but achieving a mathematical

understanding of the problem.

For example,

if there are no coins, there are no ways to make Amount.

if the largest coin is L and the remaining coins are R,

the number of ways to make change for R is

sum for i from 1 to Amount div L inclusive of

the number of ways to make Amount-i*L using R

This should suggest a particular iterative loop structure to you.

--

"conventional orthography is ... a near optimal system for the

lexical representation of English words." Chomsky & Halle, S.P.E.

Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.