Re: Change for a Dollar

Mark P wrote:
Charles Richmond wrote:
Mark P wrote:
Charles Richmond wrote:

>>>> [snip...] [snip...] [snip...]



This may *count* the number of ways change can be made. I am
*not* sure that these loops do what you (or I) think they do.

I won't speak for you, but I'm certain that these loops do exactly what *I* think they do. What do you think they do?


But for my program, I want to *list* all the ways of making
change. So lines of the list might be:

I considered writing a follow-up post after I noticed that this is what you asked for, but then I thought it might make a fun exercise for the reader to let him (you) figure it out. But if you want me to ruin that potential fun, I will. Simply replace the line ++n_ways; with an appropriate print statement using the values of n_50, n_25, n_10, n_5 and an appropriately computed value for the number of pennies.


Yes, you are certainly right. I missed some salient points of
your program when I first looked at it. I wrote my program to
use your code with the change that it printed out each solution,
and it produced all 292 ways.

I originally tried to write a recursive version in a *similar*
vein. My recursive program was *not* a very good one. For each
solution it produced, it created about 2000 extra copies of the
*same* solution. That did *not* trash the solutions, because
I was keeping a "database" of the found solutions and only
added a solution if it did *not* exist in the database already.
But *my* recursive program was *bad* and ran forever. :-( I
know there is a much better way to write a recursive one.


P.S. Incidentally, I ran my program and it computed 292 ways not 293, but perhaps Dave considers the original dollar to be the "missing" way?

Indeed, the 293rd way *is* just a silver dollar. I also tried
googling "293 ways to make" and found the following web sites
that lists the ways. Here are a couple of the sites:

http://www.maa.org/features/mathchat/mathchat_4_19_01.html

http://www.delphiforfun.org/Programs/Making_change.htm

http://www.teachnet.com/lesson/math/293changedollar.html


Thanks for your help with this... it was preying on my mind. ;-)


--
+----------------------------------------------------------------+
| Charles and Francis Richmond richmond at plano dot net |
+----------------------------------------------------------------+
.

Relevant Pages

  • Re: VBA - Form Progress
    ... loops. ... standard basic code along with database code. ... Dirk Goldgar, MS Access MVP ...
    (microsoft.public.access.modulesdaovba)
  • Re: pattern matching
    ... > database are used in this field and if so create a link to those words. ... > already showing the meaning of the word (taken from the meaning field). ... at the command prompt and *use the Perl debugger*. ... Proper indentation of the loops would help understanding of ...
    (comp.lang.perl.misc)
  • Re: Algorithm for faster search in DataTable
    ... > the data adapter's Update method to push those claims into the ... > check in the database. ... > can use so that I cut down the number of loops? ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Sqlite3. Substitution of names in query.
    ... your experience means very little for database ... 10000 loops, best of 3: ... drowned out by other fixed costs associated with performing database ... Carsten Haese ...
    (comp.lang.python)
  • Re: optimizing for speed - Array#each
    ... promising is improving your algorithm in a way that it has to run less ... loops. ... database table in some sorted fashion and dump it as a CSV file. ... separate table so you can run those same transactions on the other ...
    (comp.lang.ruby)