汉诺塔

介绍

如下图所示，从左到右有 A、B、C 三根柱子，其中 A 柱子上面有从小叠到大的 n 个圆盘，现要求将 A 柱子上的圆盘移到 C 柱子上去，期间只有一个原则：一次只能移到一个盘子，且大盘子不能在小盘子上面，求移动的步骤和移动的次数。

思路

当 n == 1：
1. 1 号盘：A -> C
当 n == 2：
1. 1 号盘：A -> B
2. 2 号盘：A -> C
3. 3 号盘：B -> C
当 n == 3：
1. 1 号盘：A -> C
2. 2 号盘：A -> B
3. 1 号盘：C -> B
4. 3 号盘：A -> C
5. 1 号盘：B -> A
6. 2 号盘：B -> C
7. 1 号盘：A -> C

分析：实现这个算法可以简单分为三个步骤：

把 n-1 个盘子由 A 移到 B；
把第 n 个盘子由 A 移到 C；
把 n-1 个盘子由 B 移到 C；

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class HanoiTest {
    // 将 A 的盘移动到 C
    public static void hanoi(int n, char A, char B, char C) {
        if (n == 1) {
            move(A, C);
        } else {
            hanoi(n-1, A, C, B);  // 将 n-1 个盘通过 C 移动过到 B
            move(A, C);     // 将第 n 个盘移动到 C
            hanoi(n-1, B, A, C);   // 将 n-1 个盘通过 A 移动到 C
        }
    }

    static void move(char A, char C) {
        System.out.println("move:" + A + " -> " + C);
    }

    public static void main(String[] args) {
        System.out.println("移动汉诺塔的步骤：");
        hanoi(3, 'A', 'B', 'C');
    }
}

时间复杂度

利用数学上的数列知识：F(n=1) = 1, F(n=2) = 3，F(n=3) = 7，F(n) = 2F(n-1)+1，所以 F(n) = 2ⁿ - 1，为指数级别的时间复杂度。

参考：汉诺塔的图解递归算法

介绍

思路

代码

时间复杂度

相关文章：