简介
汉诺塔(Tower of Hanoi)源于印度传说中,大梵天创造世界时造了三根金钢石柱子,其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
分析
我们先将问题简单化,如果有两个盘子的话把1号盘先移到b柱,再把2号盘移到c柱,最后把b柱上的1号盘移到c柱就行了。
那么我们先把上方的63个盘子看成整体,这下就等于只有两个盘子,自然很容易了,我们只要完成两个盘子的转移就行了
下面我用图来描述64个盘子的转移流程
代码实现
package com.zyp.arithmetic; /** * 汉诺塔问题 * 使用分治算法思想 * @author zyp * @create 2022/4/4 */ public class HanROMTower { public static void main(String[] args){ hanROMTowerQuestion(5,'A','B','C'); } /** * 汉诺塔问题 * @param num 个数 * @param a 柱子A * @param b 柱子B * @param c 柱子C */ public static void hanROMTowerQuestion(int num , char a, char b, char c){ if(num == 1){ System.out.println("第"+num+"个汉罗塔,从"+a+"->"+c); }else{ //超过一个将将,汉罗塔分成两部分,最后一个为一部分,其余的为另一部分 //1。先将除了最后一个的的部分移动到b hanROMTowerQuestion(num-1,a,c,b); //2.将最后一个移动到c System.out.println("第"+num+"个汉罗塔,从"+a+"->"+c); //3.将b中的部分再移动到c hanROMTowerQuestion(num-1,b,a,c); } } }