文档介绍：汉诺塔问题算法分析及C语言实现摘要:文章对“汉诺塔”问题进行了详细的分析,给出了一种实现的算法,并用C语言实现。通过该问题的C实现,可使学****者清晰地观测到解决该问题的全过程。关键词:汉诺塔;算法;递归中图分类号:TP311文献标识码:A文章编号:1009-3044(2008)17-21496-02 1问题描述问题提出:有三个塔(分别为A号,B号和C号)。开始时,有n个圆形盘以从下到上、从大到小的次序叠置在A塔上。现要将A塔上的所有圆形盘,借助B搭,全部移动到C搭上,且仍按照原来的次序叠置。移动的规则:这些圆形盘只能在3个塔间进行移动,一次只能移动一个盘子,且任何时候都不允许将较大的盘子压在比它小的盘子的上面。要求:从键盘输入初始圆形盘子个数n,用C语言实现n个盘子最佳移动的全过程。 2算法分析题目实现的是设计一个盘子移动的方案,使得A号塔上的所有盘子借助于B号塔按照原来的次序移动到C号塔上,并且给出完整的最佳的盘子移动的方案。从实际的、具体的盘子的移动过程来分析,找出问题内在的规律。经分析无论盘子的个数有多少,是1、2、3或n个,也不管怎么去移动盘子(当然是按一定规则移动),但在移动的过程中,将始终会出现这样的状态情况:(n-1)个盘子将会以从下到上、从大到下的次序叠置在B塔上,这时,A塔上第n个盘子就能被轻而易举叠放到C塔上;接着,我们再把B塔上的共(n-1)个盘子移动到C塔上,问题好像已经解决。但,B塔上(n-1)个盘子怎么移动到C塔上呢?这是要解决的第二个问题。同样,不管怎么移动,也将会出现这样的状态情况:(n-2)个盘子将会以从上到下、从大到小的次序叠置在A塔上,这时,B塔上第(n-1)个盘子就能被轻而易举放到C塔上;接着,把A塔上的共(n-2)个盘子移动到C塔上。这样,不断深入,不断细小化,最终,将到达仅有一个盘的情形,这时,递归也就终止了,问题也得到了解决。通过以上分析,这里有很明显递归关系。由此,想到了采用递归算法来解决该问题,因为递归算法有这样特征描述:为了求解出规模为n的问题的解,我们先设法将它分解成一些规模较小的问题,然后从这些较小问题的解能方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的方法分解,分解成规模更小的问题,并能从这些更小的问题的结构造出规模稍大问题的解。特别地是,当规模n=1时,能直接得到解。现在,严格按照递归算法来解决问题。先定义递归方法Hanio(intn,charA,charB,charC),按如下步骤进行解题(设初始盘子个数为N):若A塔上仅仅只有一个盘子(n=1),则直接从A移动到C,问题完全解决。若A塔上有一个以上的盘子(n>1),则需要考虑以下三个步骤。第一步:把(n-1)个盘子从A塔经过移动,叠放到B塔上。在不违反规则情况下,所有(n-1)个盘子不能作为一个整体一起移动,而是要符合要求地从一个塔移到另一个塔上。用Hanio(n-1,A,C,B)调用递归方法,注意:这里是借助于C塔,将(n-1)个盘子从A塔移动到B塔,A是源塔,B是目标塔。第二步:将剩下的第n个盘子(也就是最底下的一个)直接从A塔叠放到空着的C塔上。第三步:用第一步的方法,再次将B塔上的所有盘子叠放到C塔上。同样,这一步实际上也是由一系列更小的符合规则的移动盘子的操作组成的。用Hanio(n-1,B,A,C)调用递归方法,注