12、数据结构和算法 - 实战：递归-汉若塔游戏
1.1 汉诺塔
汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。在线游戏地址：http://ertong.973.com/p114895
汉诺塔游戏，玩法如下:
1、 有三根杆子A,B,CA杆上有若干碟子；
2、 每次移动一块碟子,小的只能叠在大的上面；
3、 把所有碟子从A杆全部移到C杆上；
1.2 思路分析
n是盘子的数量#
-
n == 1
-
第1次 1号盘 A---->C sum = 1 次
-
n == 2
-
第1次 1号盘 A---->B
-
第2次 2号盘 A---->C
-
第3次 1号盘 B---->C sum = 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 次
-
n == 4
-
第1次 1号盘 A–>B
-
第2次 2号盘 A–>C
-
第3次 1号盘 B–>C
-
第4次 3号盘 A–>B
-
第5次 1号盘 C–>A
-
第6次 2号盘 C–>B
-
第7次 1号盘 A–>B
-
第8次 4号盘 A–>C
-
第9次 1号盘 B–>C
-
第10次 2号盘 B–>A
-
第11次 1号盘 C–>A
-
第12次 3号盘 B–>C
-
第13次 1号盘 A–>B
-
第14次 2号盘 A–>C
-
第15次 1号盘 B–>C sum = 15 次
算法分析#
-
总结规律
1个圆盘的次数 2的1次方减1
2个圆盘的次数 2的2次方减1
3个圆盘的次数 2的3次方减1
4个圆盘的次数 2的4次方减1
…
n个圆盘的次数 2的n次方减1
故：移动次数为：2^n - 1 -
算法分析
-
现在有A柱子上有三个盘子，分别为1号，2号，3号。当我们有三个盘子的时候，我们把1号和2号看成一个整体，其实现在要移动1号和2号的时候，又回到了只有两个盘子的时候，所以，我们就得出结论，无论有多少个盘子，我们只需要看成一个整体，然后在分步骤解决两个盘子。
1.2 JAVA汉若塔游戏实现
汉若塔移动公式：F(n) = F(n-1) + 1 + F(n-1) 简化： F(n) = 2F(n-1) + 1
package com.yuanxw.datastructure.chapter12;
/**
* 汉若塔游戏
* 游戏地址：http://ertong.973.com/p114895
*/
public class HanoiTowerExample {
private static long moveCount = 0;
public static void main(String[] args) {
int number = 4;
move(number, 'A', 'B', 'C');
System.out.println(String.format("结果计算：【%s】盘子共需要移动【%s】步骤", 5, moveCount));
}
/**
* 汉若塔移动方法
* 思路：
* 1.假设 number == 1 时，移动步骤：【a=>c】
* 2.假设 number == 2 时，移动步骤：【a=>b】、【a=>c】、【b=>c】
* ...
* 3.似设 number == n时，移动步骤：【n-1 => b】、【n => c】、【n-1 => c】
* <p>
* <p>
* 公式：F(n) = F(n-1) + 1 + F(n-1) 简化： F(n) = 2F(n-1) + 1
* f：函数
* n：n层盘子
*
* @param number
* @param a
* @param b
* @param c
*/
public static void move(int number, char a, char b, char c) {
// 统计移动的次数
moveCount++;
if (number == 1) {
System.out.println(String.format("第1个盘子，移动：%s->%s", a, c));
} else {
move(number - 1, a, c, b);
System.out.println(String.format("第%s个盘子，移动：%s->%s", number, a, c));
move(number - 1, b, a, c);
}
}
}
执行结果：
第1个盘子，移动：A->B
第2个盘子，移动：A->C
第1个盘子，移动：B->C
第3个盘子，移动：A->B
第1个盘子，移动：C->A
第2个盘子，移动：C->B
第1个盘子，移动：A->B
第4个盘子，移动：A->C
第1个盘子，移动：B->C
第2个盘子，移动：B->A
第1个盘子，移动：C->A
第3个盘子，移动：B->C
第1个盘子，移动：A->B
第2个盘子，移动：A->C
第1个盘子，移动：B->C
结果计算：【5】盘子共需要移动【15】步骤