Mercurial > repo
comparison interps/c-intercal/pit/change.doc @ 996:859f9b4339e6
<Gregor> tar xf egobot.tar.xz
| author | HackBot |
|---|---|
| date | Sun, 09 Dec 2012 19:30:08 +0000 |
| parents | |
| children |
comparison
equal
deleted
inserted
replaced
| 995:6883f5911eb7 | 996:859f9b4339e6 |
|---|---|
| 1 The problem is to determine how many different ways there are to make | |
| 2 change for a given amount using five denominations of US coins | |
| 3 (including the 50-cent piece). One version -- taken directly from | |
| 4 section 1.2.2 of Abelson and Sussman (1st edition, 1985) -- recurses | |
| 5 both towards lower amounts and fewer kinds of coins. The space | |
| 6 required by this tree recursion grows rapidly with the size of the | |
| 7 problem. The other version is a minor modification which makes the | |
| 8 long ``amount'' direction tail-recursive. The ``kinds'' direction is | |
| 9 still recursive, but with only five kinds of coins there need be only | |
| 10 five stack frames for the routine allocated at a time. | |
| 11 | |
| 12 In case it isn't obvious, the routine starting at (100) is the | |
| 13 function ``first-denomination'' (one of the few things INTERCAL can do | |
| 14 easily), the one at (200) is the recursive version ``cc'', and (300) | |
| 15 starts the tail-recursive routine ``cc-tail''. The first few lines are | |
| 16 the main program, which you can change to run the recursive version by | |
| 17 calling (200) instead of (300). The (2000) routine at the end | |
| 18 decrements .1, and I make calls to the addition and subtraction | |
| 19 routines in the standard library. | |
| 20 | |
| 21 Two stacks are involved: the variable stack accessed by STASH and | |
| 22 RETRIEVE, and the call stack accessed by NEXT and RESUME. The former | |
| 23 is limited only by memory, but the latter is supposed to have a | |
| 24 built-in limit of 80 pending returns. The tail-recursive routine has | |
| 25 no problem with this. However, in order to permit the recursive | |
| 26 routine (200) to run with amounts greater than 70, I had to remake the | |
| 27 INTERCAL compiler with a larger limit. | |
| 28 | |
| 29 | |
| 30 (To see this program compared with similar programs in other languages, | |
| 31 visit http://www.webcom.com/nazgul/change.html.) |