汉诺塔游戏递归.doc

第17课 汉诺塔游戏——递归 相传在古印度布拉玛婆门圣庙中的僧侣喜欢玩一种被称为汉诺塔的游戏。该游戏的装置是如图所示的一块铜板，上面有三根铜（编号A，B，C），A柱自下而上、由大到小按顺序串上64个金盘。游戏的目标是把A柱上的金盘全部移到C柱上，移动时可以借用B柱，并仍按原有顺序叠好。条件是每次只能移动一个盘，并且在每次移动时每个柱子上都不允许大盘移到小盘之上。现要求用程序来实现给出n个盘从A柱移到C柱的移动过程。 【分析】打开压缩包，运行里面的程序HANOI.EXE 先考虑简单情形。如果n=3,则具体移动步骤如图17-1所示： 图：17-1只有三个盘的汉诺塔游戏天字第一号示意图 如图17-2所示，假设把上面的第3步，第4步，第7步抽出来就相当于n=2的情况（但第3步要调用过程mov(n-1,a,b,c)，即第1、第2步; 第7步要调用过程mov(n-1,b,c,a)，即第5、第6步），(把上面2个盘捆视为1个盘)。原有n个盘问题，可把n-1个盘捆在一起，同理可求解。 图：17-2汉诺塔移动简化过程 所以可按n=2的移动步骤设计： 如果n=0,则退出，那结束程序否则继续往下执行。 用C柱作为协助过度，将A柱上的(n-1)个盘移动到B柱上，调用过程mov(n-1,a,b,c)。 将A柱上剩下的一个盘直接移到C柱上。 用A柱作为过渡，将B柱上的(n-1)个盘移动C柱上，调用过程mov(n-1,b,c,a)。 其中mov中的参数分别表示需移动的盘数、开始柱、终止柱与临时过渡柱，这种转换直到转入和盘数为0时才停止，因为这时已无盘可移了。 【参考程序】 Program P17_1; var x,y,x:char; n,k:integer; Procedure mov(n:integer;a,c,b:char); {借用b,实现把n个盘片从a移动到c} Begin if n=0 then exit; mov(n-1,a,b,c); {借用 c,实现把n-1个盘片从b移动到b} inc(k); {统计移动的次数} writeln(k,:form ,a, to ,c); {输出移动的第几步及移动的方法} mov (n-1,b,c,a); {借用a,实现把n-1个盘片从b移动到C} end; begin {主程序} write(n=); readln(n); k:=0; x:=A; y:=B; Z:=C; mov(n,x,z,y); {调用子程序，实现把n个盘片从a移动到c} readln end. 程序定义了把n片盘子从A柱移到C柱的过程mov(n,a,b,c),这个过程把移动分为以下三步来进行： 先调用过程mov(n-1,a,b,c),把(n-1)片从A柱移到B柱，C柱作为过渡柱; 直接执行writeln(k,:form,a,to,c)，把A柱上剩下的一片直接移到C柱上; 调用mov (n-1,b,c,a)，把B柱上的(n-1)片从B移到C柱上，A柱是过渡柱。 对于B柱上的(n-1)片如何移动，仍然调用上述的三步，只是把(n-1)当成n，每调用一次，要移动目标柱上的片数n就减少了一片，直到减少到n=0时就退出，不再调用。 调试过程视频演示 【及时充电】 递归——上面程序中，采用了程序设计中的一种重要的算法，即递归算法。简单地说，递归就是编写这样的一个特殊的过程或函数，该过程体或函数体中有一个语句用于调用过程自身(称为递归调用)。函数或过程直接调用其自身，称为直接递归; 函数或过程间接调用其自身，称为间接递归。如图17-3所示： (a)直接递归 (b)间接递归 图17-3 递归的两种形式 使用递归求解问题，通常可以将一个比较大的问题层层转化为一个与原问题相类似的、规模较小的问题来求解，最终达到对原问题的求解。 【探索奥秘】 阶乘函数定义(n!)描述如下: 1 fac(n)= n×fac(n-1) (当n0) 请编程实现从键盘输入n(n10)值，通过调用函数求f(n)的值。 〖分析〗 读入n值，根据数学知识，1!=1，正整数n的阶乘为：n×(n-1)×(n-2)×…×2×1,该阶乘序列可转换为求n×(n-1)!,而(n-1)!以可转换为(n-1)×(n-2)!,……，直至转换为