In the Towers of Hanoi puzzle, we are given a platform with three pegs, a, b, an

Question

In the Towers of Hanoi puzzle, we are given a platform with three pegs, a, b, and c, sticking out of it. On peg a is a stack of n disks, each larger than the next, so that the smallest is on the top and the largest is on the bottom. The puzzle is to move all the disks from peg a to peg c, moving one disk at a time, so that we never place a larger disk on top of a smaller one. See the figure bellow for an example of the case n = 4. Describe a recursive algorithm for solving the Towers of Hanoi puzzle for arbitrary n. (Hint: Consider first the subproblem of moving all but the nth disk from peg a to another peg using the third as "temporary storage.")

Explanation / Answer

Algorithm:

Input : N (no. of disks)

Output: Moving N disks from a to c

TowerOfHonoi(N, a, b, c):

1. if N := 1

              Move only disk from a to c         

2. Otherwise

              Move N-1 disks from a to b using c as temporary storage i.e, TowerOfHonoi(N-1, a, c, b)

              Move Nth disk from a to c

              Move N-1 disks from b to c using a as temporary storage t.e, TowerOfHonoi(N-1, b, a, c)

Pseudo code:

Function TowerOfHonoi(N, a, b, c):         

              IF N == 1, THEN:

                             move disk from a to c

              ELSE:

                             TowerOfHonoi(N - 1, a, c, b)

                             move Nth disk from a to c            

                             TowerOfHonoi(N - 1, b, a, c)

              END IF

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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