【无标题】

汉诺塔问题的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);
        }

类HanoiRecord里面的index可以不要,只是用来打印的而已。

上一篇:LeetCode学习


下一篇:【力扣学习计划】包含min函数的栈