0%

汉诺塔问题总结

发表于 分类于
很久之前曾经总结了郝斌老师的对汉诺塔问题的解析，当时还暂时不能彻底理解，今天又重温一下汉诺塔问题，并尝试使用递归与非递归两种方式来进行实现

一、基本递归实现

下面是普遍的汉诺塔问题的递归解法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Hanoi{
    public static void hanoi(int n, String x, String y, String z){
        if (n == 1){
            System.out.println(x + " -> " + z);
        }else {
            hanoi(n - 1, x, z, y);
            System.out.println(x + " -> " + z);
            hanoi(n - 1, y, x, z);
        }
    }
    public static void main(String[] args) {
        hanoi(3, "x", "y", "z");
    }
}

输出如下：

1
2
3
4
5
6
7
x -> z
x -> y
z -> y
x -> z
y -> x
y -> z
x -> z

二、基本非递归实现

非递归实现的方式本质就是尝试使用栈来模拟递归

1.创建一个保存状态的类

1
2
3
4
5
6
7
8
9
10
11
12
13
public class State {
    public int n; // 当前层数
    public String x; // 起始柱
    public String y; // 辅助柱
    public String z; // 目标柱

    public State(int n, String x, String y, String z) {
        this.n = n;
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

2.实现主程序

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
public class Hanoi {

    public void hanoi(int n, String x, String y, String z) {
        Stack<State> s = new Stack<>();
        s.push(new State(n, x, y, z));
        State state;
        while (!s.empty() && (state = s.pop()) != null) {
            if (state.n == 1) {
                System.out.println(state.x + " -> " + state.y);
            } else {
                // 栈结构先进后出，所以需要逆序进栈，这部分是理解重点，用栈模拟递归
                s.push(new State(state.n - 1, state.y, state.x, state.z));
                s.push(new State(1, state.x, state.y, state.z));
                s.push(new State(state.n - 1, state.x, state.z, state.y));
            }
        }
    }

    public static void main(String[] args) {
        Hanoi hanoi = new Hanoi();
        System.out.println();
        System.out.println("非递归方式：");
        Hanoi.hanoi(3, "x", "y", "z");
    }
}

3.输出结果

1
2
3
4
5
6
7
8
非递归方式：
x -> z
x -> y
z -> y
x -> z
y -> x
y -> z
x -> z

三、汉诺塔问题扩展

我们尝试更改一下题目要求，不只是需要输出交换步骤，我们还需要记录交换过程中的三个柱子的圆盘存在情况

1.创建柱子类

该类用于表示汉诺塔的每一个柱子，并且这个类将记录每个柱子上的圆盘情况

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class HanoiPillar {
    public int n; // 记录传递hanoi的圆盘数量
    public String name; // 柱子名称
    public ArrayList<Integer> arr = new ArrayList<>(); //用于记录当前柱子上所存在的圆盘

    // 初始化A柱
    public HanoiPillar(int n, String name) {
        this.n = n;
        this.name = name;
        for (int i = n; i > 0; i--) {
            this.arr.add(i);
        }
    }

    // 初始化B柱和C柱
    public HanoiPillar(String name) {
        this.name = name;
    }

    // 判断该柱子上方是否为顶部盘子
    public boolean top() {
        boolean result = false;
        if (!arr.isEmpty() && arr.size() != 0 && arr.get(arr.size() - 1) == 1) {
            result = true;
        }
        return result;
    }

    public void moveTo(HanoiPillar hanoiPillar) {
        hanoiPillar.arr.add(this.getDiskSize());
        this.arr.remove(this.arr.size() - 1);
        System.out.println(this.name + " -> " + hanoiPillar.name);
    }

    // 得到当前柱子的圆盘的列表，转化为String
    public String getStore() {
        StringBuilder result = new StringBuilder();
        if (this.arr.size() > 0) {
            for (int i = this.arr.size() - 1; i >= 0; i--) {
                result.append(this.arr.get(i)).append(",");
            }
        }
        return result.length() == 0 ? "null" : result.toString().trim();
    }

    // 得到该柱子中最小的圆盘的数值。以1、2、3、4、......、n来表示各个圆盘的大小。并且方便比较
    public Integer getDiskSize() {
        return this.arr.get(this.arr.size() - 1);
    }
}

2.实现主程序

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
public class Hanoi {
    private int n;
    private int step;
    private HanoiPillar a;
    private HanoiPillar b;
    private HanoiPillar c;

    public void hanoi(int n, String a, String b, String c) {
        this.step = (int) (Math.pow(2, n) - 1);
        this.a = new HanoiPillar(n, a);
        this.b = new HanoiPillar(b);
        this.c = new HanoiPillar(c);
        this.n = n;
        if (n % 2 != 0) {
            HanoiPillar tmp = this.b;
            this.b = this.c;
            this.c = tmp;
        }
        while (this.step > 0) {

            // 进行top的移动
            if (this.a.top()) {
                list();
                this.a.moveTo(this.b);
                this.step--;
            } else if (this.b.top()) {
                list();
                this.b.moveTo(this.c);
                this.step--;
            } else if (this.c.top()) {
                list();
                this.c.moveTo(this.a);
                this.step--;
            }

            // 因为step为奇数，而最后完成后step=0；
            // 同时可以理解为最后一次移动一定是top移动，所以需要进行一次循环判断
            if (this.step == 0) {
                break;
            }

            // 执行第二步移动
            if (this.a.top()) {
                move2(this.b, this.c);
            } else if (this.b.top()) {
                move2(this.a, this.c);
            } else if (this.c.top()) {
                move2(this.a, this.b);
            }
        }
        list();
    }

    private void list() {
        if (n % 2 == 0) {
            System.out.print(this.a.name + "柱：" + this.a.getStore() +
                    "		" + this.b.name + "柱：" + this.b.getStore() +
                    "		" + this.c.name + "柱：" + this.c.getStore() + "			");
        } else {
            System.out.print(this.a.name + "柱：" + this.a.getStore() +
                    "		" + this.c.name + "柱：" + this.c.getStore() +
                    "		" + this.b.name + "柱：" + this.b.getStore() + "			");
        }

    }

    // 执行第二部移动
    private void move2(HanoiPillar a, HanoiPillar b) {
        if (a.arr.size() == 0) { // a柱为空，则将b上层的盘子移到a
            list();
            b.moveTo(a);
            this.step--;
        } else if (b.arr.size() == 0) { // b柱为空，则将a上层的盘子移到b
            list();
            a.moveTo(b);
            this.step--;
        } else if (a.getDiskSize() > b.getDiskSize()) { // 由于b盘子小于a盘子，所以将b的top盘子移动到a的top盘子
            list();
            b.moveTo(a);
            this.step--;
        } else { // 由于a盘子小于b盘子，所以将a的top盘子移动到b的top盘子
            list();
            a.moveTo(b);
            this.step--;
        }
    }

    public static void main(String[] args) {
        Hanoi hanoi = new Hanoi();
        Hanoi.hanoi(3, "A", "B", "C");
    }
}

3.输出结果

1
2
3
4
5
6
7
8
A柱：1,2,3,		B柱：null		C柱：null       A -> C
A柱：2,3,		B柱：null		C柱：1,			    A -> B
A柱：3,		        B柱：2,		        C柱：1,			    C -> B
A柱：3,		        B柱：1,2,		C柱：null			A -> C
A柱：null		B柱：1,2,		C柱：3,			    B -> A
A柱：1,		        B柱：2,		        C柱：3,			    B -> C
A柱：1,		        B柱：null		C柱：2,3,		    A -> C
A柱：null		B柱：null		C柱：1,2,3,

四、汉诺塔问题改编（递归实现）

今天在做《程序员代码面试指南：IT名企算法与数据结构题目最优解（第二版）》时，遇到了一个稍微复杂一些的汉诺塔问题，但是理解之后发现本体只是在上面简易递归的基础上进行优化。

1.题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
【题目】
 *  汉诺塔问题比较经典，这里修改一下游戏规则：
 *  现在限制不能从最左侧的塔直接移动到最右侧，也不能从最右侧直接移动到最左侧，而是必须经过中间。
 *  求当塔有N层的时候，打印最优移动过程和最优移动总步数。
 *  1.如果希望从“左”移到“中”，打印“Move 1 from left to mid”。
 *  2.如果希望从“中”移到“左”，打印“Move 1 from mid to left”。
 *  3.如果希望从“中”移到“右”，打印“Move 1 from mid to right”。
 *  4.如果希望从“右”移到“中”，打印“Move 1 from right to mid”。
 *  5.如果希望从“左”移到“右”，打印“Move 1 from left to mid”和“Move 1 from mid to right”。
 *  6.如果希望从“右”移到“左”，打印“Move 1 from right to mid”和“Move 1 from mid to left”。
 *
 *  例如，当塔数为两层时，最上层的塔记为1，最下层的塔记为2，则打印：
 *  Move 1 from left to mid
 *  Move 1 from mid to right
 *  Move 2 from left to mid
 *  Move 1 from right to mid
 *  Move 1 from mid to left
 *  Move 2 from mid to right
 *  Move 1 from left to mid
 *  Move 1 from mid to right
 *  It wi11 move 8 steps.

2.情况分析

首先我们尝试使用递归方式实现，然后进行常见情况分析

  1. 假设剩余N层塔都在左，希望全都移到中，则有下面三个步骤
    1. 将1~N-1层从左移到右，该过程为递归
    2. 将N层从左移到中
    3. 将1~N-1层从右移到中，该过程为递归
  1. 假设剩余N层塔都是从中移到右，或者从中移到左，或者从有右到中，其实原理与情况1相同，所以不做赘述
  1. 假设剩余N层塔都在左，希望都移到右，则有下面五个步骤
    1. 将1~N-1层从左移到右，该过程为递归
    2. 将N层从左移到中
    3. 将1~N-1层从右移到左，此过程为递归
    4. 将N层从中移到右
    5. 将1~N-1层从左移到右，此过程为递归

3.实现主程序

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
34
35
36
37
38
39
40
41
42
43
44
45
public class Hanoi {

    public int hanoiProblem (int num, String left, String mid,
                              String right) {
        if (num < 1)
            return 0;
        return process(num, left, mid, right, left, right);
    }

    public int process(int num, String left, String mid, String right,
                       String from, String to) {
        if (num == 1) {
            if (from.equals(mid) || to.equals(mid)) {
                System.out.println("Move 1 from " + from + " to " + to);
                return 1;
            } else {
                System.out.println("Move 1 from " + from + " to " + mid);
                System.out.println("Move 1 from " + mid + " to " + to);
                return 2;
            }
        }
        if (from.equals(mid) || to.equals(mid)) {
            String another = (from.equals(left) || to.equals(left)) ? right : left;
            int part1 = process(num - 1, left, mid, right, from, another);
            int part2 = 1;
            System.out.println("Move " + num + " from " + from + " to " + to);
            int part3 = process(num - 1, left, mid, right, another, to);
            return part1 + part2 + part3;
        } else {
            int part1 = process(num - 1, left, mid, right, from, to);
            int part2 = 1;
            System.out.println("Move " + num + " from " + from + " to " + mid);
            int part3 = process(num - 1, left, mid, right, to, from);
            int part4 = 1;
            System.out.println("Move " + num + " from " + mid + " to " + to);
            int part5 = process(num - 1, left, mid, right, from, to);
            return part1 + part2 + part3 + part4 + part5;
        }
    }

    public static void main(String[] args) {
        Hanoi hanoi = new Hanoi();
        hanoi.hanoiProblem(3, "x", "y", "z");
    }
}

4.输出结果

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
Move 1 from x to y
Move 1 from y to z
Move 2 from x to y
Move 1 from z to y
Move 1 from y to x
Move 2 from y to z
Move 1 from x to y
Move 1 from y to z
Move 3 from x to y
Move 1 from z to y
Move 1 from y to x
Move 2 from z to y
Move 1 from x to y
Move 1 from y to z
Move 2 from y to x
Move 1 from z to y
Move 1 from y to x
Move 3 from y to z
Move 1 from x to y
Move 1 from y to z
Move 2 from x to y
Move 1 from z to y
Move 1 from y to x
Move 2 from y to z
Move 1 from x to y
Move 1 from y to z

五、汉诺塔问题改编（非递归实现）

1.题目分析

我们把左、中、右三个地点抽象成栈，依次记为LS、MS和RS。最初所有的塔都在LS上。那么如上4个动作就可以看作是：某一个栈（from）把栈顶元素弹出，然后压入到另一个栈里（to），作为这一个栈（to）的栈顶。

例如，如果是7层塔，在最初时所有的塔都在LS上，LS从栈顶到栈底就依次是1～7，如果现在发生了“左”到“中”的动作，这个动作对应的操作是LS栈将栈顶元素1弹出，然后1压入到MS栈中，成为MS的栈顶。其他操作同理。

一个动作能发生的先决条件是不违反小压大的原则。
from栈弹出的元素num如果想压入到to栈中，那么num的值必须小于当前to栈的栈顶。还有一个原则不是很明显，但也是非常重要的，叫相邻不可逆原则，解释如下：

  1. 我们把4个动作依次定义为：L-＞M、M-＞L、M-＞R和R-＞M。
  2. 很明显，L-＞M和M-＞L过程互为逆过程，M-＞R和R-＞M互为逆过程。
  3. 在修改后的汉诺塔游戏中，如果想走出最少步数，那么任何两个相邻的动作都不是互为逆过程的。举个例子：如果上一步的动作是 L-＞M，那么这一步绝不可能是 M-＞L，直观地解释为：你在上一步把一个栈顶数从“左”移动到“中”，这一步为什么又要移回去呢？这必然不是取得最小步数的走法。同理，M-＞R动作和R-＞M动作也不可能相邻发生。

有了小压大和相邻不可逆原则后，可以推导出两个十分有用的结论–非递归的方法核心结论：

  1. 游戏的第一个动作一定是L-＞M，这是显而易见的。
  2. 在走出最少步数过程中的任何时刻，4个动作中只有一个动作不违反小压大和相邻不可逆原则，另外三个动作一定都会违反。

对于结论2，现在进行简单的证明。
因为游戏的第一个动作已经确定是L-＞M，则以后的每一步都会有前一步的动作。

假设前一步的动作是L-＞M：
  1. 根据小压大原则，L-＞M的动作不会重复发生。
  2. 根据相邻不可逆原则，M-＞L的动作也不该发生。
  3. 根据小压大原则，M-＞R和R-＞M只会有一个达标。
假设前一步的动作是M-＞L：
  1. 根据小压大原则，M-＞L的动作不会重复发生。
  2. 根据相邻不可逆原则，L-＞M的动作也不该发生。
  3. 根据小压大原则，M-＞R和R-＞M只会有一个达标。
假设前一步的动作是M-＞R：
  1. 根据小压大原则，M-＞R的动作不会重复发生。
  2. 根据相邻不可逆原则，R-＞M的动作也不该发生。
  3. 根据小压大原则，L-＞M和M-＞L只会有一个达标。
假设前一步的动作是R-＞M：
  1. 根据小压大原则，R-＞M的动作不会重复发生。
  2. 根据相邻不可逆原则，M-＞R的动作也不该发生。
  3. 根据小压大原则，L-＞M和M-＞L只会有一个达标。

综上所述，每一步只会有一个动作达标。那么只要每走一步都根据这两个原则考查所有的动作就可以，哪个动作达标就走哪个动作，反正每次都只有一个动作满足要求，按顺序走下来即可

2.实现主程序

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class Hanoi {

    public int hanoiProblem(int num, String left, String mid, String right) {
        Stack<Integer> lS = new Stack<>();
        Stack<Integer> mS = new Stack<>();
        Stack<Integer> rS = new Stack<>();
        // 初始化这四个栈，可以避免栈溢出问题，同时可以使while循环中的四个函数无论谁在前，都必定会限制性 l -> m
        lS.push(Integer.MAX_VALUE);//最大值：2147483647(2的7次方-1)
        mS.push(Integer.MAX_VALUE);
        rS.push(Integer.MAX_VALUE);
        for (int i = num; i > 0; i--) {//将数字(最小数字在栈顶)压入左栈[1,2,3]
            lS.push(i);
        }
        //调用枚举，记录上一步操作 创建一个数组而不是直接创建一个Action对象是为了使用引用传递而不是值传递
        Action[] record = {Action.No};
        int step = 0;
        //size();stack类从vector继承的方法；返回此向量中的组件数
        while (rS.size() != num + 1) {//当右栈未将数字全部存入时
            //按顺序移动,下面这四个函数顺序并不影响因为每次必定只会有一个函数是满足条件的
            step += fStackToStack(record, Action.MToL, Action.LToM, lS, mS, left, mid);
            step += fStackToStack(record, Action.LToM, Action.MToL, mS, lS, mid, left);
            step += fStackToStack(record, Action.RToM, Action.MToR, mS, rS, mid, right);
            step += fStackToStack(record, Action.MToR, Action.RToM, rS, mS, left, mid);
        }
        return step;
    }

    public static int fStackToStack(Action[] record,
                                    Action preNoAet,
                                    Action nowAct,
                                    Stack<Integer> fStack,
                                    Stack<Integer> tStack,
                                    String from,
                                    String to) {
        // fStack.peek() < tStack.peek() 必然可以保证 record[0] != nowAct 两条件互斥
        if (record[0] != preNoAet && fStack.peek() < tStack.peek()) {//发生移动且必须小的数字往大的数字上移动
            tStack.push(fStack.pop());//fStack 移动到 tStack 且删掉from的栈顶元素
            System.out.println("Move " + tStack.peek() + " from " + from + " to " + to);
            record[0] = nowAct;
            return 1;
        }
        return 0;
    }

    public static void main(String[] args) {
        Hanoi Hanoi = new Hanoi();
        int step = hanoi.hanoiProblem(3, "左", "中", "右");
        System.out.println("总共需要" + step + "步");
    }

    enum Action {
        No, // 无操作
        LToM, // 从左移到中
        MToL, // 从中移到左
        MToR, // 从中移到右
        RToM // 从右移到中
    }
}

3.输出结果

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
Move 1 from 左 to 中
Move 1 from 中 to 右
Move 2 from 左 to 中
Move 1 from 左 to 中
Move 1 from 中 to 左
Move 2 from 中 to 右
Move 1 from 左 to 中
Move 1 from 中 to 右
Move 3 from 左 to 中
Move 1 from 左 to 中
Move 1 from 中 to 左
Move 2 from 左 to 中
Move 1 from 左 to 中
Move 1 from 中 to 右
Move 2 from 中 to 左
Move 1 from 左 to 中
Move 1 from 中 to 左
Move 3 from 中 to 右
Move 1 from 左 to 中
Move 1 from 中 to 右
Move 2 from 左 to 中
Move 1 from 左 to 中
Move 1 from 中 to 左
Move 2 from 中 to 右
Move 1 from 左 to 中
Move 1 from 中 to 右
总共需要26步

参考视频
https://www.bilibili.com/video/av31023017?from=search&seid=15595573244367663980

参考文章
https://blog.csdn.net/weixin_42636076/article/details/81031580
https://www.jb51.net/article/128701.htm