一，起源
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。 -
二，抽象为数学问题 汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
（1）n = 1时
第1次 1号盘 A---->C sum = 1 次
(2) n = 2时
-
| 语言 |
方法 |
| 8491 |
W57FU0HZgR |
| J2ppP |
直播带货 |
| 9536 |
2008-12-23 04:28:20 |
第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的1次方减1
2个圆盘的次数 2的2次方减1
3个圆盘的次数 2的3次方减1
。 。 。 。 。
n个圆盘的次数 2的n次方减1
故：移动次数为：2^n - 1
-
三．算法分析（递归算法）：
在利用计算机求汉诺塔问题时，必不可少的一步是对整个实现求解进行算法分析。到目前为止，求解汉诺塔问题最简单的算法通过递归来求，至于什么是递归，递归实现的机制是什么，简单点就是自己是一个方法或者是函数，但是在自己这个函数里有调用自己这个函数的语句，而这个调用怎么才能调用结束呢？，这里还必须有一个结束点，或者具体的说是在调用到某一次后函数能返回一个确定的值，接着倒数第二个就能返回一个确定的值，一直到第一次调用的这个函数能返回一个确定的值。
实现这个算法简单分为三个步骤：
（1）把n-1个盘子由A 移到 B
（2）把第n个盘子由 A移到 C
（3）把n-1个盘子由B 移到 C
不难发现，移到的步数必定为奇数步：
（1）中间的一步是把最大的一个盘子由A移到C上去
（2）中间一步之上可以看成把A上n-1个盘子通过借助辅助塔（C塔）移到了B上
（3）中间一步之下可以看成把B上n-1个盘子通过借助辅助塔（A塔）移到了C上
/** * n阶汉诺塔的移动步骤 * * @author meng * */
public class HanoiDemo {
private static int count = 0;
public static void main(String[] args) {
hanio(3,'x','y','z');
System.out.println(" 总共移动了 " + count + " 次" );
}
/** * 移动 * @param n 共需要移动的盘子 * @param x 从起始位置 * @param y 借助辅助塔 * @param z 移动到终止位置 */
public static void hanio(int n, char x, char y, char z) {
count++;
if(n==1) {
move(x,n,z);
}else {
hanio(n-1,x,z,y);
move(x,n,z);
hanio(n-1,y,x,z);
}
}
/** * 打印移动 * @param x 从起使位置 * @param n 移动第几个盘子 * @param y 要移动到的最终位置 */
private static void move(char x, int n, char y) {
System.out.println(" Move " + n + " from " + x + " to " + y);
}
}
结果预测：
Move 1 from x to z
Move 2 from x to y
Move 1 from z to y
Move 3 from x to z
Move 1 from y to x
Move 2 from y to z
Move 1 from x to z
总共移动了 7 次
|
