汉诺塔

2020-03-17 约 1036 字预计阅读 3 分钟

汉诺塔问题

汉诺塔问题是递归的一个具体案例。
汉诺游戏规则如下：

1、有三根相邻的柱子，标号为 A(起始柱子),B(中间柱子),C(目标柱子)。

2、A 柱子上从下到上按金字塔状叠放着 n 个不同大小的圆盘。

3、现在把所有盘子一个一个移动到柱子 C 上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方。
汉诺塔的解题思想
- 不考虑全局，不展开递归，人脑的思维内能力有限，所以我们需要把问题简化，只考虑当前应该怎么做即可。
- 将汉诺塔问题看作两种情况：1.只有一个圆盘时 2.只有两个圆盘时(最下面的最大的盘子和上面的其他所有的盘子)。
- 当递归调用开始，每一次递归都是对之前递归的重复，直到条件或断言终止。
- 汉诺塔问题不是单一的递归问题，当圆盘个数大于 1 时，里面包含了 3 个步骤：(上面代表除最下面以外的所有盘子，下面代表最下面的盘子)
  - 移动上面的所有盘子到中间柱子
  - 移动下面的盘子到目标柱子
  - 再把移动过的上面的所有盘子从中间柱子移动到目标柱子
- 递归联想：假如有十个农民工，我们姑且叫他们老 1，老 2 …..老 10
  - 村里承包项目，盖十层楼
  - 村里把项目交给老 10 来做，老 10 只会盖第十层楼，没办法，没有前面 9 层楼他也没法盖啊，然后就把前 9 层的项目外包给了老 9
  - 很巧，老 9 只会盖第九层楼，老 9 又把前 8 层项目外包给了老 8
  - 老 8 也是一样，只会盖第 8 层，又把前 7 层外包给了老 7
  - 老 7 只会盖第 7 层，然后又外包了下去
  - 老 6…..
  - 老 5….
  - 老 4…
  - 老 3..
  - 老 2..
  - 最终老 1 拿到了这个盖第 1 层楼的活，没法再外包了(条件终止),然后老 1 就盖了起来，然后老 1 盖好 1 层了老 2 盖好 2 层……老 7 盖好 7 层，老 8 盖好 8 层，直到老 10 盖好第十层，这个项目就算完工了
  - 这个故事就是纯正的递归思想，包括思路应该很清楚了

测试代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


/**
 * @author: YunTaoChen
 * @description:
 * @Date: Create in
 * @Modified by:
 */
public class Hanoi {
    //全局变量count统计方法调用的次数
    static int count;

    public static void main(String[] args) {
        move(8, 'a', 'b', 'c');
        System.out.println(count);
    }
//A表示起始位置，B表示中间位置，C表示目标位置
    public static void move(int n, char A, char B, char C) {

        if (n == 1) {
            //如果只有一个盘子，那么就从起始位置直接移到目标位置
            System.out.println(1 + " From " + A + " to " + C);
        } else {
             //这里运用了递归思想，无论有多少个盘子，我们都认为只有两个，上面所有的和最下面的单独的一个盘子
            //移动上面的所有圆盘到中间位置
            move(n - 1, A, C, B);
            //移动最下面的圆盘到目标位置
            System.out.println(n + " From " + A + " to " + C);
            //把中间位置的圆盘移到目标位置
            move(n - 1, B, A, C);
        }
        //每调用一次move，count计数一次
        count++;
    }
}

目录

汉诺塔

汉诺塔问题