----------------------------------------------------------------------------------
@MSGID:
<ac9b82d1-53fe-4bcc-b1a2-165b0a31b7b4n@googlegroups.com> 59df17df
@REPLY:
<790b5095-79fe-4012-8fee-e2d1cb33f7a3n@googlegroups.com> fe64ddf5
@REPLYADDR Marcel Hendrix <mhx@iae.nl>
@REPLYTO 2:5075/128 Marcel Hendrix
@CHRS: CP866 2
@RFC: 1 0
@RFC-References:
<55f30e3c-a6fe-428c-a95f-02bacf08c1een@googlegroups.com> <dbfca034-8ca9-4a9b-b563-3fa9da176386n@googlegroups.com>
<51074ba9-ac74-49aa-8f12-28668d28171fn@googlegroups.com> <8f99b90f-7f00-4544-8fa6-d258ee6f4ef2n@googlegroups.com>
<84586256-f364-4dcd-9b34-ef354fcd834dn@googlegroups.com> <790b5095-79fe-4012-8fee-e2d1cb33f7a3n@googlegroups.com>
@RFC-Message-ID:
<ac9b82d1-53fe-4bcc-b1a2-165b0a31b7b4n@googlegroups.com>
@TZUTC: -0700
@PID: G2/1.0
@TID: FIDOGATE-5.12-ge4e8b94
DOC
(*
http://www.webcom.com/nazgul/change.html#gcc
For the curious, here are the results computed for various
amounts, using coins in
denominations 1, 5, 10, 25 and 50. The ``answer`` column shows
the number of ways
found to make change for the given amount, the ``leaves`` column
shows the number
of leaf nodes in the tree recursion, and the ``calls`` column
shows the total number
of times the recursive procedure was called.
(amount=)
nanswer leaves calls
---------------------------------------------
50 50 786 1571
100 292 7750 15499
150 972 35888 71775
200 2435 114795 229589
250 5126 293666 587331
300 9590 646296 1292591
350 16472 1276080 2552159
400 26517 2321013 4642025
450 40570 3958690 7917379
500 59576 6411306 12822611
550 84580 9950656 19901311
600116727 14903135 29806269
650157262 21654738 43309475
700207530 30656060 61312119
750268976 42427296 84854591
800343145 57563241115126481
850431682 76738290153476579
900536332100711438201422875
950658940130331280260662559
All timings (argument = 200) are in seconds on a 75 MHz Pentium
running Linux 1.2.13
with libc 5.0.9, except that CMUCL needed Linux 2.0.25 and libc
5.2.18, and MSW Logo
was run under Windows 95.
gccGnu C 0.05
p2cP2C Pascal Translator 0.05
a60Algol 60 to C Translator 0.08
cmuclCMU Common Lisp 0.09
gclGnu Common Lisp 0.09
schemeMIT Scheme 0.15
swnMIT Scheme without Numerics 1.17
scheme48Scheme 48 3.65
p4P4 Pascal P-code Interpreter 7.31
postscriptGhostscript 8.52
emacsEmacs Lisp 12.27
awkGnu Awk 15.34
orthOrthogonal 32.48
texTeX 46.49
a60Algol 60 Interpreter 69.69
intercalINTERCAL 75.60
ucblogoUCB Logo 214.00
mswlogoMSW Logo 221.00
logopascalPascal in Logo 1049.00
walkLisp in Awk 43000.00
*)
ENDDOC
ANEW -count_change
#1500 =: MAXSIZE
CREATE _cc1 1 , HERE MAXSIZE CELLS ALLOT MAXSIZE CELLS ERASE
CREATE _cc2 2 , HERE MAXSIZE CELLS ALLOT MAXSIZE CELLS ERASE
CREATE _cc3 3 , HERE MAXSIZE CELLS ALLOT MAXSIZE CELLS ERASE
CREATE _cc4 4 , HERE MAXSIZE CELLS ALLOT MAXSIZE CELLS ERASE
CREATE _cc5 5 , HERE MAXSIZE CELLS ALLOT MAXSIZE CELLS ERASE
CREATE _ccx 0 , _cc1 , _cc2 , _cc3 , _cc4 , _cc5 ,
: `cc _ccx []CELL @ []CELL ; ( amount kinds_of_coins -- addr )
CREATE KOC 0 , 1 , 5 , #10 , #25 , #50 ,
: first_denomination KOC []CELL @ ; ( kinds_of_coins -- n )
\\ The order of recursive calls is important!
\\ Stack overflow will follow if they are interchanged.
: cc ( amount kinds_of_coins -- n )
OVER 0= IF 2DROP 1 EXIT ENDIF
OVER 0< IF 2DROP 0 EXIT ENDIF
DUP 0= IF 2DROP 0 EXIT ENDIF
2DUP `cc DUP @ ?DUP IF >R 3DROP R> EXIT ENDIF
>R
2DUP DUP >R first_denomination - R> RECURSE >R
1- RECURSE
R> +
DUP R> ! ;
: count_change ( amount -- u )
DUP MAXSIZE >= ABORT" out of range"
CR TIMER-RESET
5 cc . .ELAPSED ;
: count_changes ( -- )
#1550 #50 DO CR I 5 .R TIMER-RESET
I 5 cc 9 .R 2 SPACES .ELAPSED
#50 +LOOP ;
CR .( Try: count_changes)
DOC
(*
\\ P54C-166 iForth 1.11e
FORTH> count_changes
50 50 0.000 seconds elapsed.
100 292 0.000 seconds elapsed.
150 972 0.001 seconds elapsed.
200 2435 0.000 seconds elapsed.
250 5126 0.000 seconds elapsed.
300 9590 0.001 seconds elapsed.
350 16472 0.000 seconds elapsed.
400 26517 0.000 seconds elapsed.
450 40570 0.001 seconds elapsed.
500 59576 0.000 seconds elapsed.
550 84580 0.000 seconds elapsed.
600 116727 0.001 seconds elapsed.
650 157262 0.000 seconds elapsed.
700 207530 0.000 seconds elapsed.
750 268976 0.001 seconds elapsed.
800 343145 0.001 seconds elapsed.
850 431682 0.000 seconds elapsed.
900 536332 0.001 seconds elapsed.
950 658940 0.000 seconds elapsed.
1000 801451 0.000 seconds elapsed.
1050 965910 0.001 seconds elapsed.
1100 1154462 0.001 seconds elapsed.
1150 1369352 0.000 seconds elapsed.
1200 1612925 0.001 seconds elapsed.
1250 1887626 0.001 seconds elapsed.
1300 2196000 0.000 seconds elapsed.
1350 2540692 0.000 seconds elapsed.
1400 2924447 0.001 seconds elapsed.
1450 3350110 0.001 seconds elapsed.
1500 3820626 0.000 seconds elapsed. ok
*)
ENDDOC
\\ EOF
--- G2/1.0
* Origin: usenet.network (2:5075/128)
SEEN-BY: 5001/100 5005/49 5015/255 5019/40 5020/715
848 1042 4441 12000
SEEN-BY: 5030/49 1081 5058/104 5075/128
@PATH: 5075/128 5020/1042 4441