[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionIn a monastery in Benares India there are three diamond towers holding 64 disks made of gold. The disks are each of a different size and have holes in the middle so that they slide over the towers and sit in a stack. When they started, 1500 years ago, all 64 disks were all on the first tower arranged with the largest on the bottom and the smallest on the top. The monks' job is to move all of the disks to the third tower following these three rules: Techniques & BackgroundThis is version 1 of the Towers problem. It knows what to do, but doesn't really do it. Coming are Version 2, makes the moves internally and displays a list of which disks move to which pegs and Version 3 which adds graphics so you can drag the disks around or watch the program move them. But first to solve the basic problem. Here is a good example of the method of mathematical proof known as "Mathematical Induction". The Induction method applied to our problem says that if you can solve it for one disk and if, assuming you can solve the problem for M disks, you can tell how to solve it for M+1 disks, then you can solve the problem for any number of disks! So, we can surely solve the problem for one disk - just move it. Given a stack of M+1 disks, and knowing how to move M disks, can we figure out how to solve the problem? First notice that the top M disks of this pile wouldn't know about the bottom disk at all - since it's the largest disk, if it were alone on the tower, any other disk could move on top of it just like it wasn't there. I'm going to use the word "pegs" for "towers" from now on - shorter. Lets call the pegs A, B, and C and assume that we have the M+1 disks on peg A. We're assuming by induction that we can move the top M disks to another peg, say to B. Presto, we did it! So we now we have peg A left with the largest disk, peg B with the other M disks and peg C empty. Now move the largest disk from A to C. Next, since we have a method that moves M pegs from peg A to peg B, we can just re-label the pegs appropriately (so A has the M pegs, B is the one with the large disk on it that we want to move the other M to, and C is the spare). Now apply our method for moving M pegs from A to B once again and we're done! If you look at the source code, you'll see that that is exactly what the program does. There is a procedure called MoveOne(A,B) that moves the top disk from peg A to peg B. In this version it doesn't do much except add 1 to a counter and call Application.Processmessages to give Windows a chance to do handle other messages (like the user hitting the stop button). Later on, Moveone will list the move or do the graphics stuff. The other major procedure is called MoveStack(n,A,B,C). Its job is to move a stack of n disks from A to B using peg C as the spare. It does this using another bit of magic called recursion. Recursion occurs when a procedure calls itself. See this article in Delphi Techniques for a more extensive discussion. To move along here, MoveStack performs the 3 steps we described above Procedure MoveStack(n,A,C,B:Integer); Begin If n=1 then MoveOne(A,C); {If there's only one to move, move it} MoveStack(n-1,A,B,C); MoveStack(n-1,B,C,A); end; That's it. Some code to display output and to let the user stop if he puts in a big number and estimate time to complete and we're done. For now. Running/Exploring the Program
Suggestions for Further ExplorationsNext time, we'll present a version smart enough to list the moves. Work on that if you're bored and looking for something to do.Two more problems in recursion.See this article on Recursion describing a couple of examples of recursive function calls. Then:
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |