PadhaikoAll subjects

Past exam question: 2079 Ashwin (Back), Q5(a)

Data Structure and Algorithms · 3 marks

Open in the Padhaiko app

Topic: Recursion

Question

Write an algorithm for Tower of Hanoi (TOH) with 'n' disks.

Solution

Problem Formulation and Rules: The Tower of Hanoi (TOH) puzzle consists of three pegs: Source (), Destination (), and Auxiliary (), with disks of differing diameters initially stacked on in descending order of size.

The objective is to transfer all disks from peg to peg subject to three inviolable rules:

  1. Only one disk can be moved at any time.
  2. Only the uppermost disk from a peg may be picked up.
  3. No larger disk may ever be placed atop a smaller disk.

Recursive Strategy (Divide and Conquer): To transfer disks from to using as an auxiliary peg:

  1. Subproblem 1: Recursively move the top disks from to using as the auxiliary peg.
  2. Base Action: Move the remaining -th (largest) disk directly from to .
  3. Subproblem 2: Recursively move the disks from to using as the auxiliary peg.

Base Case: If , move the single disk directly from to and terminate.

Formal Recursive Algorithm:

Algorithm TOH(n, Source, Destination, Auxiliary):
1. [Base Case: Single Disk]
   If n == 1:
       Print "Move disk 1 from " + Source + " to " + Destination
       Return

2. [Recurse: Move n-1 disks from Source to Auxiliary]
   Call TOH(n - 1, Source, Auxiliary, Destination)

3. [Direct Move: Move the largest n-th disk to Destination]
   Print "Move disk " + n + " from " + Source + " to " + Destination

4. [Recurse: Move n-1 disks from Auxiliary to Destination]
   Call TOH(n - 1, Auxiliary, Destination, Source)

5. Return

Complexity Analysis:

Answer:

The recursive Tower of Hanoi algorithm:

void TOH(int n, char S, char D, char A) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", S, D);
        return;
    }
    TOH(n - 1, S, A, D);
    printf("Move disk %d from %c to %c\n", n, S, D);
    TOH(n - 1, A, D, S);
}

Requires exactly moves, running in time and stack space.

All past exam questions for Data Structure and Algorithms