From: A Certain Monk at a certain village in Hanoi I thought I'd share this with you: -----------CUT HERE------------- program Hanoi(input,output); type Pegnumber = 1..3; var N: integer; Procedure WriteMoves (N: integer; Peg1, Peg2, Peg3: PegNumber); begin {Moves} if N=1 then writeln('Move a ring from ', Peg1:1, ' to ', Peg2:1) else begin {else} WriteMoves(N-1, Peg1, Peg3, Peg2); writeln('Move a ring from ', Peg 1:1, ' to ', Peg2:1); WriteMoves(N-1, Peg3, Peg2, Peg1) end {else} end; {Moves} begin {Program} writeln{'Enter the number of rings and'); writeln('I''ll explain how to play Towers of Hanoi.'); readln(N); writeln (' To move ', M,' rings'); writeln (' from peg 1 to peg 2 proceed as follows:'); WriteMoves(N, 1, 2, 3); writeln (' That does it.') end. {Program} ------------AND HERE----------- I've used it on 64 rings, and it works fine. Of course this runs slowly and does tend to use a lot of storage. The stack really grows too large. I'm hoping that it may be possible to use this type of call with some bandwidth growth to help defeat analysis. "Would you tell me, please, which way I ought to go from here?" "That depends a good deal on where you want to get to." said the Cat. --Lewis Carroll
Of course this runs slowly and does tend to use a lot of storage. The stack really grows too large. I'm hoping that it may be possible
That's just because it was an intuitive, but excruciatingly inefficient, implementation. You can do towers of hanoi with *no* stack, as long as you can loop (and even if you can't explicitly loop, you can do it tail recursively, which this version isn't, and still avoid using stack.) It's much harder to recognize that the code relates to the problem... but if you treat the problem as "generate this stream of numbers" it's not too hard to see how to do it. The story behind the original "towers of hanoi" problem (three ivory rods, 64 gold and silver disks) is amusing, though, in that it's an example of using an "intractable" problem (moving the 64 rings by the proper rules -- only stack on the immediate smaller size, only move one at a time, and get the whole pile moved) to protect a "secret" (as I've heard it, the world would be destroyed (or saved?) when the operation was finished... perhaps the "secret" would be that it wasn't going to work :-) [how's that a desperate stretch for a cryptographic tie in?] _Mark_ <eichin@paycheck.cygnus.com> ... just me at home ...
participants (2)
-
Anonymous -
Mark W. Eichin