Towers of Hanoi

The Towers of Hanoi Problem. According to legend, here existed in ancient Hanoi a monastery where the monks had the painstaking task of moving a collection of n stone disks from one pillar, designated as Pillar a, to another designated as pillar c. Moreover, the relative ordering of the disks on pillar a had to be maintained as they were moved to pillar c, i.e. the disks were to be stacked from largest to smallest, beginning from the bottom. Additionally:

1. Only one disk may be moved at a time.
2. No larger disk could ever be placed on top of a smaller disk.
3. A third pillar b could be used as an intermediate to store one or more disks as they were being moved from their original source a to their destination c.

Consider:

1. If n=1, merely move the disk from a to c.
2. If n=2, move the first disk from a to b. Then, move the second disk from a to c. Then, move the first disk from b to c.
3. If n=3, call upon the technique already established in step 2 to move the first two disks from a to b, using c as an intermediate. Then move the third disk from a to c. Then, use the technique in step 2 to ove the first disks from b to c using a as an intermediate.
4. For general n, use the technique in the previous step to move n-1 disks from a to b using c as intermediate. Then, move one disk from a to c. Then, use the technique in the previous step to move n-1 disks from b to c, using a as intermediate.

function hanoi(numofd, start, dest, spare)

{

if (numofd>0)

{

hanoi(numofd-1,start,spare,dest);

printf("move top of disk from peg %i to peg %i \n",

start, dest);

hanoi(numofd-1,spare,dest,start);

}

}

start,dest, and spare are peg numbers.

Let the comparison of numofd to 0 to be the basic operation.

T(0)=1

• a. Show the recursion tree for numofd=4
• b. From the general recursion tree, write a recurrence formula for T(n)
• c. By examination of your recursion tree, guess a solution to T(n). Show this guess in the form T(n) = theta( ).
• d. Explain the worst case and average case execution behavior of the program.

Last modified: 11/4/2023