目录
一、背景
二、解决思路
三、代码
1、递归实现
2、非递归实现
一、背景
法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，
假如每秒钟一次，共需多长时间呢？一个平年365天有31536000秒，闰年366天有31622400秒，平均每年31557600秒，计算一下：
18446744073709551615秒
二、解决思路
假如A上有1片，A->C 直接从A移到C步骤数1 f(1)=1
假如A上有2片，A->C 第一片从A移到B 第二片从A移到C 再把第一片从B移到C 步骤数3 f(2)=3
假如A上有n片，A->C 最上面(n-1)片从A移到B 最后一片从A移到C 再把B上的(n-1)片移到C 步骤数2*f(n-1)+1 f(n)=2*f(n-1)+1 (这个移动方法是对的)
假如A上有n片，A->C 第一片从A移到B （n-1）片从A移到C 再把第一片从B移到C 步骤数f(n-1)+2 (思考一下这个移法为啥是错误的?)
三、代码
1、递归实现
int f(int n){if(n<1)return 0;else if(n==1)return 1;else if(n==2)return 3;else return 2*f(n-1)+1;}
2、非递归实现
int f(int n){if(n<1)return 0;if(n==1)return 1;int a=1;for(int i=1;i<n;i++){a=2*a+1;}return a;}
