CHALLENGE PROBLEM
Author Message
CHALLENGE PROBLEM

Quote:

> Here's a quick challenge to those that are more experienced than I.

> Design a procedure that evolves an iterative process for solving a
> change counting problem. For example:

[chomp]
> Remember, the function must be iterative, not recursive.

any other homework from SICP you'd like us to do for you?

--

Network Engineer                 http://www.*-*-*.com/ ~black
Minnesota Regional Network                         OC-3 Or Bust

Sat, 18 Jul 1998 03:00:00 GMT
CHALLENGE PROBLEM

Here's a quick challenge to those that are more experienced than I.

Design a procedure that evolves an iterative process for solving a
change counting problem. For example:

(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).

ie. (count-change 4)   will return   1   becuase there is only one
way to make up four cents (by using four pennies)
(count-change 5)   will return   2
(count-change 10)  will return   4

etc...

Remember, the function must be iterative, not recursive.

Sat, 18 Jul 1998 03:00:00 GMT
CHALLENGE PROBLEM

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])

(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?

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.

Sun, 19 Jul 1998 03:00:00 GMT
CHALLENGE PROBLEM

Quote:

>> ...
>> Design a procedure that evolves an iterative process for solving a
>> change counting problem. For example:
>> ...

>any other homework from SICP you'd like us to do for you?

> ...

Really? For me it will always be Exercise 6.5, Scheme and the Art of
Programming.

Otherwise, ditto.

--

Ph.D. Candidate in Programming Languages
Indiana University Computer Science
<http://www.cs.indiana.edu/hyplan/jrossie.html>

Sun, 19 Jul 1998 03:00:00 GMT

 Page 1 of 1 [ 4 post ]

Relevant Pages