前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神的书让我对算法有了新的感悟认识！

问题介绍

原问题
给定整数n作为圆盘个数，现在需要将n个圆盘从左边移动到右边，注意，不能从左边直接到右边，一次只能走一步，打印最优轨迹

解决方案

方案一：递归方式
1、将倒数第二个盘及以上盘作为一个整体，问题就简化成了2个盘的问题了，整体移动使用递归即可，非常简单
方案二：栈方式
首先每一轮都只有四种选择走法：
* 1、左-中、中-左、中-右、右到中
* 2、每一个状态都面临上面四种抉择
* 3、四种抉择中通过以下2条定律就能够筛选出能够使用的唯一那条路
* a)移动不违反大压小原则，需要过去的圆盘不能比目标栈的栈顶大
* b)相邻不可逆：如果前一个动作是左-中，那么下一个动作一定不是中-左，并且不可能重复上一个步骤（违反大压小）
* 总结：任何时刻，四个动作都只有一个满足ab原则，剩下三个一定违反原则
方案三：DP版本请看另一篇文章~

代码编写

java语言版本

方案一

public class HannioTower {
    /**
     * 入口函数
     * @param num 汉诺塔数量
     * @param left 左边：可以是字符串
     * @param mid 中间
     * @param right 右边
     * @param from 起点
     * @param to 终点
     * @return
     */
    public int hanioProblem(int num, String left, String mid, String right, String from, String to){
        if(num < Constants.NUM_1){
            return Constants.NUM_0;
        }
        return this.process(num, left, mid, right, from, to);
    }
    
    /**
     * 递归函数
     * @param num
     * @param left
     * @param mid
     * @param right
     * @param from
     * @param to
     * @return
     */
    private int process(int num, String left, String mid, String right, String from, String to){
        // 终止条件，就一个的时候为终止
        if(num == Constants.NUM_1){
            if(from.equals(mid) || to.equals(mid)){
                // 其中一个点是中间，则只需要一步即可
                System.out.println("Move 1 from :" + from + " to: " + to);
                // 返回步数
                return Constants.NUM_1;
            }else{
                // 都不是中点的情况移动两步，一定会经过中间
                System.out.println("Move 1 from :" + from + " to: " + mid);
                System.out.println("Move 1 from :" + mid + " to: " + to);
                return Constants.NUM_2;
            }
        }
        // 如果数量超过一个，则不是终止条件
        if(from.equals(mid) || to.equals(mid)){
            /**
             * 有一个是中间，分三步走：
             * 1、先移动num-1层到另外一边（交给递归）
             * 2、底层移动到目标
             * 3、num-1移动到目标（交给递归）
             */
            // 另一边一定是终点或者起点的对立面（其中有一个是mid）
            // 这个other作为对立面，总会存在from-other，from-mid,other-from,mid-to,from-to
            String other = (from.equals(left) || to.equals(left)) ? right : left;
            // num-1起点到对立面
            int part1StepNum = process(num-1, left, mid, right, from, other);
            // 最后一层到达目标
            System.out.println("Move " + num + " from :" + from + " to: " + to);
            int part2StepNum = Constants.NUM_1;
            // num-1起点到终点
            int part3StepNum = process(num-1, left, mid, right, other, to);
            return part1StepNum + part2StepNum + part3StepNum;
        }else{
            /**
             * 从一边到另外一边
             * 1、先移动num-1 到另外一边（递归）
             * 2、移动num到中间
             * 3、再移动num-1 到起点
             * 4、移动num到终点
             * 5、移动num-1到终点
             */
            // num-1层移动到终点
            int part1StepNum = process(num - 1, left, mid, right, from, to);
            // num移动到中间
            System.out.println("Move " + num + " from :" + from + " to: " + mid);
            int part2StepNum = Constants.NUM_1;
            // num-1移动到起点
            int part3StepNum = process(num -1, left, mid, right, to, from);
            // 移动num到终点
            System.out.println("Move " + num + " from :" + mid + " to: " + to);
            int part4StepNum = Constants.NUM_1;
            // 移动num-1到终点
            int part5StepNum = process(num -1, left, mid, right, from, to);
            return part1StepNum + part2StepNum + part3StepNum + part4StepNum + part5StepNum;
        }
    }
    /**
     * 测试用例
     * @param args
     */
    public static void main(String[] args) {
        HannioTower hannioTower = new HannioTower();
        hannioTower.hanioProblem(2, "left", "mid", "right", "left", "right");
    }
}

方案二：

public class HanoiTower {

