Java汉诺塔问题（超级详细题解！！！）

问题描述 

如图所示，汉诺塔问题是有三个柱子，和n个大小不一样的块组成，把这些块从A位置 挪动 C位置，且小的块，必须在大的块上面。每次只能挪动一个块。 

 解题思路：

我们通过递归把复杂问题简单化，上述汉诺塔看成叠盘子
 n = 1   =>  move(1,a,b,c); 直接把a的盘子 -> c柱子
 n = 2   =>  move(2,a,b,c); 分解为：move(1,a,c,b) , move(1,a,b,c);
 n = 3   =>  move(3,a,b,c); 分解为：move(2,a,c,b) , move(1,a,b,c) , move(2,b,a,c);

在n=3的时候move(2,a,c,b) 表示把n-1个盘子放到b柱子上，因为每次只能挪动一个盘子所以这里包含三个步骤：
{
    move(1,a,b,c);
    move(1,a,c,b);
    move(1,c,b,a);
}

move(2,b,a,c)包含{
    move(1,b,c,a);
    move(1,b,a,c);
    move(1,a,b,c);
}

这样下来递归也就出来，我们假设上半部分为一个整体也是n-1（但实际上还是每次只能挪动一块），最底下的那一个盘子是一个整体
推出===>
第一步：将a中前n-1个盘子借助c搬到b中  move(n-1,A,C,B)

第二步：将a中的"第"n个盘子搬到c中 借助b move(1,A,B,C)

第三步：将b中的n-1个盘子借助a搬到c中  move(n-1,B,A,C)

这样通过一层层递归就会变成我们上述分解的情况，也就是n为1的情况，一个一个盘子挪。
可以发现n=1情况下盘子都是直接挪动你想挪的位置


个人理解：

 其中把n-1个盘子看成整体挪像b柱子的时候，再将这n-1个盘子可以继续去分成两组去挪，这样自然就是划分成一个一个去挪了

案例代码： 

package com.jyy.test01;import java.util.Scanner;public class text003 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入一个整数：");int n = sc.nextInt();move(n,'A','B','C');}// n 表示块的总数，a-> 表示 第一个柱子(可以理解为初始柱子，也就是最开始的柱子)// b-> 表示第二个柱子 (可以理解为过渡柱子)// c -> 表示第三个柱子 （目标柱子）// 上述柱子不必太纠结，定义的字母，如果太过繁琐我们可以理解为普通的三个柱子，有一个初始柱子，一个过渡柱子，一个终点柱子// 这个过渡柱子是一定要有的，因为每次只能挪动一块，没有第三者的帮助我们始终是完不成的。（这就好比交换变量时候）   我们总会// 去使用一个temp 去做一个过渡。public static void move(int n,char a,char b,char c){//如果就一个块的话就不需要移动了if(n==1){System.out.println(a + "->" + c); // a柱子 挪到 c柱子}else{/** 把盘子分为上下两个部分，最底下是一部分，上面所有的盘子是一个部分，* 所以上面部分是（n-1）* 最底下部分是1* */move(n-1,a,c,b); // 把n-1个盘子从 a 挪到 b 借助 cSystem.out.println(a + "->" + c); // 把最下面的盘子从 a -> cmove(n-1,b,a,c); // 把n-1个盘子从b 挪到 c 借助 a}}
}

此题本人在代码中有很多注释帮助小伙伴，更好的理解汉诺塔问题，如果有错误的地方欢迎小伙伴留言，喜欢的 留个关注再走吧~