递归算法计算汉诺塔游戏移动方案

Valonia ·

更新时间:2024-11-10

· 992 次阅读

背景
闲来无事，想起来小时候玩的汉诺塔游戏。汉诺塔是将存放在A柱子上的8（可调整）个圆盘，挪移到C柱子上去
在这里插入图片描述

游戏规则
1、每次只能移动一个圆盘
2、大圆盘必须处于小圆盘的下方

核心算法
递归算法

核心思路
想要把8层汉诺塔从A位置挪移到C位置，需要拆解成以下三个步骤：
1、将上面7层移动到B位置
2、将第8层移动到C位置
3、将B位置的7层移动到C位置

这样就将8层汉诺塔，拆分成移动2次7层汉诺塔和一次A到C的圆盘移动；然后可以将7层汉诺塔移动再拆分成2次6层汉诺塔移动，直到0层汉诺塔移动；0层汉诺塔是无需移动的（递归算法的终止条件）

Java代码实现

/**
 - 汉诺塔游戏算法
 */
public class HanNuoTaGame {
    public static Integer stepNum = 1;//移动步数
    public static void main(String[] args) {
        System.out.println("游戏开始");
        HanNuoTaGame.hanNuoTa(6,"A","B","C");
        System.out.println("游戏结束");
    }
    /**
     * 汉诺塔迭代算法
     * @param level 层级（有多少层圆盘）
     * @param current 当前圆盘所在位置
     * @param targer 想要移动的目标位置
     * @param transfer 中转柱位置
     */
    public static void hanNuoTa(Integer level,String current,String targer,String transfer){
        /*
        * 汉诺塔游戏核心思想是一个迭代算法：
        * 圆盘是0个，即level=0时：无需移动
        * 圆盘是N时，即level=N时：
        * 1、将当前位N-1个圆盘移动到中转位置（递归算法）
        * 2、将第N个圆盘移动到目标位置
        * 3、将中转位的N-1个圆盘移动到目标位置（递归算法）
        */
        if(level == 0){
            //0级汉诺塔无需任何操作
        }else{
            //将当前位N-1个圆盘移动到中转位置（递归算法）
            hanNuoTa(level-1,current,transfer,targer);
            //将第N个圆盘移动到目标位置
            System.out.println("第" + stepNum + "步，移动方法："+current+" --> " + targer);
            stepNum ++;
            //将中转位的N-1个圆盘移动到目标位置（递归算法）
            hanNuoTa(level-1,transfer,targer,current);
        }
    }
}

运行结果
游戏开始
第1步，移动方法：A --> C
第2步，移动方法：A --> B
第3步，移动方法：C --> B
第4步，移动方法：A --> C
第5步，移动方法：B --> A
第6步，移动方法：B --> C
第7步，移动方法：A --> C
第8步，移动方法：A --> B
第9步，移动方法：C --> B
第10步，移动方法：C --> A
第11步，移动方法：B --> A
第12步，移动方法：C --> B
第13步，移动方法：A --> C
第14步，移动方法：A --> B
第15步，移动方法：C --> B
第16步，移动方法：A --> C
第17步，移动方法：B --> A
第18步，移动方法：B --> C
第19步，移动方法：A --> C
第20步，移动方法：B --> A
第21步，移动方法：C --> B
第22步，移动方法：C --> A
第23步，移动方法：B --> A
第24步，移动方法：B --> C
第25步，移动方法：A --> C
第26步，移动方法：A --> B
第27步，移动方法：C --> B
第28步，移动方法：A --> C
第29步，移动方法：B --> A
第30步，移动方法：B --> C
第31步，移动方法：A --> C
第32步，移动方法：A --> B
第33步，移动方法：C --> B
第34步，移动方法：C --> A
第35步，移动方法：B --> A
第36步，移动方法：C --> B
第37步，移动方法：A --> C
第38步，移动方法：A --> B
第39步，移动方法：C --> B
第40步，移动方法：C --> A
第41步，移动方法：B --> A
第42步，移动方法：B --> C
第43步，移动方法：A --> C
第44步，移动方法：B --> A
第45步，移动方法：C --> B
第46步，移动方法：C --> A
第47步，移动方法：B --> A
第48步，移动方法：C --> B
第49步，移动方法：A --> C
第50步，移动方法：A --> B
第51步，移动方法：C --> B
第52步，移动方法：A --> C
第53步，移动方法：B --> A
第54步，移动方法：B --> C
第55步，移动方法：A --> C
第56步，移动方法：A --> B
第57步，移动方法：C --> B
第58步，移动方法：C --> A
第59步，移动方法：B --> A
第60步，移动方法：C --> B
第61步，移动方法：A --> C
第62步，移动方法：A --> B
第63步，移动方法：C --> B
游戏结束
作者：*任逍遥*

汉诺塔游戏汉诺塔递归算法递归算法

1024 个赞