    /**
     * 方法二：栈方式实现
     * 首先每一个盘都有四种选择走法
     * 1、左-中、中-左、中-右、右到中
     * 2、每一个状态都面临上面四种抉择
     * 3、四种抉择中通过以下2条定律就能够筛选出能够使用的唯一那条路
     *  a)移动不违反大压小原则，需要过去的圆盘不能比目标栈的栈顶大
     *  b)相邻不可逆：如果前一个动作是左-中，那么下一个动作一定不是中-左，并且不可能重复上一个步骤（违反大压小）
     * 总结：任何时刻，四个动作都只有一个满足ab原则，剩下三个一定违反原则
     * @param num
     * @param left
     * @param mid
     * @param right
     */
    public static int hanoiTower2(int num, String left, String mid, String right){
        Stack<Integer> lS = new Stack<>();
        Stack<Integer> mS = new Stack<>();
        Stack<Integer> rS = new Stack<>();
        // 盘底需要最大值
        lS.push(Integer.MAX_VALUE);
        mS.push(Integer.MAX_VALUE);
        rS.push(Integer.MAX_VALUE);
        // 先将圆盘放入到最左边的柱子上
        for (int i = num; i > 0; i--){
            lS.push(i);
        }
        // 上一个动作
        ActionEnum[] record = new ActionEnum[]{ActionEnum.NO};
        // 总步数
        int step = 0;
        // 每一次都是四种尝试
        while (rS.size() < num + 1){
            step += fStack2tStack(record, ActionEnum.M2L, ActionEnum.L2M, lS, mS, left, mid);
            step += fStack2tStack(record, ActionEnum.L2M, ActionEnum.M2L, mS, lS, mid, left);
            step += fStack2tStack(record, ActionEnum.R2M, ActionEnum.M2R, mS, rS, mid, right);
            step += fStack2tStack(record, ActionEnum.M2R, ActionEnum.R2M, rS, mS, right, mid);
        }
        return step;
    }

    /**
     * 判断走法
     * @param record
     * @param pre
     * @param now
     * @param fStack
     * @param tStack
     * @param from
     * @param to
     * @return
     */
    private static int fStack2tStack(ActionEnum[] record, ActionEnum pre, ActionEnum now, Stack<Integer> fStack, Stack<Integer> tStack, String from, String to) {
        if (record[0] != pre && fStack.peek() < tStack.peek()){
            System.out.printf("Move %d from %s to %s\n", fStack.peek(), from, to);
            tStack.push(fStack.pop());
            record[0] = now;
            return 1;
        }
        return 0;
    }
    /**
     * 测试用例
     * @param args
     */
    public static void main(String[] args) {
//        HanoiTower hanoiTower = new HanoiTower();
        // 两个盘从左边到右边
        HanoiTower.hanoiTower2(2, "left", "mid", "right");
    }
}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

方案一:中的思路就是递归的另一种看法，一种的栈的方式看递归，每一层都是一个状态，这种方式就是将问题变化为一个基本的步骤和一个整体的步骤，最基本的需要实现（最底部的盘的运动），剩下的看做一个整体（n-1个盘的运动），问题就简化成了两个盘的运动了。
方案二:
说实话，方案二是我根本想不到的方法，感谢左大神开拓思路，那么想一下为什么能想到这种办法呢？这种办法有什么原理呢？以后能解决什么类似的问题呢？悟一下是学习中最重要的环节！
回答1：首先方案一的递归会让人联想到栈，那么栈的思路就来了，这个我想过，但是不知道怎么实现。
回答2：重要的原理就是栈结构的进出规则类似于汉诺塔的进出规则！那么肯定要三个栈代表汉诺塔的三个柱子；这里感慨一下汉诺塔的空柱子和栈的最大的底Integer.MAX_VALUE的设计达到同样的效果，记住这个方法！；之后就是最难想的步骤，该如何制定逻辑能够走出正确的步伐，其实汉诺塔的最优解一定就只有一条路，并且这条路的每一步都有一个范围，那就是四种走法，然后往下尝试发现每一次四种走法都只有一种可以走！问题得到解答！
回答3：我觉得能够知道四种走法的时候问题就解决了一半，所以以后遇到最优解路径的问题时，可以尝试自己先走一下最优解，然后想一下为什么最优解在这一步的时候要这么走？不这么走会怎么样，从而产生出一个”原则“！也就是后面要形成的判断逻辑！

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可咨询2260755767@qq.com或在评论区回复即可.
再次感谢左大神的书对我算法的指点迷津！