) Tower of Hanoi problem is stated as follows: There are 3 pegs 1, 2 and 3 and i

Question

) Tower of Hanoi problem is stated as follows: There are 3 pegs 1, 2 and 3 and initially we have a stack of different sized disks in peg 1 with a smaller disk on top of a larger disk. The task is to move these disks to peg 2 using the other peg if necessary with the restriction that you can only move a disk from top of the stack and place it on a larger disk in another peg. For example, if we have 2 disks in peg 1, we can do the following: (a) Move top disk from peg 1 to peg 3, (b) Move the bottom disk from peg 1 to peg 2, (c) Move the disk from peg3 to peg 2. Can you extend this to 3 disks ? Think recursively and that approach should work for any n.
Write a recursive function tower_of_hanoi(n, fromPeg, toPeg) that prints the disc moves required to move a stack of n disks from fromPeg to toPeg where fromPeg and toPeg are integers between 1 and 3. Test your function for n=3 and n=4. For example, the call tower_of_hanoi(3,1,2) should print the following:
Move disk from peg 1 to peg 2
Move disk from peg 1 to peg 3
Move disk from peg 2 to peg 3
Move disk from peg 1 to peg 2
Move disk from peg 3 to peg 1
Move disk from peg 3 to peg 2
Move disk from peg 1 to peg 2

Explanation / Answer

#include<stdio.h>

void towerOfHanoi(int n, int from_peg, int to_peg, int oth_peg)
{
    if (n == 1)
    {
        printf(" Move disk 1 from peg %d to peg %d ", from_peg, to_peg);
        return;
    }
    towerOfHanoi(n-1, from_peg, oth_peg, to_peg);
    printf(" Move disk %d from peg %d to peg %d ", n, from_peg, to_peg);
    towerOfHanoi(n-1, oth_peg, to_peg, from_peg);
}

int main()
{
   towerOfHanoi(3, 1,2,3);
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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