JavaSE递归求解汉诺塔
渡上舟(每天都要坚持学习鸭) 人气:01. 汉诺塔的介绍和玩法
汉诺塔(Tower of Hanoi),又称河内塔,是一个源于印度古老传说的益智玩具。
一共有3根柱子(A、B、C),A柱子由下到上放着由大到小的盘子,我们需要将A柱子上的盘子移到C柱子上,每次只能移动一个盘子,且在任意一次移动中,大盘子都必须处于小盘子下方。
2. 汉诺塔问题的思路
若A柱子上只有1个盘子,只需要移动1步:A->C
若A柱子上有2个盘子,需要移动3步:A->B,A->C,B->C
此时需要借助B柱子,才能将A柱子的盘子移到C柱子上。
那么若A柱子上有3个盘子,会怎么移动呢?
思路:此时,A为起始位置,B为中转位置,C为最终位置。我们需要将A柱子最上面的两个盘子先想办法移到中转位置B柱子上,然后将A柱子最下面的那个盘子移动到C柱子上,最后再将B柱子上面的盘子想办法移动到C柱子上。
将A柱子最上面的两个盘子想办法移到B柱子上:那对于这两个盘子来说,A是起始位置,B是最终位置,C是中转位置,需要借助C将A上的两个盘子移动到B上。具体移法:要先将A柱子最上面的一个盘子移动到中转位置C上,然后将A柱子上下面那个盘子移到最终位置B柱子上,最后将C柱子上的盘子移到B柱子上。
将B柱子上面的盘子想办法移动到C柱子上:那对于B柱子上的这两个盘子来说,B为起始位置,A为中转位置,C为最终位置,需要借助A将B上的两个盘子移动到C上。具体移法:要先将B柱子最上面的一个盘子移动到中转位置A上,然后将B柱子上下面那个盘子移到最终位置C柱子上,最后将A柱子上的盘子移到C柱子上。
所以,最终三个盘子的移动路径是 A->C,A->B,C->B,A->C,B->A,B->C,A->C,需要移动7步
网上找的动图,更易于理解
那么A柱子上有n个盘子时,该怎么移动呢?
以此类推,先将A柱子上面n-1个盘子想办法移到B柱子上,然后将A柱子上最后一个盘子移动到C柱子上,最终再将B柱子上的n-1个盘子想办法移到C柱子上。 想办法:其实就是柱子上有n-1个盘子,该怎么移动这个问题。
所以汉诺塔问题用递归实现最好解决。
3. 用递归的代码实现
public class HanoiGame { /* * 第一个参数用来放给的盘子数, *第二个参数用来放起始位置 *第三个参数用来放中转位置 *第四个参数用来放最终位置 * */ public static void hanoi(int n,char pose1,char pose2,char pose3){ // 3 'A' 'B' 'C' if(n == 1){ move(pose1,pose3);//若只有一个盘子,只需从起始位置移到最终位置这1步。 // 这里的pose1不一定等于'A',pose3不一定等于'C';随着递的次数的不一样,对应不同的值。 return; } hanoi(n-1,pose1,pose3,pose2);//这n-1个盘子是要借助 C 移动到 B 上的。 //所以 对于这n-1个盘子来说,起始位置是'A',中转位置是'C',最终位置是'B' move(pose1,pose3); hanoi(n-1,pose2,pose1,pose3); } /* * 第一个参数用来放起始位置 * 第二个参数用来放最终位置 */ public static void move(char pose4,char pose5){ System.out.println(pose4+" -> "+ pose5); } public static void main(String[] args) { hanoi(3,'A','B','C'); } }
总结
加载全部内容