汉诺塔问题（进阶）--- 递归方法

【题目】
汉诺塔问题比较经典，这里修改一下游戏规则：现在限制不能从最左侧的塔直接移动到最右侧， 也不能从最右侧直接移动到最左侧，而是必须经过中间。求当塔有N层的时候，打印最优移动过程和最优移动总步数。 例如，当塔数为两层时，最上层的塔记为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 will moves 8 steps.

【要求】
用以下两种方法解决：
*方法一：递归的方法
*方法二：非递归的方法，用栈来模拟汉诺塔的三个塔。

【解答】
见源代码！

package pers.mao.stackAndQueue.demo_06;

/**
 * @author Mao Qingbo
 * @date 2020-10-04
 */
public class TowersOfHanoi1 {//递归方法
    public int hanoiProblem1(int num ,String left,String mid,String right){
        if(num<1){
            return 0;
        }
        return process(num,left,mid,right,left,right);//from-->left,to-->right
    }

    /**
     *
     * @param num 汉诺塔的层数
     * @param left 左塔
     * @param mid 中塔
     * @param right 右塔
     * @param from 出发塔
     * @param to 目标塔
     * @return 返回步数
     */
    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;
            }
        }
        /*
         * 递归情形：有N层塔需要移动（从上到下依次为1~N）
         * 如果，出发塔和目标塔中的一个是中塔，那么需3步走：
         *   1）将1~N-1层从出发塔移动到辅助塔（another）；
         *   2）将第N层从出发塔移动到目标塔；
         *   3）将1~N-1层从辅助塔（another）移动到目标塔。
         * 否则，需要5步走：
         *   1）将1~N-1层从出发塔移动到目标塔塔；
         *   2）将第N层从出发塔移动到中塔；
         *   3）将1~N-1层从目标塔移动到出发塔；
         *   4）将第N层从中塔移动到目标塔；
         *   5）将1~N层从出发塔移动到目标塔。
         */
        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;
        }
    }

}