JavaSE递归求解汉诺塔问题的思路与方法

Elita ·

更新时间:2024-11-10

· 1743 次阅读

1. 汉诺塔的介绍和玩法

2. 汉诺塔问题的思路

3. 用递归的代码实现

总结

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');
    }
}