亲宝软件园·资讯

展开

JavaSE递归求解汉诺塔

渡上舟(每天都要坚持学习鸭) 人气:0

1. 汉诺塔的介绍和玩法

汉诺塔(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');
    }
}

总结

加载全部内容

相关教程
猜你喜欢
用户评论