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

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.



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  
 
 [ 4 post ] 

 Relevant Pages 

1. Challenge Problem #2 of 17

2. Challenge problem

3. a gui challenge problem

4. explode - another guiFest challenge problem

5. Challenge problem - a simple spreadsheet

6. A solution to Challenge Problem 2

7. challenge problem: equivalence classes

8. Challenging problem

9. A challenging problem...

10. Challenging problem in prolog (find the transitive closure in a graph)

11. Challenge problem

12. Challenge problem

 

 
Powered by phpBB® Forum Software