汉诺塔•法国数学家卢卡斯（Edouard Lucas）在1883年提出了一个数学游戏：•传说在世界中心贝拿勒斯（印度北部）的圣庙里，一块黄铜板上有三根宝石柱。
印度教的主神大梵天在创造世界的时候，在其中一根柱上从下到上地穿好了由大到小的64片金盘。
大梵天命令僧侣们将圆盘从下面开始按大小顺序重新摆放在另一根柱子上，并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
预言说当这些盘子移动完毕时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
A B C•这个传说又称作梵天寺之塔问题(Tower of Brahma puzzle)，而且有若干变体：其一是寺院的地点位于越南河内，因此该问题也常被称作“河内塔”或“汉诺塔（Tower of Hanoi）”。
•考虑该问题的一般形式：有n个圆盘，最初自下而上、自大而小地穿在A柱上，每次按规则移动一个圆盘，最终将所有圆盘移动到C柱上。
A B CA B C •共移动7次•先将A柱上所有其他盘子移到B柱上（这是一个类似于自己的子问题）•接着将最大的盘子从A柱移到C柱，之后不必再管它•最后再将刚才移到B柱上的盘子移到C柱上（这又是一个子问题）。
1……n-1nA B C•汉诺塔的递归算法 Hanoi (n, source, dest, by) 输入：圆盘数n。
• 1.If (n=1) then• 1.1.Print (Move disk from source to dest) • 2.Else• 2.1.Hanoi (n-1, source, by, dest)• 2.2.Print (Move disk from source to dest) • 2.3.Hanoi (n-1, by, dest, source)•递归算法直接解决足够简单? Y 通过一些操作简化为与自己类似的子问题N问题规模变小•用T(n)表示移动n 个圆盘所需要的步数•根据算法•先把前面n-1 个盘子转移到B上；•然后把第n 个盘子转到C上；•最后再次将B上的n-1 个盘子转移到C上•得到递推关系T(n)=2T(n-1)+1•使用倒推法求解T(n)=2T(n-1)+1, T(1)=1: T(n) = 2T(n-1)+1= 2(2T(n-2)+1)+1 =22T(n-2)+2+1= 22(2T(n-3)+1)+2+1 = 23T(n-3)+22+2+1= ……= 2n-1T(1)+2(n-1)-1+…+22+2+1= 2n-1+2(n-1)-1+…+22+2+1= 2n-1汉诺塔•回到最初的汉诺塔问题，要将64片金盘重新摆放在另一根柱子上，最少需要264-1步，即使僧侣每秒钟移动一步而且每次移动都是正确的方法，那么也需要5.8⨯1011 年，即5千多亿年！11E nd。
