©2020-2024 ioDraw All rights reserved
<>有趣的问题：
汉诺塔是一个比较抽象的问题,一定要去理解这个问题才能领略其中的奥妙：
汉诺塔（Tower of
Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
<>规则描述
有a,b,c这三个柱子,开始时,在a柱子上摆放着诺干个从下往上依次变小的盘子,
而我们要做的就是把这些有序的盘子遵循小盘子放在大盘子上面的原则,来将a柱子上的盘子全都挪放到c柱子上
<>找规律：
咱们先来看一个数量为三个盘子的汉诺塔问题找找规律
为了更清楚的看移动过程会将这三个盘子命名为1,2,3
咱们要遵循原则的将盘子从a柱移动到c柱,
那么要移动3时,a柱上一定就只有这一个盘子,且c柱上没有盘子,
否则就会违背原则;
即a柱上只有最大的盘子,
最大的盘子上面的盘子都遵循原则的移动到了b柱上,
移动过程1:
1.
a -> c
2.
a -> b
3.
c -> b
然后再移动3到c柱上
移动过程2:
a -> c
现在a柱上没有盘子,
最大的盘子3在c柱上,
其余的盘子都有序的坐落在b柱上;
那么我们现在要做的就是
将b柱上的所有盘子移动到c柱上,
等等,这句话是不是和我们最初的命题很相似啊?
最初命题:将a柱上的盘子全都挪放到c柱上,
当前任务:将b柱上的盘子全都挪放到c柱上,
咱们先保留这个疑问,继续完成三个盘子的汉诺塔,
移动过程3:
1.b -> a
移动过程4:
b -> c
移动过程5:
a -> c
那么三个盘子的汉诺塔命题就解决了;
因为要遵顼原则,所以一定要先将最大的,次大的,…最小的依次放到c柱上(最大的最先放在c柱上)
<>思考解决方法
假设,一共有n个盘子,
<>步骤一:
也就是说挪动最大的盘子时,要先将其他(n - 1)个盘子放到b柱上,(具体怎么放,这个问题比较抽象,咱们最后在做讨论),
然后再将最大的盘子,从a柱上移动到c柱上,
即 a -> c;
因为此时,最大的盘子在c柱上,
所以这个最大的盘子上放那个盘子都遵循原则,
因为他是最大的,其他盘子都没他大,
所以此时就可以忽略这个最大的盘子的存在了,
那么解决这个命题就变成了,将剩下的b柱上的(n - 1)个盘子放到c柱上,
<>步骤二:
第一步肯定是先将,
次大的盘子上的(n - 2)个盘子放到a柱上,
然后再将次大的盘子放到c柱上,
即 b -> c;
和上面一样,可以忽略最大的盘子与次大的盘子的存在了,
那么解决这个命题就变成了,
将剩下的a柱上的(n - 2)个盘子放到c柱上,
步骤与上述步骤原理相同,甚至可以直接令(n = n - 2)套用;
<>步骤三:
将次次大的盘子上的(n - 3)个盘子全都挪放到b柱上,(为了展示效果,又多画了一个盘子,大家不要看错了)
然后再将次次大的盘子放到c柱上,
即 a -> c;
和上面一样,可以忽略最大的盘子,次大的盘子和次次大的盘子的存在了,
那么解决这个命题就变成了,
将剩下的b柱上的(n - 3)个盘子放到c柱上,
<>步骤四:
次次次大的盘子上的(n - 4)个盘子放到a柱上,
然后再将次次次大的盘子放到c柱上,
即b -> c
和上面一样,可以忽略最大的盘子,次大的盘子,次次大的盘子和次次次大的盘子的存在了,
那么解决这个命题就变成了,将剩下的a柱上的(n - 4)个盘子放到c柱上,
.
.
.
.
.
.
大家观察
(步骤1和步骤2)是不是与(步骤3和步骤4)是不是一个循环,
他们除了数值不同,其他的做法,思想原理都是相同的,
所以就这样一次次的循环下去就可以解决汉诺塔问题了;
那么解决汉诺塔问题,是不是也将这一个大问题细分成了数个解决方法相同的小问题了呢? 这是不是很像我们的递归呢?
欸
那是不是应该用递归来解决汉诺塔呢?
有思路了,
这数个小问题的解决方法是什么呢?
循环1. 将起始柱上的大盘子之上的所有盘子,全都先存放在另一个柱子上(咱们称其为好人柱),然后将大盘子移动到c柱(目标柱)上;
循环2. 现在的问题就变成了将起始柱(上一个好人柱)上的(n - 1)个盘子移动到c柱上
一直循环1和2就可以解决汉诺塔问题了对不对?
是的,就是这样解决汉诺塔问题;
这里也就解决了上面当前任务与最初命题很相似的疑问,即他们完成了一个循环;
<>用代码实现
我们来用代码实现一下:
1.首先写一个移动方法;
public static void move(char pos1,char pos2) { System.out.print(pos1 + "->" +
pos2+" "); }
然后咱们来构造这个汉诺塔的方法
上述方法中,一共有四个变量,
1.盘子的数量:n
2.起始柱:pos1
3.好人柱(中间柱):pos2
4.目标柱:pos3
咱们先来剖析循环1;
起始柱肯定是a柱,
但是,咱们要先将起始柱a上最大盘子之上的(n - 1)个盘子放到好人柱b上,所以b柱既是好人柱,也是辅目标柱;
然后再将起始柱a上最大的盘子 放到c柱上主目标柱,
public static void Tower_of_Hanoi(int n,char pos1,char pos2,char pos3) { if(n
== 1) { move(pos1,pos3); return ; } Tower_of_Hanoi(n - 1,pos1,pos3,pos2); move(
pos1,pos3); Tower_of_Hanoi(n - 1,pos2,pos1,pos3); }
**咱们来剖析这个方法:
n是要移动的盘子数量,
递归的结束条件就是(n == 1)时,
将起始柱1上的唯一 一个盘子移动到主目标柱3上
根据咱们从传入move方法的数据来看,(传入的数据也可以改变,但是汉诺塔方法中的几个柱的位置也要相应的做出改变)
汉诺塔方法里的pos1是起始柱,pos3是目标柱,pos2是好人柱;**
(注意:pos1,pos2,pos3只是变量名,
在每次调用的时候里面存放的数据都是不同的,
咱们为了好区分接下来n后的第一个柱,称为1柱,第二个柱称为2柱,第三个柱称为3柱;)
即1柱是起始柱,3柱是目标柱,2柱是好人柱
循环1: 咱们第一步要做的是将起始柱1上的(n - 1)个盘子借助好人柱3放到辅目标柱2上(第6行代码)
然后将起始柱1上最大的那个盘子放到主目标柱3柱上(第7行代码)
循环2: 问题就变成了从起始柱2(辅目标柱)把剩下的(n - 1)个盘子放到(主目标柱)3上; 然后让递归来解决他即可
注意第6行代码与第7行代码去调用自身的时候
起始柱,好人柱,主辅目标柱都会改变;
**具体的移动过程是比较抽象的一个过程,
就是在递归中, 不断的通过递归去减少n的值,
去找到子问题的子问题…,
从而不断的改变起始柱,好人柱,主辅目标柱,
直到最后n == 1时,递归结束,
输出每个子问题的 起始柱 -> 主目标柱;
每一次递归都是一个单独的过程,所以时间复杂度与空间复杂度都很大;**
至此汉诺塔就讲解完了;
理解汉诺塔的两个要点就是
1.理解汉诺塔方法中一直去寻找子问题的子问题…的原理;
2.是理解汉诺塔方法每一次调用自己传进去的pos1,pos2,pos3中存放的数据的变化,从而保证可以解决汉诺塔问题;
今天关于汉诺塔的分享就到这里,如果大家有不同的见解,欢迎评论区一起讨论
为了诗和远方,仍在努力攀登这座雄伟的山峰