一、汉诺塔的背景故事
在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。 印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片，一次只移动一片，不管在哪根针上，小片必在大片上面，该怎样移动呢？
二、找规律
当一个金片时
当二个金片时
当三个金片时
当四个金片时
三、了解什么是递归
一个方法在执行过程中调用自身, 就称为 “递归”.
递归相当于数学上的 “数学归纳法”, 有一个起始条件, 然后有一个递推公式.
例如, 我们求 N!
起始条件: N = 1 的时候, N! 为 1. 这个起始条件相当于递归的结束条件.
递归公式: 求 N! , 直接不好求, 可以把问题转换成 N! => N * (N-1)!
递归的必要条件：
- 将原问题划分成其子问题，注意：子问题必须要与原问题的解法相同
- 递归出口
四、分析问题
当只有一个金片时，直接将A中的金片移动到C，也就是递归的出口，
通过观察发现：
前n-1个金片都需要借助C移动到B（如：当有两个金片时的第2步；当有三个金片时的第4步）
然后将第n个金片移动到C（如：当有两个金片时的第3步；当有三个金片时的第5步）
最后将B上的n-1个金片借助A移动到C（如：当有两个金片时的第4步；当有三个金片时的第8步）
五、核心思想
假设总共需要移动n个盘子
1.将A柱上的n-1个盘子借助C柱移向B柱
2.将A柱上仅剩的最后一个盘子移向C柱
3.将B柱上的n-1个盘子借助A柱移向C柱
六、代码实现
public static void move(char pos1,char pos2) { System.out.print(pos1+"->"+pos2+" "); } public static void hanio(int n,char pos1,char pos2,char pos3) { if (n == 1) { move(pos1,pos3); return; } hanio(n - 1, pos1, pos3, pos2); move(pos1, pos3); hanio(n - 1, pos2, pos1, pos3); }
七、完整代码
//汉诺塔 //5.代码实现的思路主要分为三步： //假设总共需要移动n个盘子 //1.将A柱上的n-1个盘子借助C柱移向B柱 //2.将A柱上仅剩的最后一个盘子移向C柱 //3.将B柱上的n-1个盘子借助A柱移向C柱 public class Test1 { public static void move(char pos1,char pos2) { System.out.print(pos1+"->"+pos2+" "); } public static void hanio(int n,char pos1,char pos2,char pos3) { if (n == 1) { move(pos1,pos3); return; } hanio(n - 1, pos1, pos3, pos2); move(pos1, pos3); hanio(n - 1, pos2, pos1, pos3); } public static void main(String[] args) { hanio(2,'A','B','C'); System.out.println(); hanio(3,'A','B','C'); System.out.println(); hanio(4,'A','B','C'); } }
运行结果
个人感想：汉诺塔问题太抽象了，很难理解，我也是看了很多的讲解，自己理解的也不是很深刻，如果看本篇文章，建议多看几遍，自己动手画画，或者可以结合讲解视频很好理解
创造不易，如果本篇对你有所帮助，请给我一个免费的赞！如有不同见解或者疑惑，欢迎在评论区留言！
