| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
The book "Struture and Interpretation of Computer Programs", by
Abelson and Sussman (MIT Press 1985) gives a recursive solution
to the change-counting problem. Does anybody have an iterative
solution?
The problem is stated as follows:
It only takes a bit of cleverness to come up with an iterative
Fibonacci algorithm. In contrast, consider the following problem:
How many different ways can we make change of $1.00, given half
dollars, quarters, dimes, nickels, and pennies? More generally,
can we write a procedure to compute the number of ways to change
any given amount of money?
This problem has a simple solution as a recursive procedure. Suppose
we think of the types of coins available as arranged in some order.
Then the following relation holds:
Number of ways to change amount A using N kinds of coins =
Number of ways to change amount A using all but the first kind of
coin
+
Number of ways to change amount (A - D) using all N kinds of coins,
where D is the denomination of the first kind of coin.
To see why this is true, observe that the ways to make change can
divided into two groups: those that do not use the first kind of
coin, and those that do.....
.
.(more explanation and a Scheme language implementation of the
. recursive procedure)
.
Count-change generates a tree-recursive process with redundancies
similar to those in our first implementation of Fib (it will take
quite a while for that 292 to be computed [292 ways to count change
of $1.00]) ON the other hand, it is not so obvious how to design
a better algorithm for computing the result, and we leave this problem
as a challenge.
- Rick
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 440.1 | ideas, anyone? | CLT::GILBERT | Juggler of Noterdom | Tue May 13 1986 21:38 | 0 |
| 440.2 | LATOUR::JMUNZER | Mon May 19 1986 17:08 | 50 | ||
A diagramatic method (inspired by note 271) for counting the ways to
change various amounts of money follows. Some rows are selected from
higher rows, some rows are sums:
x y ...
z x+z x+z+y ...
** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
Total cents:
0-4 10-14 20-24 30-34 40-44 50-54 60-64 70-74 80-84 90-94 100-104
5-9 15-19 25-29 35-39 45-49 55-59 65-69 75-79 85-89 95-99
Combinations of nickels & pennies:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
2 6 12 20 30 42 56 72 90 110
1 4 9 16 25 36 49 64 81 100 121
Combinations of dimes & nickels & pennies:
1 2 4 6 9 12 16 20 25 30 36 42 49 56 64 72 81 90 100 110 121
9 39 103 213
6 31 87 187
4 24 73 163
2 18 60 141
1 13 49 121 242
Combinations of quarters & dimes & nickels & pennies:
1 2 4 6 9 13 18 24 31 39 49 60 73 87 103 121 141 163 187 213 242
39 252
31 218
24 187
18 159
13 134
9 112
6 93
4 77
2 62
1 50 292
Combinations of halves & quarters & dimes & nickels & pennies:
1 2 4 6 9 13 18 24 31 39 50 62 77 93 112 134 159 187 218 252 292
** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
The recursion of .0 is still evident, however.
John
| |||||
| 440.3 | CLT::GILBERT | Juggler of Noterdom | Mon May 19 1986 18:44 | 18 | |
Let P(n,s) be the number of ways to produce change for the amount n,
using coins with values in set s. For example,
P(n,{1}) = 1 (only one way if you only have pennies)
P(n,{1,5}) = [n/5]+1 (use between 0 and [n/5] nickels)
P(n,{1,k}) = [n/k]+1 (in general, for k > 1)
[n/5]
P(n,{1,5}) = Sum 1
i=0
[n/5] [i/2]
P(n,{1,5,10}) = Sum Sum 1
i=0 j=0
Using some magic, this is:
P(n,{1,5,10}) = ( [n/10]+1 )( [n/10]-[n/5]+1 )
| |||||
| 440.4 | How's it work? | CSC32::S_JOHNSON | Lifetime Member of Aye Phelta Thi | Mon Oct 01 1990 12:51 | 16 |
Total cents:
0-4 10-14 20-24 30-34 40-44 50-54 60-64 70-74 80-84 90-94 100-104
5-9 15-19 25-29 35-39 45-49 55-59 65-69 75-79 85-89 95-99
Combinations of nickels & pennies:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
2 6 12 20 30 42 56 72 90 110
1 4 9 16 25 36 49 64 81 100 121
Can someone explain how this table works? I understand how the values
were calculated, but I don't know see how the table would work to give
me the different combinations of coins for $.23?
scott
| |||||
| 440.5 | re .4 | ESCROW::MUNZER | Wed Oct 03 1990 12:29 | 11 | |
Total cents: 0-4 5-9 10-14 15-19 20-24 Combinations of 1�: 1 1 1 1 1 Summing: [start=0] 0+1 1+1 2+1 3+1 4+1 Combinations of 1�, 5�: 1 2 3 4 5 Summing: [start=0] 0+1 1+2 2+3 3+4 4+5 Combinations of 1�, 5�, 10�: 1 3 5 7 9 There are nine combinations -- DDPPP through P^23. John | |||||
| 440.6 | P^6 & N.P^1 & ??? | TRACE::GILBERT | Ownership Obligates | Thu Oct 04 1990 11:52 | 5 |
>Total cents: 0-4 5-9 10-14 15-19 20-24 >Combinations of 1�, 5�, 10�: 1 3 5 7 9 So there are 3 ways to make change for 6�? But 9 was the right answer for 23�! | |||||
| 440.7 | re .4,.5,.6 | ESCROW::MUNZER | Thu Oct 04 1990 12:42 | 17 | |
Sorry, I forgot that each coin added a table, not a line. I had to refer to 271.* and try to remember 1985 to get it right. Total cents: 0-4 5-9 10-14 15-19 20-24 25-29 Combinations of 1�: 1 1 1 1 1 1 Summing: [start=0] 0+1=1 1+1=2 2+1=3 3+1=4 4+1=5 5+1=6 Combinations of 1�, 5�: 1 2 3 4 5 6 Summing: [start=0] 0+2=2 2+4=6 6+6=12 Summing: [start=0] 0+1=1 1+3=4 4+5=9 Combinations of 1�, 5�, 10�: 1 2 4 6 9 12 John | |||||