tomclegg.net |
Towers of HanoiPosted March 25, 2001 Mostly Mozart is sponsored by Comfort and Joy, a unique children's store. The other day, I was trying to fall asleep, and since I resolved a long time ago never to count sheep in order to fall asleep, I started listing programming languages instead. One for each letter of the alphabet. But don't get scared. This is not going to be a show about programming. This is just the setup. A and B are pretty easy. Everyone knows about assembly language and BASIC. C is even easier, since there's a language called C. D is for Dylan; E is for Expect. F is obviously for Fortran, or perhaps Forth. G is for ghostscript, a non-proprietary language that happens to be compatible with Postscript (tm).
Then I got stuck on H. It
Then I thought that there should be a programming language called
Hanoi. I don't know if there Here's how it works. You've got a small board, with three pegs pointing straight up. The first peg has eight different-sized rings on it, with the smallest ring at the top and the biggest ring at the bottom. The other two pegs are empty. Your task is to move all of the rings from the first peg onto the second peg. Which sounds easy, of course, until you hear the rules. The first rule is that you can only pick up one ring at a time, and you have to put it onto another peg immediately. The second rule is that you can't put a bigger ring on top of a smaller ring. And that's all the rules.
You don't need pegs and rings in order to play the Towers of Hanoi.
If you don't have pegs and rings, you can just cut out eight pieces of
paper of different sizes, or use different sizes of coins, or
whatever. But if you
While you listen to the music, have a little game of Towers of Hanoi.
If you're planning to move one ring every 8 seconds, you'll need just
8 rings to take you to the end of this Mozart piece. If you're going
to move one ring Before the music starts, here are the rules again: You need 8 rings of different sizes, and three real or imaginary pegs to put them on. You start out with all 8 rings on the first peg, the biggest one at the bottom and the smallest one at the top. The object is to move all the rings onto one of the two empty pegs. And there are only two rules. You can only move one ring at a time; and you can't put a bigger ring on top of a smaller ring. Have fun, and play nice! --- Comfort and Joy is happy to sponsor Mostly Mozart. My name is Tom Clegg, and today I'm teaching you to play a solitaire game called the Towers of Hanoi.
If you caught the first few minutes of the show, you've had a little
fun with the Towers already. And perhaps you were paying really close
attention to the bit about how long it takes to play a game with 19
rings. 20 hours a day for 7 days, moving one ring per Let's go over the rules again. You start with 8 rings, smallest one at the top. You can move one ring at a time, and you can't put a bigger ring on top of a smaller ring.
So the first two moves were probably pretty obvious. You take ring
#1, the smallest ring, and put it on an empty peg. Then you take ring
#2, and since you can't put it on top of ring #1, you have to put it
on the Now, before you take ring 3 off the first peg and put it on the empty peg, you should notice something. You just made 3 moves. And you just finished a 2-ring game of Towers of Hanoi. You took two rings, smallest one at the top, and moved them on to another peg, without breaking either of the rules. Now you can move ring 3 onto an empty peg. That's your fourth move. Then you move rings 1 and 2 onto ring 3, using the same sequence of three moves that you just used to get them off the first peg in the first place. That's a total of 7 moves. So. Moving 1 ring takes 1 step. Moving 2 rings takes 3 steps. Moving 3 pegs takes 7 steps. I think there's a pattern emerging. In order to move three rings, you first move the 2 top rings onto one empty peg, then you move ring 3 onto another empty peg, then you move the 2 top rings on top of it. So, to play a 3-ring game, you simply play a 2-ring game, take one step to move ring 3, then play another 2-ring game. So the number of steps it takes to play a 3-ring game is twice what it takes to play a 2-ring game, plus one. Twice 3, plus 1, equals 7. So, if it takes 7 steps to play 3 rings, how many steps does it take to play 4 rings? Twice 7 is 14, plus 1 is 15. 5 rings? twice 15 is 30, plus 1 is 31. Now if you know any of the powers of 2, you'll notice something about this sequence of numbers. 1, 3, 7, 15, 31. If not, you'll certainly notice something about them if I add 1 to each of them. 2, 4, 8, 16, 32. Each time you add another ring to the game, it takes you twice as many steps to finish. This means that the time it takes to play Towers of Hanoi grows exponentially with the number of rings. If you stack up a few hundred rings, the number of steps required to finish the game will be pretty close to the number of particles in the universe. |