2022.6.24

目录

1.什么是汉诺塔？

 2.如何去思考汉诺塔

（1）假设只有1个圆盘

（2）假设有2个圆盘

（3）假设有3个圆盘

 （4）假设有n个圆盘

3.代码实现

（1）模拟移动

（2）递归汉诺塔

1.什么是汉诺塔？

 2.如何去思考汉诺塔

目的：把圆盘从一个柱子挪到另一个柱子

要求：

1.一次只能挪动一个圆盘

2.大圆盘不能放在小圆盘上面

我们现在来结合目的与要求来思考一下如何挪动（由A->C）

（1）假设只有1个圆盘

 我们只需要A-->C即可

（2）假设有2个圆盘

 我们会发现不能直接从A挪到C了，我们需要借助B来挪动

A->B

A->C

 B->C

 至此，我们就实现了挪动

（3）假设有3个圆盘

 A->C  A->B

C->B  A->C 

B->A   

 B->C  A->C结束

 （4）假设有n个圆盘

我们在上面几个例子中可以发现，无论是几个圆盘，我们都需要先将最后一个圆盘上面的挪到B上，然后在将最后一个圆盘挪到C上

也就是说：我们如果要挪动n个圆盘，就需要先将上面的n-1个圆盘经过C来挪到B上，然后再把第n个圆盘挪到C上。然后我们需要将在B上的n-2个圆盘经过C挪到A上，然后把第n-1个圆盘挪到C上.....以此类推

以下为图解

 

 

 我们把第n个圆盘挪到C之后，只需要把n-1个圆盘也挪到C就可以完成了。

那么我们如何把剩下的n-1个挪到C上呢？

我们可以参考上面的方法来挪动

 

 以此类推

3.代码实现

（1）模拟移动

pos1为起始位置，pos2为挪动后的位置

（2）递归汉诺塔

 我们了解思想之后，写出完整代码

public class hannoi {
    public static void move (char pos1, char pos2) {
        System.out.println(pos1+"->"+pos2);
    }

    
    public static void hanNoi(int n, char pos1, char pos2, char pos3) {
        if(n==1){
            move(pos1,pos3);//只有一个盘子，直接从A挪到C
        }else{
            hanNoi(n-1,pos1,pos3,pos2);//先把n-1个盘子从A经过C挪到B
            move(pos1,pos3);//把第n个盘子从A挪到C
            hanNoi(n-1,pos2,pos1,pos3);//把剩下的n-1个盘子从B经过A挪到C
        }
    }
    public static void main(String[] args) {
        hanNoi(3,'A','B','C');
    }
}