| | 汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。
后来，这个传说就演变为汉诺塔游戏:
1.有三根杆子a,b,c。a杆上有若干碟子
2.每次移动一块碟子,小的只能叠在大的上面
3.把所有碟子从a杆全部移到c杆上
经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片：
如3阶汉诺塔的移动：a→c,a→b,c→b,a→c,b→a,b→c,a→c
此外，汉诺塔问题也是程序设计中的经典递归问题。
补充：汉诺塔的算法实现（c++）
#include <fstream>
#include <iostream>
using namespace std;
ofstream fout("out.txt");
void move(int n,char x,char y)
{
fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;
}
void hannoi(int n,char a,char b,char c)
{
if(n==1)
move(1,a,c);
else
{
hannoi(n-1,a,c,b);
move(n,a,c);
hannoi(n-1,b,a,c);
}
}
int main()
{
fout<<"以下是7层汉诺塔的解法:"<<endl;
hannoi(7,'a','b','c');
fout.close();
cout<<"输出完毕！"<<endl;
return 0;
}
c语言精简算法
/* copyrighter by ss7e */
#include<stdio.h> /* copyrighter by ss7e */
void hanoi(int n,char a,char b,char c) /* copyrighter by ss7e */
{
if(n==1)
{
printf("move disk %d from %c to %c
",n,a,c);
}
else
{
hanoi(n-1,a,c,b); /* copyrighter by ss7e */
printf("move disk %d from %c to %c
",n,a,c);
hanoi(n-1,b,a,c); /* copyrighter by ss7e */
}
}
main() /* copyrighter by ss7e */
{
int n;
printf("请输入数字n以解决n阶汉诺塔问题：
");
scanf("%d",&n);
hanoi(n,'a','b','c');
}/* copyrighter by ss7e */ | | 汉诺塔的由来
汉诺塔是源自印度神话里的玩具。
上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。
上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘。
汉诺塔与宇宙寿命
如果移动一个圆盘需要1秒钟的话，等到64个圆盘全部重新落在一起，宇宙被毁灭是什么时候呢？
让我们来考虑一下64个圆盘重新摞好需要移动多少次吧。1个的时候当然是1次，2个的时候是3次，3个的时候就用了7次......这实在是太累了
因此让我们逻辑性的思考一下吧。
4个的时候能够移动最大的4盘时如图所示。
到此为止用了7次。
接下来如下图时用1次，在上面再放上3个圆盘时还要用7次（把3个圆盘重新放在一起需要的次数）。
因此，4个的时候是
“3个圆盘重新摞在一起的次数”+1次+“3个圆盘重新摞在一起需要的次数”
=2x“3个圆盘重新摞在一起的次数”+1次
=15次。
那么，n个的时候是
2x“（n-1）个圆盘重新摞在一起的次数”+1次。
由于1 个的时候是1次，结果n个的时候为（2的n次方减1）次。
1个圆盘的时候 2的1次方减1
2个圆盘的时候 2的2次方减1
3个圆盘的时候 2的3次方减1
4个圆盘的时候 2的4次方减1
5个圆盘的时候 2的5次方减1
........
n个圆盘的时候 2的n次方减1
也就是说，n=64的时候是（2的64次方减1）次。
因此，如果移动一个圆盘需要1秒的话，
宇宙的寿命=2的64次方减1（秒）
用一年=60秒x60分x24小时x365天来算的话，大约有5800亿年吧。
据说，现在的宇宙年龄大约是150亿年，还差得远呢。
汉诺塔问题在数学界有很高的研究价值，
而且至今还在被一些数学家们所研究，
也是我们所喜欢玩的一种益智游戏，
它可以帮助开发智力，激发我们的思维。
汉诺塔的C语言实现
#include"stdio.h"
void move(char x,char y)
{
printf("%c-->%cn",x,y);
}
void hanoi(int n,char one ,char two,char three)
{
if(n==1) move(one,three);
else
{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}
main()
{
int m;
printf("input the number of disks:");
scanf("%d",&m);
printf("the step to moving %3d diskes:n",m);
hanoi(m,'A','B','C');
}
====================================华丽的分割线==================================
concreteHAM：
现在有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，现在把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，设移动次数为H(n)。
首先我们肯定是把上面n-1个盘子移动到柱子C上，然后把最大的一块放在B上，最后把C上的所有盘子移动到B上，由此我们得出表达式：
H(1) = 1
H(n) = 2*H(n-1)+1 (n>1)
那么我们很快就能得到H(n)的一般式：
H(n) = 2^n - 1 (n>0)
并且这种方法的确是最少次数的，证明非常简单，可以尝试从2个盘子的移动开始证，你可以试试。
进一步加深问题(解法原创*_*)：
假如现在每种大小的盘子都有两个，并且是相邻的，设盘子个数为2n，问：(1)假如不考虑相同大小盘子的上下要多少次移动，设移动次数为J(n)；(2)只要保证到最后B上的相同大小盘子顺序与A上时相同，需要多少次移动，设移动次数为K(n)。
(1)中的移动相当于是把前一个问题中的每个盘子多移动一次，也就是：
J(n) = 2*H(n) = 2*(2^n - 1) = 2^(n+1)-2
在分析(2)之前，我们来说明一个现象，假如A柱子上有两个大小相同的盘子，上面一个是黑色的，下面一个是白色的，我们把两个盘子移动到B上，需要两次，盘子顺序将变成黑的在下，白的在上，然后再把B上的盘子移动到C上，需要两次，盘子顺序将与A上时相同，由此我们归纳出当相邻两个盘子都移动偶数次时，盘子顺序将不变，否则上下颠倒。
现在回到最开始的问题，n个盘子移动，上方的n-1个盘子总移动次数为2*H(n-1)，所以上方n-1个盘子的移动次数必定为偶数次，最后一个盘子移动次数为1次。
讨论问题(2)，综上两点，可以得出，要把A上2n个盘子移动到B上，首先可以得出上方的2n-2个盘子必定移动偶数次，所以顺序不变，移动次数为：
J(n-1) = 2^n-2
然后再移动倒数第二个盘子，移动次数为2*J(n-1)+1 = 2^(n+1)-3，
最后移动最底下一个盘子，所以总的移动次数为：
K(n) = 2*(2*J(n-1)+1)+1 = 2*(2^(n+1)-3)+1 = 2^(n+2)-5 |
|
|