29 lines
1 KiB
Text
29 lines
1 KiB
Text
There are four types of common coins in [https://en.wikipedia.org/wiki/United_States US] currency:
|
|
:::# quarters (25 cents)
|
|
:::# dimes (10 cents)
|
|
:::# nickels (5 cents), and
|
|
:::# pennies (1 cent)
|
|
|
|
|
|
There are six ways to make change for 15 cents:
|
|
:::# A dime and a nickel
|
|
:::# A dime and 5 pennies
|
|
:::# 3 nickels
|
|
:::# 2 nickels and 5 pennies
|
|
:::# A nickel and 10 pennies
|
|
:::# 15 pennies
|
|
<br>
|
|
|
|
;Task:
|
|
How many ways are there to make change for a dollar using these common coins? (1 dollar = 100 cents).
|
|
|
|
|
|
;Optional:
|
|
Less common are dollar coins (100 cents); and very rare are half dollars (50 cents). With the addition of these two coins, how many ways are there to make change for $1000?
|
|
|
|
(Note: the answer is larger than 2<sup>32</sup>).
|
|
|
|
|
|
;Reference:
|
|
* [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_Temp_52 an algorithm from MIT Press].
|
|
<br><br>
|