疫情当前，大家要做好防护哦。

带好口罩了嘛？

每日一练，锻炼思维

汉诺塔

    

💬 汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。 大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。 并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。 问应该如何操作？

   

🔴 思路解读

   

💠 任务1：确定n的值，if(n==1),只有A->C一种情况，else进行任务2

   

💠 任务2：确定三大子任务和盘子的起始位置，中转位置和结束位置

   

💠 子任务1：我必定会将n个盘子中的n-1个盘子放到B盘(A盘只剩下一个)，这样我才能将A盘的最后一个最大的盘子放到C去。

    

举例 n=3，子任务1将会执行

• A盘(顶层)->C盘
• A盘(中间)->B盘
• C盘(顶层)->B盘(中间+顶层)

   

🔻 注意

      当n更大时，我们子任务1移动的顺序和次数会更加复杂，但是总目标不变，就是将A盘上面除去最后一个盘的所有盘（n-1）放到B盘上面，到这里我们的子任务1就执行完了。

      

💠 子任务2：A盘的上面经过执行任务1已经没有盘子了(盘子都在B盘),我们现在的总任务就是将A盘(底层)移动到C盘(底层)

     

举例 n=3，执行完子任务1后

• A盘(底层)->C盘

     

💠 子任务3: 此时A盘最大的盘到达了目标C盘，我们现在子任务3的总目标就是将B盘上的（n-1）个盘移到A盘，再将B盘最底下的转移到C上。

   

举例 n=3，执行完子任务1，2后

B(顶层)->A(底层)

B(底层)->C(顶层)

A(底层)->C(底层)

    

......接着就是调用子任务1,2,3反复执行直到将所有盘移动到C位置

   

🔻 注意

是不是感觉有点像，子任务1一样，将B盘上面移空，在将最大的放到目标盘C？没错是一样的，

• 子任务1的流程是 A-C-B（A是起始盘，C是中转盘，B目标盘）
• 子任务2的流程是 A-C(A是起始盘，C是目标盘)
• 子任务3的流程是 B-A-C(B是起始盘，A是中转盘，C目标盘)

   

代码解释： 

• 子任务1：hanio(n-1,post1,post3,post2);
• 子任务2：move(post1,post3);
• 子任务3：hanio(n-1,post2,post1,post3);

      

📝 代码展示

    

    /**     n      代表你的盘子数目     post1  盘子所在的起始位置     post2  盘子的中转位置     post3  盘子的结束位置    **/public class 汉诺塔 {    public static void main(String[] args) { // n 为 1 hanio(1,'A', 'B', 'C'); System.out.println(); // n 为 2 hanio(2,'A', 'B', 'C'); // n 为 3 System.out.println(); hanio(3,'A', 'B', 'C');    }    public static void move(char post1,char post2){ System.out.print(post1+"->"+post2+" ");    }    public static void hanio(int n,char post1,char post2,char post3){ if(n==1){     move(post1,post3); }else{     hanio(n-1,post1,post3,post2);     move(post1,post3);     hanio(n-1,post2,post1,post3); }    }}