Question

Describe an algorithm to solve the variant of the Towers of Hanoi in as few moves as possible. Prove that your algorithm is correct. Initially, all the n disks are on peg 1, and you need to move the disks to peg 2. You are not allowed to put a bigger disk on top of a smaller disk.

1. Suppose you are forbidden to move any disk directly between peg 1 and peg 2, and every move must involve (the third peg). Exactly (i.e., not asymptotically) how many moves does your algorithm make as a function of n?

Answer 1

How many moves will it take to transfer n disks from the left post to the right post?

1 disk: 1 move

• Move 1: move disk 1 to post C

2 disks: 3 moves

• Move 1: move disk 2 to post B
  Move 2: move disk 1 to post C
  Move 3: move disk 2 to post C

3 disks: 7 moves

• Move 1: move disk 3 to post C
  Move 2: move disk 2 to post B
  Move 3: move disk 3 to post B
  Move 4: move disk 1 to post C
  Move 5: move disk 3 to post A
  Move 6: move disk 2 to post C
  Move 7: move disk 3 to post C

A. Recursive pattern

Here M = the number of moves

1. for 1 disk it takes 1 move to transfer 1 disk from post A to post C;
2. for 2 disks, it will take 3 moves:    2M + 1 = 2(1) + 1 = 3
3. for 3 disks, it will take 7 moves:    2M + 1 = 2(3) + 1 = 7
4. for 4 disks, it will take 15 moves: 2M + 1 = 2(7) + 1 = 15
5. for 5 disks, it will take 31 moves: 2M + 1 = 2(15) + 1 = 31

B. Explicit Pattern

• Number of Disks (n) Number of Moves
  1 2^1 - 1 = 2 - 1 = 1
  2 2^2 - 1 = 4 - 1 = 3
  3 2^3 - 1 = 8 - 1 = 7
  4 2^4 - 1 = 16 - 1 = 15
  5 2^5 - 1 = 32 - 1 = 31

So the formula for finding the number of steps it takes to transfer n disks from post A to post B is: 2^n - 1.

Algoithm:

 START Procedure Hanoi(disk, A, C, B) IF disk == 1, THEN move disk from A to C ELSE Hanoi(disk - 1, A, B, C) // Step 1 move disk from A to C // Step 2 Hanoi(disk - 1, B, C, A) // Step 3 END IF END Procedure STOP