Write the algorithm in pseudocode. 3. Towers of Hanoi problem: There is a board

Question

Write the algorithm in pseudocode.

3. Towers of Hanoi problem: There is a board with three pegs and three disks of different sizes (see Figure 1). The goal of the game is to move the three disks from the peg where they have been placed (largest disk on the bottom, smallest disk on the top) to one of the empty pegs, subject to the following constraints: Only the top disk on a peg can be moved to another peg A larger disk cannot be placed on top of a smaller disk. a. b. Figure 1: Towers of Hanoi Design an algorithm to handle the Towers of Hanoi problem. (20 Marks)

Explanation / Answer

Tower of Hanoi

Tower of Hanoi is a classic problem to learn recursion.

We have three pegs : L, M, R. Peg L contains N(N=3 in this example) disks which are stack in such a way that any disk below is larger then that of disk above as shown in figure. Move these N disks to Peg M in same condition mentioned above using the peg R.

Initial state:

                       

Final State:

Analysis

            If there is only one disk, we can straight forwardly move it from origin to destination. But this problem is with three disks and three pegs. We have to some how move 2 other disk from origin to intermediate peg.
Then move last disk from origin to destination. Then move two disks from intermediate peg to destination.

In general to Move N-1 disks from peg L to peg R and then move the Nth disk to destination peg M. Now we have a problem left with N-1 disks which need to move from peg R to peg M using peg L as spare.

Generalized version of this algorithm is :

So we get the sight of recursion here

First : We need to do same process to N-1 disk which we did for N disks.

Second : Base case is when we are left with only one disk at source, we directly move that to destination.

Pseudo-code for Tower of Hanoi

Function: Tower_Of_Hanoi(N, source,destination,helper)

            If N == 1: Move disk from souce to destination

            Else

            Tower_Of_Hanoi(N-1, source,destination,helper)

            Move disk from source to destination

            Tower_Of_Hanoi(N-1, source,destination,helper)

Code:

void tower_of_hanoi(int N, char source, char dest, char help){

if(N>0){

tower_of_hanoi(N-1, source, help, dest);

printf("Moving disk from %c to %c ", source, dest);

tower_of_hanoi(N-1, help, dest, source);

            }

}

Sample Example:

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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