永久免费网站推荐,wordpress 广告,创建wordpress用户,钟村免费建站公司历史传说#xff1a;
在世界中心贝拿勒斯#xff08;在印度北部#xff09;的圣庙里#xff0c;一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候#xff0c;在其中一根针上从下到上地穿好了由大到小的64片金片#xff0c;这就是所谓的汉诺塔。不论白天黑夜…历史传说
在世界中心贝拿勒斯在印度北部的圣庙里一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候在其中一根针上从下到上地穿好了由大到小的64片金片这就是所谓的汉诺塔。不论白天黑夜总有一个僧侣在按照下面的法则移动这些金片一次只移动一片不管在哪根针上小片必须在大片上面。僧侣们预言当所有的金片都从梵天穿好的那根针上移到另外一根针上时世界就将在一声霹雳中消灭而梵塔、庙宇和众生也都将同归于尽。
不管这个传说的可信度有多大如果考虑一下把64片金片由一根针上移到另一根针上并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片移动次数是f(n).显然f⑴1,f⑵3,f⑶7且f(k12*f(k)1。此后不难证明f(n)2^n-1。n64时f64 2^64-118446744073709551615。假如每秒钟一次共需多长时间呢一个平年365天有 31536000 秒闰年366天有31622400秒平均每年31556952秒计算一下18446744073709551615/31556952584554049253.855年
这表明移完这些金片需要5845亿年以上而地球存在至今不过45亿年太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年不说太阳系和银河系至少地球上的一切生命连同梵塔、庙宇等都早已经灰飞烟灭。***********************************************************************************************************************************************************************************
汉诺塔问题的限制条件
1.在小圆盘上不能放大圆盘。
2.在三根柱子之间一回只能移动一个圆盘。
3.只能移动在最顶端的圆盘。
首先我们从简单的例子开始分析然后再总结出一般规律。
当n 1的时候即此时只有一个盘子那么直接将其移动至C即可。移动过程就是 A - C
当n 2的时候这时候有两个盘子那么在一开始移动的时候我们需要借助B柱作为过渡的柱子即将A柱最上面的那个小圆盘移至B柱然后将A柱底下的圆盘移至C柱最后将B柱的圆盘移至C柱即可。那么完整移动过程就是A - B , A - C , B - C
当n 3的时候那么此时从上到下依次摆放着从小到大的三个圆盘根据题目的限制条件在小圆盘上不能放大圆盘而且把圆盘从A柱移至C柱后C柱圆盘的摆放情况和刚开始A柱的是一模一样的。所以呢我们每次移至C柱的圆盘移至C柱后不再移到其他柱子上去必须是从大到小的即一开始的时候我们应该想办法把最大的圆盘移至C柱然后再想办法将第二大的圆盘移至C柱......然后重复这样的过程直到所有的圆盘都按照原来A柱摆放的样子移动到了C柱。
那么根据这样的思路问题就来了
如何才能够将最大的盘子移至C柱呢
那么我们从问题入手要将最大的盘子移至C柱那么必然要先搬掉A柱上面的n-1个盘子而C柱一开始的时候是作为目标柱的所以我们可以用B柱作为暂存这n-1个盘子的过渡柱当把这n-1的盘子移至B柱后我们就可以把A柱最底下的盘子移至C柱了。
而接下来的问题是什么呢
我们来看看现在各个柱子上盘子的情况A柱上无盘子而B柱从上到下依次摆放着从小到大的n-1个盘子C柱上摆放着最大的那个盘子。
所以接下来的问题就显而易见了那就是要把B柱这剩下的n-1个盘子移至C柱而B柱作为过渡柱那么我们需要借助A柱将A柱作为新的过渡柱将这n-1个盘子移至C柱。
*********************************************************************************************************************************************************************
作者Adherer
来源CSDN
原文https://blog.csdn.net/liujian20150808/article/details/50793101
版权声明本文为博主原创文章转载请附上博文链接
*********************************************************************************************************************************************************************
该问题可以分解成以下子问题
第一步将n-1个盘子从A柱移动至B柱借助C柱为过渡柱
第二步将A柱底下最大的盘子移动至C柱
第三步将B柱的n-1个盘子移至C柱借助A柱为过渡柱
解1n 1
第1次 1号盘 A----C sum 1 次
(2) n 2
第1次 1号盘 A----B
第2次 2号盘 A----C
第3次 1号盘 B----C sum 3 次
3n 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
n的阶乘问题
再说一个例子计算n的阶乘
f(n) n!
其递归算法如下
int factorial(int n){
if(n 1)
return 1;
else
return n * factorial(n-1);
}
这段程序加载到内存的分配图如下图片来源于“码农翻身”公众号
由于递归是函数自身调用自身所以程序被编译后代码段中只有一份代码。递归调用是如何进行的呢注意看堆栈中的栈帧啊 每个栈帧就代表了被调用中的一个函数 这些函数栈帧以先进后出的方式排列起来就形成了一个栈 栈帧的结构如下图所示图片来源于“码农翻身”公众号
相信大家还记得《数据结构》严蔚敏版一书中提到的“工作记录”就是指函数栈帧。栈顶指针被称为“当前环境指针”。忽略到其他内容 只关注输入参数和返回值的话阶乘函数factorial4的工作栈如下图所示图片来源于“码农翻身”公众号
其计算过程如下图所示图片来源于“码农翻身”公众号
注意 每个递归函数必须得有个终止条件 要不然就会发生无限递归了 永远都出不来了。
当然针对于此递归算法对于n的值是有限制的。因为堆栈容量是有限的如果n值太大程序会崩掉。
该如何解决呢从上面的代码中可以知道“factorial(n) n * factorial(n-1 )” 这个计算式是整个程序的核心。 图中每个栈帧都需要记录下当前的n的值 还要记录下一个函数栈帧的返回值 然后才能运算出当前栈帧的结果。 也就是说使用多个栈帧是不可避免的。
可以使用下面的递归算法int factorial(int n,int result){
if(n 1){
return result;
}
else{
return factorial(n-1,n * result);
}
}注意函数的最后一个语句 就不是 n * factorial(n-1) 了 而是直接调用factorial(....) 这个函数本身 这就带来了巨大的好处。
计算过程如下当执行到factorial(1, 24)的时候直接就可以返回结果了。这就是妙处所在了计算机发现这种情况只用一个栈帧就可以搞定这些计算无论n有多大。图片来源于“码农翻身”公众号
这就是所谓的“尾递归”了 当递归调用是函数体中最后执行的语句并且它的返回值不属于表达式一部分时 这个递归就是尾递归。
现代的编译器就会发现这个特点 生成优化的代码 复用栈帧。 第一个算法中因为有个n * factorial(n-1) , 虽然也是递归但是递归的结果处于一个表达式中还要做计算 所以就没法复用栈帧了只能一层一层的调用下去。
