Your task is to describe and to implement the algorithm to solve the puzzle. As

Question

Your task is to describe and to implement the algorithm to solve the puzzle. As the number of discs n is given to you as the input (we will use n from 1 to 5, if you program try to go to 10), you have to be able to show the stepbystep solution.

We will use the classical 3 prongs puzzle, remember the rules:

1. If any two or more disks ar eon top of each other, their sizes graduate from the largest on the bottom to the smallest on the top. It is forbidden to place a larger disk on top of a smaller disk.

2. We can only move one disk at a time.
3. We have to achieve the objective of moving all the disks of the tower from the initial peg to the

final peg in a minimum number of steps.

Hint:

Initial set up is to have A as the “beginning” peg with the original tower, B as the “auxiliary” peg, and “C” as the “end” peg to which we wish to move the entire tower.

Image credit: https://en.wikipedia.org/wiki/Tower_of_Hanoi

Own images in the material “Hints for the Towers of Hanoi” posted separately

Try the procedure for n=1, 2, 3.

Now try for n=4.

As we discuss in class, the main idea is to repeat (iterate, if you program – call) the procedure by changing the assignment of the roles of the “beginning”, “auxiliary”, “end” pegs.

(1) Yourinputisthenumberofdisksn.

You may produce a sequence of images as your output or invent (and describe) as way to code the steps and to print them out.

If you code, provide the printout of the code.

If you do not code, provide clear diagrams and/or pictures of you solving the puzzle stepbystep.

(2) Now explain how to setup a recursive relationship for the numbe rof step to solve the puzzle subject to an appropriate initial condition and use any method to solve this recursive relationship theoretically resulting in (2^n1) formula. Hint: we did it in class.

(3) Now usewolframalpha.com (or whichever soft you use)to numerically solve the recursion you set up in (2) and to confirm your theoretical result.

Explanation / Answer

Tower of Hanoi

1. Code :

/* C Program */

#include<stdio.h>

void tower (int n, char beginning, char end, char auxilary)

{

     if(n == 1)

     {

          printf(" Move disk 1 from %c to %c ", beginning, end);

          return;

     }

     tower(n-1, beginning, auxilary, end);

     printf(" Move disk %d from rod %c to %c ", n, beginning, end);

     tower(n-1, auxilary, end, beginning);

}

int main()

{

int n;

printf("Enter the number of disks : ");

scanf("%d",&n);

tower(n, 'A', 'C', 'B');

return 0;

}

Output

Enter the number of disks : 4

Move disk 1 from rod A to rod B

Move disk 2 from rod A to rod C

Move disk 1 from rod B to rod C

Move disk 3 from rod A to rod B

Move disk 1 from rod C to rod A

Move disk 2 from rod C to rod B

Move disk 1 from rod A to rod B

Move disk 4 from rod A to rod C

Move disk 1 from rod B to rod C

Move disk 2 from rod B to rod A

Move disk 1 from rod C to rod A

Move disk 3 from rod B to rod C

Move disk 1 from rod A to rod B

Move disk 2 from rod A to rod C

Move disk 1 from rod B to rod C

2. Forming Recurrence Relation :

If M(n) is the number of disk moves then,

M(1) = 1

M(n) = 2M(n-1) + 1

        = 2[2M(n-2) + 1] + 1 = 4M(n-2) + 3

        = 2^(n-1) * M(1) + 2^(n-1) - 1

        = 2^(n-1) + 2^(n-1) - 1

        = (2^n - 1)

Hence, recurrence relation has been formed for the problem.

Verification :

For n = 4,

2^4 - 1 = 15

(i.e)., 15 steps necessary for 4 disks

The output of the above written program gives 15 steps for 4 disks.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.