汉诺塔问题的Java实现（递归与非递归）

文章目录

汉诺塔问题的Java实现（递归与非递归）

一、汉诺塔问题描述

汉诺塔问题就是有三张柱子A、B、C，然后初始化在A上放了N个圆盘，圆盘按照小压大的方式堆放，需要用最少的步骤从A柱子上挪到C柱子上。在整个移动的过程中，也必须保持小压大的规则。
如下图所示，需要把A上的四个圆盘挪到C上。
在这里插入图片描述

二、汉诺塔解题思路

假设A上面有N个圆盘，我们可以把每个圆盘的直径看作是N，那从最下面开始数：盘子直径是N，N-1，N-2，…,2,1
因为到目标柱子C后还需要维持小压大的规则，那第一个到达C柱子的圆盘肯定是最大的圆盘,也就是直径为N的圆盘，那剩下的圆盘(1到N-1)在哪里呢，都在过渡柱子B上。
按照这个逻辑，C上每次放一个除了C上面的圆盘外，最大的圆盘，然后其余的圆盘按照小压大的逻辑放在过度柱子上（有可能是A，也有可能是B）。
由上面可以看出，C上放一个除它外最大圆盘的逻辑是，先从堆满圆盘的柱子上转移圆盘，只剩下一个，然后把这一个圆盘挪到C上。

三、递归

递归思路很符合上面的思路，一共有三个柱子，from、to、temp，先从from move n-1个圆盘到temp，然后从from move第N个给 to，最后从temp上面把剩余圆盘转移给to。

        public static void hanoi(int n) {
            if (n > 0) {
                func(n, "A", "C", "B");
            }
        }

        private static void func(int n, String from, String to, String other) {
            if (n == 1) {
                System.out.println("move 1 from " + from + " to " + to);
            } else {
                func(n - 1, from, other, to);
                System.out.println("move " + n + " from " + from + " to " + to);
                func(n - 1, other, to, from);
            }
        }

四、非递归

        static class HanoiRecord {
            int index;//代表盘子的序号
            int n;
            String from;
            String to;
            String other;

            public HanoiRecord(int index, int n, String from, String to, String other) {
                this.index = index;
                this.n = n;
                this.from = from;
                this.to = to;
                this.other = other;
            }
        }

        public static void hanoi3(int n) {
            hanoiNonRecursion(n, "A", "C", "B");

        }


        private static void hanoiNonRecursion(int n, String A, String C, String B) {
            if (n < 1) return;

            Stack<HanoiRecord> stack = new Stack<>();
            stack.push(new HanoiRecord(n, n, A, C, B));
            while (!stack.isEmpty()) {
                HanoiRecord pop = stack.pop();
                if (pop.n == 1) {
                    move(pop.index, pop.from, pop.to);
                } else {
                    //栈是先进后出的，所以和递归的处理逻辑相反，先把temp到to进栈
                    stack.push(new HanoiRecord(pop.n - 1, pop.n - 1, pop.other, pop.to, pop.from));
                    stack.push(new HanoiRecord(pop.n, 1, pop.from, pop.to, pop.other));
                    stack.push(new HanoiRecord(pop.n - 1, pop.n - 1, pop.from, pop.other, pop.to));
                }

            }
        }

        private static void move(int index, String from, String to) {
            System.out.println("move " + index + " from " + from + " to " + to);
        }