汉诺塔游戏递归.doc

第17课 汉诺塔游戏递归 相传在古印度布拉玛婆门圣庙中的僧侣喜欢玩一种被称为汉诺塔的游戏。该游戏的装置是如图所示的一块铜板，上面有三根铜（编号A，B，C），A柱自下而上、由大到小按顺序串上64个金盘。游戏的目标是把A柱上的金盘全部移到C柱上，移动时可以借用B柱，并仍按原有顺序叠好。条件是每次只能移动一个盘，并且在每次移动时每个柱子上都不允许大盘移到小盘之上。现要求用程序来实现给出n个盘从A柱移到C柱的移动过程。【分析】打开压缩包，运行里面的程序HANOI.EXEN=3时的初始状态第一步：从A移到C第二步：从A移到B第三步：从C移到B第四步：从A移到C 先考虑简单情形。如果n=3,则具体移动步骤如图17-1所示：第五步：从B移到A第六步：从B移到C第七步：从A移到C图：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个盘捆在一起，同理可求解。问题：将A柱上的n个盘移动到C柱 第1步：将A柱上的n-1个盘移动到B上(A为源柱，B为目标，C为过渡柱)第2步：将A柱上的1个盘移动C上，不用调用过程第3步：将B柱上的n-1个盘移动到C上(B为源柱，C为目标，A为过渡柱，记为(B，C，A)图：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 readlnend.程序定义了把n片盘子从A柱移到C柱的过程mov(n,a,b,c),这个过程把移动分为以下三步来进行：(1) 先调用过程mov(n-1,a,b,c),把(n-1)片从A柱移到B柱，C柱作为过渡柱;(2) 直接执行writeln(k,:form,a,to,c)，把A柱上剩下的一片直接移到C柱上; (3) 调用mov (n-1,b,c,a)，把B柱上的(n-1)片从B移到C柱上，A柱是过渡柱。对于B柱上的(n-1)片如何移动，仍然调用上述的三步，只是把(n-1)当成n，每调用一次，要移动目标柱上的片数n就减少了一片，直到减少到n=0时就退出，不再调用。调试过程视频演示【及时充电】l 递归上面程序中，采用了程序设计中的一种重要的算法，即递归算法。简单地说，递归就是编写这样的一个特殊的过程或函数，该过程体或函数体中有一个语句用于调用过程自身(称为递归调用)。函数或过程直接调用其自身，称为直接递归; 函数或过程间接调用其自身，称为间接递归。如图17-3所示：主程序子程序P。调用P。主程序子程序P子程序Q。调用P。 (a)直接递归(b)间接递归 图17-3 递归的两种形式 使用递归求解问题，通常可以将一个比较大的问题层层转化为一个与原问题相类似的、规模较小的问题来求解，最终达到对原问题的求解。【探索奥秘】例1 阶乘函数定义(n!)描述如下: 1 fac(n)= nfac(n-1) (当n0) 请编程实现从键盘输入n(n10)值，通过调用函数求f(n)的值。 分析读入n值，根据数学知识，1!=1，正整数n的阶乘为：n(n-1)(n-2)21,该阶乘序列可转换为求n(n-1)!,而(n-1)!以可转换为(n-1)(n-2)!,，直至转换为21!，而1!=1。参考程序一Program P17_2; var n:byte; function fac(n:byte):longint; begin if n=1 then fac:=1 当n=1时，函数值为1 else fac:=n*fac(n-1); 当n1时，函数值为n*fac(n-1),调用自身 end; begin 主程序 write(N=);readln(n); writeln(N! ,fac(n); end. 在子程序fac中，当n1时，又调用函数fac,参数为n-1,这种操作一直持续到n=1为止。例如当n=5时，fac(5)的值变为5*fac(4),求fac(4)又变为4*fac(3),当n=1时递归停止，逐步返回到第一次调用的初始处，返回结果5*4*3*2*1,即5!。如图17-4所示就是求f(5)的递归调用过程。nfac(n)fac(n)5n*fac(n-1)5*fac(4)5*fac(4)204(n-1)4*fac(3)4*fac(3)2433*fac(2)3*fac(2)622*fac(1)2*fac(1)21111先把因数推向极值1，然后再逐层退回来利用关系n*fac(n-1)得到最后结果图 17-4 递归调用的过程从图17-4中可以看出，递归过程的执行总是一个过程体执行完，就带着本次执行的结果又进入另一轮过程执行。如此反复，不断深入。直到某次过程的执行遇到终止递归调用的条件成立时，则不再深入。而执行本次的过程体余下的部分，然后又返回到上一次调用的过程体，执行其余的部分。如此反复，直到回到起始位置上，才最终结束整个递归过程执行，得到相应的执行结果。图17-4中左边部分表明了由于递归调用不断产生新的局部变量是保存在一个栈中，这些变量虽然同名，但各自独立，在逐层返回的过程中又是不断地从栈顶取出，直到取完。采用递归算法来编程，程序结构简洁，它能使一个蕴涵递归关系且结构复杂的程序简洁精练，增加可读性。但递归过程的实现决定了递归算法的效率往往很低，费时和费内存空间。如在汉诺塔游戏中，按照移动原则，将n个盘从A杆移动到C杆需要移动盘的次数是2的n次幂减1,那么64个盘移动次数就是18 446 744 073 709 511 645,近19亿亿次。这是一个天文数字，即使一台功能很强的现代计算机来解汉诺栽塔问题，恐怕也需要很长的时间，因此要想得到结果，在运行程序时，输入的n可不能太大。据说布拉玛婆罗门圣庙的僧侣声称，汉诺塔游戏结束就标志着世界末日的到来，现在看来确实是有道理的。因为如果每秒移动一次，64个盘则大约需近5800亿年，而据科学家以能源角度推算，太阳系的寿命只不过150亿年而已。所以在实际编程中，如果能使用递推法解决的，应尽量用递推法，其效率更高些。用递推法求解上面阶乘函数的思路是：先求fac(1),再求fac(2),直到求出fac(n)。参考程序二program P17_3; var n:integer; function fac(n:integer):longint; var i:integer; m:longint; begin m:=1; for i:=1 to n do m:=m*I; fac:=m; end;begin 主程序 write(n=); readln(n); writeln(fac(,n,)=,fac(n):6:2);end.例2输入一个字符串，最后以“#”结束，再按逆序输出来。分析读入一个字符，判断是否为#号，如果不是就继续读入，即可以调用程序本身。如果是“#”，则输出字符参考程序program P17_4; procedure rever; var c:char; begin read(c); if c# then rever; 递归调用的地方，下一次调用会分配新单元c write(c); 输出c,则会逐层栈中的Cr 值 end; begin rever; 调用子程序 end.典型的栈操作例3用递归算法求xn。分析我们可以：把xn分解成：x0=1 (n=0)x1=x*x0 (n=1)x2=x*x1 (n1)x3=x*x1 (n1)xn= x*xn-1 (n1)因此当n1时，将xn转化为x*xn-1，其中求xn-1又用求xn的方法进行求解。(1)定义过程xn(x,n:integer)求xn;如果n1则递归调用xn(a,n-1)求xn-1。(2)当递归调用到达n=0，就执行tt:=1,然后执行本“层”的后继语句。(3)遇到过程的end就结束本次的调用，返回到上一“层”调用语句的地方，并执行其后续语句tt:=tt*x.(4)继续执行步骤(3)，从调用中逐“层”返回，最后返回到主程序，输出tt的值。参考程序program p17_5; var tt,a,b:integer; provedure xn(x,n:integer); begin if n=0 then tt:=1 else begin xn(x,n-1); 递归调用过xn(x,n-1)求纪-1 tt:=tt*x; end; end; begin 主程序 writeinput x,n: readln(a,b); 输入a，b xn(a,b); 主程序调用过程xn(a,b)求ab writeln(a,b,=,tt); end.例4要求找出具有下列性质的数的个数(包含输入的自然数n);先输入一个自然数n(n50),然后对此自然数按照如下方法进行处理：(1)不作任何处理。(2)在它的左边加上一个自然数，但该自然数不能超过原数的一半。(3)加上数后，继续按些规则进行处理，到不能再加自然数为止。输入输出666162612636136分析(1)这道题只要求出满足条件的数的个数，在n值不大的情况下用递归求解比较方便，因为它本身题目的条件就是递归定义的。(2)目前可加的数x为1n/2 。(3)当前加上了x时，这时x前面根据题意也可以加上1n/2，这是一个不断递归调用本身的过程。(4)直到x=0，则不能再加任何数了，结束递归。参考程序program P17_6; var n,i:integer; s:real;procedure qiu(x:integer); 递归的过程 var k:integer; begin if x0 then 当x为零时结束递归调用 begin s:=s+1; 累加统计个数 for k:=1 to x div2 do qiu(k) 递归调用本身 end end; begin 主程序 real(n); s:=0; s清零，用来统计满足条件的个数 qiu(n); 调用子程序 writeln(s:2:0)end. 展示实力万炽洋的程序：1、某人写了n封信和n个信封，结果所有信都装错信封。求所有的信都装错信封共有多少种不同的情况。2、楼梯有n阶台阶，上楼可以一步上一阶，也可以一步上二阶。请用递归方法编程计算共有多少种不同的走法。3、用递归方法方法完成：有52张牌，使它们全部正面朝上，第一轮是从第2张开始，凡是2的倍数位置上的牌翻成正面朝下；第二轮从第三张牌开始，凡是3的倍数位置上的牌以，正面朝上的翻成正面朝下，正面朝下的翻成正面朝上；第三轮从第4张牌开始，凡是4的倍数位置上的牌按上面相同规则翻转，从此类推，直到第一张要翻的牌超过52为止。统计最后有几张牌正面朝上，以及它们的位置号。4、用递归方法来实现：在不改变字符串的内容的情况下，将字符串S中的字符逆序输出。如s=abcd,则输出dcba.5、有n个硬币(n为偶数)正面朝上排成一排，每次将n-1个硬币翻成朝上为止。编程让计算机把悉硬币的最简过程及翻币次数打印出来(用*代表正面，用0代表反面)。6、阿克曼(ackmann)函数a(x,y)中，x,y定义域是非负整数，函数值定义为： a(x,y)=y+1(x=0) a(x,0)=a(x-1,1)(x0,y=0) a(x,y)=a(x-1,a(x,y-1)(x,y