汉诺塔
汉诺塔的由来
汉诺塔是源自印度神话里的玩具。
上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着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-->%c
",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:
",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