CS13002 Programming and Data Structures | Section: 4/D, Spring 2005 |
Assignment 4
Tower of Hanoi
There are three pegs A,B,C. Initially, Peg A contains n disks (with holes at their centers). The disks have radiuses 1,2,3,...,n and are arranged in Peg A in increasing sizes from top to bottom, i.e., the disk of radius 1 is at the top, the disk of radius 2 is just below it, ..., the disk of radius n is at the bottom. Your task is to move the disks from Peg A to Peg B in such a way that you are never allowed to move a larger disk on the top of a smaller disk. You may use Peg C as an auxiliary location for the transfer.
An algorithm for this problem can be based on the following idea. First move the top n-1 disks from Peg A to Peg C using Peg B as an auxiliary location. Then move the largest disk from Peg A to Peg B. Finally, move the n-1 disks from Peg C to Peg B using Peg A as an auxiliary location.
Write a recursive function by which you can perform this transfer. Your function should print all disk movements and also the contents of the three pegs after each disk movement. Store the contents of each Peg in an array.
Demonstrate the sequence of movements for n = 8 disks.
Sample output
A recommended format of the output follows. Here . as a peg content means empty location in the corresponding array. The empty locations are shown for neater display.
n = 4 Initial configuration : Peg A: 4321 Peg B: .... Peg C: .... Disk 1 : Peg A to Peg C : Peg A: 432. Peg B: .... Peg C: 1... Disk 2 : Peg A to Peg B : Peg A: 43.. Peg B: 2... Peg C: 1... Disk 1 : Peg C to Peg B : Peg A: 43.. Peg B: 21.. Peg C: .... Disk 3 : Peg A to Peg C : Peg A: 4... Peg B: 21.. Peg C: 3... Disk 1 : Peg B to Peg A : Peg A: 41.. Peg B: 2... Peg C: 3... Disk 2 : Peg B to Peg C : Peg A: 41.. Peg B: .... Peg C: 32.. Disk 1 : Peg A to Peg C : Peg A: 4... Peg B: .... Peg C: 321. Disk 4 : Peg A to Peg B : Peg A: .... Peg B: 4... Peg C: 321. Disk 1 : Peg C to Peg B : Peg A: .... Peg B: 41.. Peg C: 32.. Disk 2 : Peg C to Peg A : Peg A: 2... Peg B: 41.. Peg C: 3... Disk 1 : Peg B to Peg A : Peg A: 21.. Peg B: 4... Peg C: 3... Disk 3 : Peg C to Peg B : Peg A: 21.. Peg B: 43.. Peg C: .... Disk 1 : Peg A to Peg C : Peg A: 2... Peg B: 43.. Peg C: 1... Disk 2 : Peg A to Peg B : Peg A: .... Peg B: 432. Peg C: 1... Disk 1 : Peg C to Peg B : Peg A: .... Peg B: 4321 Peg C: ....