资源描述：
《关于Hanoi塔递推关系的建立及其启示》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、关于Hanoi塔递推关系的建立及其启示Hanoi的背景来源 汉诺塔是源自印度神话里的玩具。 上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。 有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘。算法分析当圆盘个数较少的时候，我们可以通过笔算将所有可能的情况列举出来。ＡＢＣ如上图：当ｎ＝３时移动：A—CA—BC—BA—CB—AB—CA
2、—C5移塔的过程： 1.MoveTower(N-1,A,B,C);分解：2.把一个圆盘从Ａ柱移到Ｃ柱。 3.MoveTower(N-1,B,C,A);(3,1,3,2)1—3(2,2,3,1)2—3(1,1,3,2)(0,2,3,1)(0,2,3,1)1—3(1,2,1,3)(0,2,3,1)2—1(0,3,1,2)(2,1,2,3)1—2(0,1,2,3)(1,1,3,2)(0,2,3,1)1—3(1,2,3,1)(0,2,3,1)3—2(0,1,2,3)当n>3时,该怎样研究呢？其中又蕴涵着怎样的数学思想和规律呢？这正是我们提出这一课题的目
3、的．探究过程5研究当n较小的时候的情况，通过发现,归纳,总结,得出一般性的规律，进而在数学的严格证明之下推广到任意情况！通过探究，我们得出如下规律：1.如果只有一个圆盘，则把该圆盘从初始柱移动到目标柱，结束。其实这也是递归调用的终止条件。2.如果有n个圆盘，则把前n-1个圆盘移动到辅助的柱，然后把自己移动到目标棒，最后再把前n-1个移动到目标柱，这其实是将原来的n个圆盘转化为n-1个圆盘的问题，降低了问题的规模，这也是递归调用的本质：将一个较大规模的问题用同样的方法（即递归方程）不断转化将规模化小，直至满足终止条件，然后回归求解。算法复杂度分析n个圆
4、盘的汉诺塔问题需要移动的金片数是n-1个圆盘的汉诺塔问题需要移动的圆盘数的2倍再加1。因此：h(n-1)*2+1(n>=2)递归方程：h(n-1)=1(n=1)h(n)=h(n)为移动第n个圆盘时的用的总步数5因此，要完成64个圆盘的汉诺塔问题，需要移动的金片数为：如果每秒移动一次，一年有31,536,000秒，则僧侣们一刻不停地来回移动，也需要花费5849亿年的时间；假定计算机以每秒1000万个金片的速度进行移动，则需要花费58,490年的时间。汉诺塔问题说明了理论上可以计算的问题，实际上并不一定能行，这属于计算复杂性领域的研究内容。通常将可以在多
5、项式时间内求解的问题看作是易解问题，这类问题在可以接受的时间内实现问题求解，将需要指数时间求解的问题看作是难解问题，这类问题的计算时间随着问题规模的增长而快速增长，即使中等规模的输入，其计算时间也是以世纪来衡量的。启示5通过对汉诺塔递推关系的建立的探究，我们不仅得到了汉诺塔递推关系的递归方程，明白了古代汉诺塔问题的难解性，还领悟到递推方法的妙用。灵活地将递推方法应用到日常生活的学习中去，可以达到事半功倍的效果。这次研究性学习，不仅使我们敏锐的思维得到了发散，更重要的是提高我们组员间的团结能力，增强了集体凝聚力，这在我们今后的学习生活中，必将是一笔极大
6、的精神财富！5
