设计与思考

改变世界的力量

0%

汉诺塔问题

发表于 分类于

题目

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

示例1:

输入：A = [2, 1, 0], B = [], C = []
输出：C = [2, 1, 0]
示例2:

输入：A = [1, 0], B = [], C = []
输出：C = [1, 0]
提示:

A中盘子的数目不大于14个。

解决思路

优先考虑递归实现, 那么考虑以下3个问题:

  1. 问题能否分解?
  2. 问题与分解后的子问题, 除了数据规模不同, 解决思路完全一样吗?
  3. 递归终止条件?

首先模拟一下小数据量时的解决过程:

  • n = 1:
    A将最大盘子移到C,A -> C
  • n = 2:
    A将1个盘子移到B, 再将最大盘子移到C,B再将1个盘子移到C
    A -> B, A -> C, B -> C
  • n = 3时:
    A将2个盘子移到B, 再将最大盘子移到C,B再将2个盘子移到C
    A -> C, A -> B, C -> B, A -> C | B -> A, B -> C, A -> C

那么, 我们可以推出子问题和递归终止条件了:

  • 当n > 1:

    • 先把A上的n-1个盘子通过C移到B(子问题, 递归)
    • 再把A上最大盘子移到C
    • 再把B上n-1个盘子通过A移到C(子问题, 递归)

  • 递归终止条件:
    n = 1, 直接把A上的盘子移到C

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
    if (A == null || A.size() == 0) {
        return;
    }
    hanoi(A.size(), A, B, C);
}

public void hanoi(int n , List<Integer> A, List<Integer> B, List<Integer> C) {
    if (n == 1) {
        C.add(A.remove(A.size() - 1));
        return;
    }
    hanoi(n - 1, A, C, B);
    C.add(A.remove(A.size() - 1));
    hanoi(n - 1, B, A, C);
}