一．起源：
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
二．抽象为数学问题：
如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数
解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| （1）n == 1
第1次 1号盘 A---->C sum = 1 次
(2) n == 2
第1次 1号盘 A---->B
第2次 2号盘 A---->C
第3次 1号盘 B---->C sum = 3 次
（3）n == 3
第1次 1号盘 A---->C
第2次 2号盘 A---->B
第3次 1号盘 C---->B
第4次 3号盘 A---->C
第5次 1号盘 B---->A
第6次 2号盘 B---->C
第7次 1号盘 A---->C sum = 7 次
|
三．算法分析（递归算法）
求解汉诺塔问题最简单的算法还是通过递归算法，递归就是自己是一个方法或者说是函数，但是在自己这个函数里有调用自己这个函数的语句，而这个调用怎么才能调用结束呢？，这里还必须有一个结束点，或者具体的说是在调用到某一次后函数能返回一个确定的值，接着倒数第二个就能返回一个确定的值，一直到第一次调用的这个函数能返回一个确定的值。
实现这个算法可以简单分为三个步骤：
1
2
3
4
5
| （1） 把n-1个盘子由A 移到 B；
（2） 把第n个盘子由 A移到 C；
（3） 把n-1个盘子由B 移到 C；
|
算法实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| /**
* 汉诺塔递归程序
* level:当前移动的层数
* from:移动开始点
* pass:中间辅助点
* to:移动目标位置
**/
function hanoi(level,from,pass,to){
/**
* 移动递归主函数
* level:当前移动的层数
* from:移动开始点
* pass:中间辅助点
* to:移动目标位置
**/
function move(level,from,pass,to){
if(level === 1){
moveConsole(1,from,to);
}else{
move(level-1,from,to,pass);
moveConsole(level,from,to);
move(level-1,pass,from,to);
}
}
/**
* 移动打印
* id:当前移动的盘子
* from:移动开始点
* to:移动目标位置
**/
function moveConsole(id,from,to){
console.log(`第${++num}次移动，将${id}号盘${from}->${to}`);
}
let num = 0;//移动次数
move(level,from,pass,to);//开始移动
console.log(`${level}层汉诺塔共移动${num}次`);
}
|
