Learning C++ Programming from Scratch, Day 414: Classic Recursive Problem

1222 – Classic Recursive Problem – Tower of Hanoi

1. Problem Understanding Phase (Tower of Hanoi Problem)

The Tower of Hanoi problem is a classic recursive problem with the following rules:

1. There are three rods (A, B, C), and rod A has n disks of different sizes.

2. Only one disk can be moved at a time.

3. A larger disk cannot be placed on top of a smaller disk.

4. The goal is to move all disks from rod A to rod C.

2. Core Idea of the Recursive Algorithm

The recursive approach to solving the Tower of Hanoi problem is as follows:

1. Move n-1 disks from the source rod to the auxiliary rod.

2. Move the nth (largest) disk from the source rod to the target rod.

3. Move n-1 disks from the auxiliary rod to the target rod.

3. Detailed Execution Process (Example with n=3)

Move sequence:
1. A → C
2. A → B
3. C → B
4. A → C
5. B → A
6. B → C
7. A → C

Reference Code

#include <iostream>  // Include input-output stream library
using namespace std; // Use standard namespace
/**
 * Tower of Hanoi recursive function
 * @param x Number of disks to move
 * @param a Source rod (initially 'A')
 * @param b Auxiliary rod (initially 'B')
 * @param c Target rod (initially 'C')
 */
void han(int x, char a, char b, char c) {
    // Base case: return when there are no disks to move
    if (x > 0) {
        // Step 1: Move x-1 disks from rod a to rod b (using rod c)
        han(x - 1, a, c, b);
        // Step 2: Move the bottom disk from rod a to rod c
        cout << a << " To " << c << endl;
        // Step 3: Move x-1 disks from rod b to rod c (using rod a)
        han(x - 1, b, a, c);
    }
}
int main() {
    int n; // Store the number of disks input by the user
    cin >> n; // Read user input
    // Call the Tower of Hanoi function, moving from rod A using rod B to rod C
    han(n, 'A', 'B', 'C');
    return 0; // Program ends normally
}

Reference Code

#include <bits/stdc++.h>
using namespace std;
/* Move process:
1. First, move n-1 disks (all disks except the bottom one) from position A, using position C, to position B, which requires fun(n-1) steps.
2. Move the bottom disk from position A directly to position C, which requires 1 step.
3. Move n-1 disks from position B to position C using position A, which requires fun(n-1) steps.
Thus, the conclusion is as follows: fun(n) = fun(n-1) + 1 */
void move(int n, char p1, char p2, char p3) {
    // Base case: as long as there are disks, recurse; if no disks, stop recursion
    if (n > 0) {
        // Step 1: Move n-1 disks from p1 to p2 using p3
        move(n - 1, p1, p3, p2);
        // Step 2: Move the nth disk from p1 to p3
        cout << p1 << " To " << p3 << endl;
        // Step 3: Move n-1 disks from p2 to p3 using p1
        move(n - 1, p2, p1, p3);
    }
}
int main() {
    int n;
    cin >> n; // Recursive call, print the move steps
    move(n, 'A', 'B', 'C');
    return 0;
}