Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #13063
| Newsgroups | comp.lang.forth |
|---|---|
| From | Albert van der Horst <albert@spenarnc.xs4all.nl> |
| Subject | Re: Euro's and Dollars. |
| Date | 2012-06-19 15:41 +0000 |
| Message-ID | <m5vfli.1em@spenarnc.xs4all.nl> (permalink) |
| Organization | Dutch Forth Workshop |
| References | <m5tu4r.9ba@spenarnc.xs4all.nl> |
In article <m5tu4r.9ba@spenarnc.xs4all.nl>,
Albert van der Horst <albert@spenarnc.xs4all.nl> wrote:
>In studying Scheme I came across the example program to count
>in how many ways one dollar can be changed.
>Of much more interest is the same problem for the Euro.
>
>This can be even shorter in Forth.
>Translating the Lisp source is probably easier then debugging a
>Forth version. :-(
Elizabeth has called this insane stacktrashing, let's see.
The explanation why the lisp program worked runs several pages.
>-----------8< --------------------------------
>CREATE kind-of-coins 0 , 1 , 5 , 10 , 25 , 50 ,
>: first-denomination kind-of-coins SWAP CELLS + @ ;
>
>( amount kinds-of-coins -- count )
>: cc OVER 0= IF 2DROP 1 ELSE OVER 0< OVER 0= OR IF 2DROP 0 ELSE
> 2DUP 1- RECURSE >R >R R@ first-denomination - R> RECURSE R> +
> THEN THEN ;
( amount kinds-of-coins -- same same flag )
: zero-amount OVER 0= ;
( amount kinds-of-coins -- same same flag )
: negative-amount-or-no-coins?
OVER 0< OVER 0= OR ;
( amount kinds-of-coins -- amount lesser-kinds-of-coins )
: one-less-kind 1- ;
( amount kinds-of-coins -- new-amount kinds-of-coins )
: one-less-large-coin >R R@ first-denomination - R> ;
\ Personally prefer this over :
: one-less-large-coin DUP first-denomination NEGATE ROT + SWAP ;
( amount kinds-of-coins -- count )
: cc [ RECURSIVE ( so we can call cc from within ) ]
\ We can compose an amount of zero in exactly one way, regardless of
\ the coins available. (or is this nanny-granny comment?)
zero-amount? IF 2DROP 1 ELSE
\ We cannot realize a negative amount, or any amount using no
\ coins (except zero, but that has already been take into account.)
negative-amount-or-no-coins? IF 2DROP 0 ELSE
\ Possibility one: don't use largest denomination
2DUP one-less-kind 2>R ( a k -- a k )
\ Possibility two: do use largest denomination so at least one of it.
one-less-coin 2>R ( a k -- )
( empty stack, all arguments on return stack )
2R> cc 2R> cc +
THEN THEN ;
Disclaimer : above code for illustration purposes. It has not been
tested.
>
>( amount -- count )
>: count-change 5 cc ;
>
>100 count-change "Dollars :" TYPE . CR
>
>-----------8< --------------------------------
>
>For euro's you need:
>
>-----------8< --------------------------------
>CREATE euro-change 0 , 1 , 2 , 5 , 10 , 20 , 50 ,
>: count-change 6 cc ;
>-----------8< --------------------------------
>
>
>Dollars : 292
>
>Euro's : 4562
>
>The Euro wins. (As long as you use cents and tuppences,
> which will be over shortly.)
>
>Now for the $100 question.
>If we order the coins in descending order then :
>
>A. It gives a wrong result
>B. It runs faster
>C. It runs slower but not by an order of magnitude
>D. It runs so slow that you may loose your patience, or risk
> a stack overflow
>
>Groetjes Albert
>
P.S. the worst trashing occurred by a news reader that changed
2DUP 1- RECURSE >R >R R@ first-denomination - R> RECURSE R> +
into
2DUP 1- RECURSE>R>R R@ first-denomination - R> RECURSE R> +
--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-18 19:00 +0000
Re: Euro's and Dollars. "A. K." <akk@nospam.org> - 2012-06-18 23:18 +0200
Re: Euro's and Dollars. Mark Wills <markrobertwills@yahoo.co.uk> - 2012-06-19 00:20 -0700
Re: Euro's and Dollars. "Elizabeth D. Rather" <erather@forth.com> - 2012-06-18 21:51 -1000
Re: Euro's and Dollars. vandys@vsta.org - 2012-06-19 00:49 +0000
Re: Euro's and Dollars. Spam@ControlQ.com - 2012-06-18 21:43 -0400
Re: Euro's and Dollars. "A. K." <akk@nospam.org> - 2012-06-19 07:20 +0200
Re: Euro's and Dollars. Ecki <ecki@intershop.de> - 2012-06-19 09:26 +0200
Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-19 15:58 +0000
Re: Euro's and Dollars. "A. K." <akk@nospam.org> - 2012-06-19 19:58 +0200
Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-20 01:31 +0000
Re: Euro's and Dollars. "A. K." <akk@nospam.org> - 2012-06-20 07:15 +0200
Re: Euro's and Dollars. Ecki <ecki@intershop.de> - 2012-06-20 10:15 +0200
Re: Euro's and Dollars. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-06-20 10:46 +0000
Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-20 17:39 +0000
Re: Euro's and Dollars. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-06-21 16:21 +0000
Re: Euro's and Dollars. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-06-21 11:58 -0500
Re: Euro's and Dollars. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-06-22 14:57 +0000
Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-21 20:38 +0000
Re: Euro's and Dollars. vandys@vsta.org - 2012-06-19 15:49 +0000
Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-19 15:43 +0000
Re: Euro's and Dollars. vandys@vsta.org - 2012-06-19 15:51 +0000
Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-19 15:41 +0000
Re: Euro's and Dollars. Paul Rubin <no.email@nospam.invalid> - 2012-06-19 10:26 -0700
Re: Euro's and Dollars. Paul Rubin <no.email@nospam.invalid> - 2012-06-19 23:34 -0700
Re: Euro's and Dollars. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-06-19 12:41 -0500
Re: Euro's and Dollars. Paul Rubin <no.email@nospam.invalid> - 2012-06-19 11:10 -0700
Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-20 03:12 +0000
Re: Euro's and Dollars. Paul Rubin <no.email@nospam.invalid> - 2012-06-19 23:51 -0700
Re: Euro's and Dollars. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-06-20 03:15 -0500
csiph-web