pascal递归.doc

中山纪念中学信息学奥林匹克算法设计题选四、递 归这里我们将再一次讨论PASCAL语言的递归算法设计方法。一般的，用BASIC语言实现递归是非常困难的，而用PASCAL语言的自定义函数或过程来实现就要方便、快捷的多，这就是为什么在信息学竞赛中同学们广泛使用PASCAL语言的原因。我们已经学习自定义函数、过程的编写以及递归的实现方法，这里再简单重复一下。递归函数递归函数是PASCAL语言编程中通向高级算法的必由之路，要掌握递归函数必须要先掌握递归这个概念。什么是递归呢？我们来看一个例题，在此之前我们先学会什么是数列。数列即一序列数的总称，如：1，2，3，4，5，6，7，8是自然数数列；2，4，6，8，10，是自然偶数数列；象这种以某种关系定义的数的序列就叫数列。数列的名称可任取，象上述第一个数列如果名为A，第二个数列名为B，则第一个数列的各个数字的名字就为：A1，A2，A3，A4或A（1），A（2），A（3）。数列A的数字关系是：（1）A（N）=A（N-1）+1（N1）；（2）A（1）=1；由此两个关系，我们只要知道该数列中任何一个数的序号，就可推知该数的数值。那么如果对于数列A，我想知道A（100）是多少该如何推算呢？由上述关系我们已经知道：A（100）=A（99）+1，即要知道A（100），我们就必须先知道A（99）；而A（99）=A（98）+1；即要知道A（99）就必须先知道A（98）；由此类推A（98）=A（97）+1；A（3）=A（2）+1；A（2）=A（1）+1；而此时就已经不用继续推算下去了，因为A（1）是已知的了。而实际上，上述推算过程就是递归过程。即要完成某个计算，必须先完成其前的另一个计算，以此类推，直到推到一个已知的值为止。例1有一个数列N，已知：N（1）=1，N（X）=N（X-1）*3-1（X1），求N（100）；我们已经知道，由递归关系，我们要求N（100），就必须知道N（99）N（1），而最终N（1）是已知的，所以这个递归关系我们就可以用PASCAL语言很好地表现出来。以下我们用递归函数来完成，请大家注意递归的实现方法，即自己调用自己。Var n100:integer;Function dg(n:integer):integer;Begin If n:=1 then dg:=1 Else beginDg:=dg(n-1)*3-1; End;End;Begin N100:=dg(100); Writeln(n100);End.定义程序主体中的变量定义自定义函数DG，形式参数1个，用以记录现在是推算到了第几个数。递归出口是当N等于1时，DG的值为1如果N不等于1，我们就继续递归，这就是递归关系式程序主体调用递归函数由上可以看出，用递归函数来实现算法，程序主体可以变得非常简单，只需少数几句即可。而递归函数就显得至关重要了，由上述程序可以看出，递归函数的实现实际上就是一个自己调用自己的函数。直到调用到已知的数为止。递归问题我们还将在递归过程中详细分析。由上可见，递归过程实际上只有一句，IF 条件 THEN 出口 ELSE 调用下一次递归；递归过程我们从一个例题中来看看递归的实际实现及运行过程。例2打印A、B、C、D、E这五个字符任意排列的所有情况。分析，此题可用五重循环来做，但那样就把此题给复杂化了，运行速度也要慢很多，而此题用递归过程来做的话就要简单许多。我们把递归过程定为每次从五个字符中取一个字符，当然这个字符必须与已经取得的字符全不相同，而我们取得的字符存放在一个字符串中，并把它作为形式参数（这一点至关重要，否则答案将完全错误）。当我们已经取完五个字符后，在取第六个字符时，递归过程就将结束。这就是递归的出口。这样我们就能把所有结果找出来。程序如下：Var t:longint;Procedure dg(n:integer;s:string);Var I:char;Begin If n=6 then begin T:=t+1;Writeln(t:5, ,s); End else beginFor I:=A to E do begin If pos(I,s)=0 then begin Dg(n+1,s+I); End;End; End;End;Begin T:=0; Dg(1,);End.计算答案总数的计数器递归过程有两个形式参数，N表示当前取第N个字符，S存放已经取得的N-1个字符；N等于6时，递归到了一个答案答案总数加1把答案数及答案打印出来从此句中返回调用此过程的上一过程从AE五个字符中取一个如果这个字符在已经取得的N-1个字符中没有出现就调用下一次递归，即调用自己，只不过参数N变为N+1，即下次将取第N+1个字符（相对于当前来说），而输入的S参数也变为已经加入第N个字符的新字符串。程序主体开始答案总数初值为0调用递归过程，输入值1表示要找第1个字符，表示已经找到的0个字符上述程序的运行过程如下：过程步骤N的值S的值1.以参数1，输入递归过程DG，开始递归第一层12.取到第一个字符，A1A3.以参数(N+1,S+I), 即(2,A)调用第二层递归,即第一层过程尚未结束, 就调用第二层递归过程, 此时,第一层过程保留在内存中,程序执行到循环语句的A, 程序返回此过程中时,将继续执行此循环语句,而此时此循环已被挂起2A4.进入第二层递归,取到第二个字符,此时A已不能取, 只能取B2AB3.以参数(N+1,S+I), 即(3,AB)调用第三层递归,即第一层及第二层过程尚未结束, 就调用第三层递归过程, 此时,第一,二层过程保留在内存中,3AB5.进入第三层递归,取到第三个字符,此时A和B已不能取, 只能取C3ABC接上. 以参数(N+1,S+I), 即(5,ABCD)调用第五层递归,即第一层到第四层过程尚未结束, 就调用第五层递归过程, 此时,第一至四层过程留在内存中,5ABCD接上. 进入第五层递归,取到第五个字符,此时只能取E5ABCDE接上. 以参数(N+1,S+I),即(6,ABCDE)调用第六层递归,即第一层到第五层过程尚未结束, 就调用第六层递归过程, 此时,第一至四层过程留在内存中6ABCDE接上. 进入第六层递归过程, 此时N=6条件满足,将不执行下一层递归,而是打印出第一个答案ABCDE, 并结束此次递归过程, 这意味着,程序将回到调用第六层递归的第五层递归的循环语句中6ABCDE接上. 程序回到第五层递归过程中, 而此时, 循环已经执行到E, 无其它字母可加入,所以第五层递归将被自然结束,返回第四层递归过程的循环语句,注意: 此时,N已经变成5, 而S为ABCD, 与开始进入第五层递归是一致的,这就是把N和S作为形式参数的意义之处5ABCD接上. 程序回到第四层递归中, 此时的循环执行到D, 还有E可取4ABCE接上. 取完E后,程序又调用第五层递归,此时可取D,5ABCED接上. 进入第六层递归,打印已经取得的新答案:ABCED接上. 取得新答案后, 返回第五层, 没有字符可取, 正常结束再返回第四层, 仍没有字符可取,再返回第三层,此时,第三层刚取完C,可取D3ABD接上,再重复上述过程,N及S的取值情况如下:4ABDC5ABDCE4ABDE5ABDEC3ABE4ABEC5ABECD从上述分析中，可以看出整个递归过程完全是动态的，不停地在各层递归过程之间调用，也包括返回第一层的情况，这样就能把所有答案都找出来。下面我们以取ABC三个字符的全排列来看其生成树的全过程：第0层： 开始(1)第一层： A(2) B(7) C(12)第二层 AB(3) AC(5) BA(8) BC(10) CA(13) CB(15)第三层 ABC(4) ACB(6) BAC(9) BCA(11) CAB(14) CBA(16) 由上可以看出，共生成了16个节点（NODE），我们把每一个状态，即每一个递归过程产生的字符串叫做一个节点，请大家记住这个概念。从开始第一个节点开始，我们的子点遍历过程是按数字大小来标明的，即（1）-（16）这16个节点是按顺序生成的，结果共有6个，这6个节点产生的顺序也可看出是按数字大小来产生的。整个递归过程共产生了三层节点，每个目标节点都是直线产生，每条能够走通的路线都一定能产生出目标节点，这就是递归，同样，这就是我们所说的深度优先搜索问题，即搜索方向是直向深处的节点的。另外，上述图中，程序经过每个节点的顺序我们也能很清楚的说出了：（开始）1234325652178987101110711213141312151615121（结束）。上述到达4、6、9、11、14、16节点是找到了答案，由小节点往大节点走时是调用深一层递归过程，而大节点往小节点走时是由深层的节点返回上一层节点，这其实也就是回溯了。从这种观点来看，递归与回溯的差别是很小的，递归是在找到一个答案之前，即中途是不会返回上一层的，而回溯是在中途就有可能无法展开下一层节点，而只能返回上一层。下面我们将以数个例子来更深入地说明递归与回溯这两大重点。例3从键盘输入一个正整数N，求把它分解成若干个小于等于N的正整数之和的所有情况。分析：我们完全可模仿例2的方法，把递归过程定为每次从1到N-1这些正整数中取一个整数，而我们取得的数字经转换为字符后，也存放在一个字符串中，并把它作为形式参数。然后把M减去这整数后再做为新的参数，当我们新的参数已经为0时，递归过程就将结束。这就是递归的出口。这样我们就能把所有结果找出来。程序如下：Var a,t:longint;Procedure shu(n:integer;s:string);Var I:integer; C:string;Begin If n=0 then begin T:=t+1;Writeln(t:5, ,a,= ,copy(s,1,length(s)-1); End else beginFor I:=1 to n do begin Str(I,c); Shu(n-i,s+c+);End; End;End;Begin T:=0; Readln(a); Shu(a,);End.键盘输入值及计算答案总数的计数器递归过程有两个形式参数，N表示剩下的整数是多少，S存放已经取得的数字N等于0时，递归到了一个答案答案总数加1答案打印(去掉最后一个加号)从此句中返回调用此过程的上一过程从1N的整数中取一个整数转换为字符串调用下一次递归，即调用自己，只不过参数N变为N-i，即下次将用N-I来减，输入的S参数也变为已经加入新取的这一个数字及加号。程序主体开始答案总数初值为0读入A调用递归过程，输入值A及（空字符串）4：求N！（阶乘）。分析：我们知道：N！=1*2*N。实际上：N！=（N-1）！*N，即要求N的阶乘，得先求N-1的阶乘。同理，要求N-1的阶乘，得先求N-2的阶乘要求2的阶乘，得先求1的阶乘，而1的阶乘就等于1，这就是递归的结束（出口）。也就是说，求N！实际上是一个递归问题。我们知道，求递归问题要编写一个自定义函数或过程，在这个函数或过程中只要有以下几个语句即可：1、递归结束的条件以及结束后做什么；2、递归结束的条件不满足时，即应该继续递归时做什么。下面给出的程序就是用递归算法求N！。var n:integer;function dg(m:integer):longint;begin if m=1 then dg:=1 else dg:=m*dg(m-1);end; begin readln(n); writeln(dg(n);end.如果M等于1就结束递归，否则用公式M*DG（M-1）调用M-1的阶乘调用递归函数上述程序中设计了一个递归函数，虽然只有一个语句，但其作用却是非常大的。它的作用过程请大家根据已经掌握的递归知识自已分析一下。下面我们看一个数据结构的概念树，树的定义如下：一个树是N个元素的有限集合。（1） 每个元素称为结点；（2） 有一个特别的结点称为树的根或根结点；（3） 除根结点外，其余结点能分成M（M=0）个不相交的集合，而每个集合又都是树，这些集合称为这个树的子树（即可把某一非根结点发出的所有结点作为一个子树）。 12 3 4 5 6 7 8 9 10 11 12在第（3）点中，又引用了树的概念，这就是递归。我们可用下图来说明树与子树的关系：从上述树中可以看出，根结点为1，而其余2、3、4、5、6、7都能发出一个子树。5：菲波那契（Fibonacci）数列。有雌雄一对兔子，假定两个月便可繁殖雌雄各一的一对兔子。问N个月后共有多少对兔子？（注意：此题是不符合实际情况的，在此题中我们假定一对兔子可以第1、2个月中分别怀孕，然后在第3、4月中分别生下小兔子。请大家自己考虑此题改为：1、兔子每个月就可生一对小兔子的情况；2、小兔子需一个月长成大兔子后，然后与大兔子一样每个月生一对小兔子的情况）。分析：设N个月后有F（N）对兔子，则F（N）应该等于第N-1个月后的兔子数（即F（N-1）加上第N-1个月（即第N个月时）后出生的小兔子，由题目条件可知，第N个月出生的兔子数应该和第N-2个月后兔子总数（即F（N-2）相等！所以可得到以下等式：F（N）=F（N-1）+F（N-2）并且，我们可以知道，第一个月后的兔子对数F（1）=1，第二个月后兔子对数F（2）=1。所以，我们可得到以下公式：程序如下：var n:integer;function f(m:integer):integer;begin if (m=1) or (m=2) then f:=1 else f:=f(m-1)+f(m-2);end; begin readln(n); writeln(f(n);end.请大家注意，我们在上述两个程序中都是用自定义函数来实现递归的，如果用过程来实现的话，性质是相同的。6：梵塔问题：有三个塔柱（以A，B，C表示）。在A上有一个干塔，共N层。今以一个圆盘代表一层，在盘在下，小盘在上。要求将塔从A移动到C。按规定，每次只能移动一个盘子，可以将盘子放在三个塔柱中任一个上，但大盘子不能放在小盘子上面。试编程序打印出移塔过程。分析：我们可以发现，要把N片全从A移动到C上，则必须先把A上的N-1片移动到B上，这时可用C作媒介；要把A上的N-1片移动到B上，则先必须把A上的N-2片以B为媒介移动到C上。这样就是一个递归过程，即深度优先搜索问题。我们可以定义一个递归过程：MOVE（M，X，Y，Z）：表示把X上M片以Y为媒介移动到Z上，这里M,z)else beginmove(m-1,x,z,y);writeln(x:4,=,z);move(m-1,y,x,z);end;end;beginreadln(n);move(n,A,B,C);end. 上述程序我们就是用自定义过程来实现的，可以看到其实质上和自定义函数来实现是相同的。7、递归：验证卡布列克常数，对于一个四位数N，进行下列运算：（1）将组成该四位数的4个数字由大到小排列，形成由这4个数字组成的最大的四位数；（2）将组成该四位数的4个数字由小到大排列，形成由这4个数字组成的最小的四位数（如果高位为0则取得的数不足4位）；（3）求两个数的差，得到一个新的四位数（高位0保留），称为对N进行了一次卡布列克运算。有这样的规律：对一个各位数字不全相同的四位数重复进行若干次卡布列克运算，最后得到的结果总是6174。这个数被称为卡布列克常数。N从键盘输入。输出每一次的卡布列克运算及得到6174时的运算次数。这是一个典型的递归过程，递归的出口为得到6174为止。请大家读懂下列程序，然后自己再编一遍。var n,t:integer; procedure fournum(f:integer;var f1,f2,f3,f4:integer); 取得四位字各位数字的过程var n1,n2,n3,n4:integer;begin n1:=f div 1000; n2:=(f-n1*1000) div 100; n3:=(f-n1*1000-n2*100) div 10; n4:=f mod 10; f1:=n1;f2:=n2;f3:=n3;f4:=n4;end; function pdsame(s:integer):boolean; 判断该数是否不全相同的函数var p:array1.4 of integer; q,r:integer;begin fournum(s,p1,p2,p3,p4); pdsame:=true; for q:=1 to 3 do begin for r:=q+1 to 4 do begin if pqpr then pdsame:=false; end; end;end;procedure kblk(m:integer);递归过程，卡布列克运算var num:array1.4 of integer; i,j,k,x,y:integer;begin if m=6174 then begin writeln(total times: ,t); end else begin fournum(m,num1,num2,num3,num4); for i:=1 to 3 do begin for j:=i+1 to 4 do begin if numinumj then begin k:=numi; numi:=numj; numj:=k; end; end; end; x:=num1*1000+num2*100+num3*10+num4; y:=num4*1000+num3*100+num2*10+num1; writeln(x, - ,y, = ,x-y); t:=t+1; kblk(x-y); end;end;begin主程序 readln(n); if (n9999) or (pdsame(n) then writeln(wrong input!) else begin t:=0; kblk(n); end;end.8、递归：对任意自然数N，将其拆分为若干个自然数之和。9、递归：有一楼梯共有N级，现在从第1级开始，每步可以走1级，也可以走2级、3级，问共有多少种走法并打印所有走法。10、递归：快速排序法：把数组中的N个数进行快速排序。N及N个数从键盘输入。分析：（1）把N个数存放在数组S中，当前集合为S中所有数。 （2）把当前集合第一个数定为标准数K，把S分为两个子集，左边子集S1为小于等于K的数，右边子集S2为大于等于K的数。这一操作是这样完成的：（A）、设定集合第一个数作为标准数K，设定指针I、J，I指向集合第一个数，J指向集合最后一个数；（B）、把J向左移（J：=J-1），直到找到一个SJ=K，则交换SI与SJ的位置，并把J前移（J：=J-1）；（D）、重复B、C直到I=J。（3）依次把S1、S2作为当前集合，以第一个数作为标准数K，重复第2步，直到S1、S2及其产生的子集元素个数为1。详细过程举例如下：原序：265371611159154819一：195151112659614837二：115151192659614837三：151115192659614837四：151115192659614837五：151115192659614837六：151115192637485961七：151115192637485961八：151115192637485961快速排序法是所有排序方法中速度最快、效率最高的方法。程序如下：uses crt;var n:array1.10 of integer; a:integer;procedure dg(x,y:integer);X，Y表示集合的左右边界，即把第X到第Y个数进行排序var i,j,b,c,d,e,f,k:integer;begin k:=nx;标准数 i:=x;I，J为指针 j:=y; repeat j:=j+1; repeat从J往左找到一个nj=k j:=j-1; until (njj); if i=k i:=i+1; until (ni=k) or (ij); if ij; if j-x0 then dg(x,j);如果集合中不止一个数则进入下一层递归，X，J为新边界 if y-i0 then dg(i,y); 如果集合中不止一个数则进入下一层递归，I，Y为新边界end;begin clrscr; for a:=1 to 10 do read(na); dg(1,10); for a:=1 to 10 do write(na:4);end.习题1、 楼梯有N级台阶，上楼可以一步上一级，也可以一步上两级，请编一递归程序，打印出所有从第1级上到第N级的走法。提示：S（N）=S（N-1）+S（N-2）。2、 编写一个程序，生成1，2，3，4，5五个数字的全排列。3、 编写一个程序，生成1，2，3，4，5，6六个数字中任选出四个数字的全排列。六、回 溯回溯算法与递归算法实现方法完全相同，所用的自定过程或函数几乎完全相同，只是在我们对它的理解以及这些函数/过程运行时有所不同。我们知道，回溯算法是解搜索问题的首要方法。搜索算法中的深度优先搜索就是比较简单的递归或回溯过程，即每次搜索的策略是：能进则进，不能进则退。这样每次递归或回溯到目标状态时就是一个答案，即这种搜索法能把满足条件的所有答案都找出来。因而这种算法就是用来搜索一个问题的所有答案。1、回溯：八皇后问题：在一个8X8的国际象棋棋盘上放置8个皇后，使它们不能互相攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）。试求出所有方法。分析：这是一个最经典的回溯问题。实际上，回溯与递是同曲异工，过程的编写完全相同，只不过递归一定能沿着一条路径走到一个答案；而回溯则不然，有时在一条路上找不到答案，这时需要程序往回走，再走其它分支。该问题我们已经在PASCAL语言中详细分析了，这里不再多说。无论是递归还是回溯，它们的过程都是类似以下：IF 递归结束条件满足 THEN 打印此时结果否则 继续往下递归；IF 回溯结束条件满足 THEN 打印此时结果否则 继续往下回溯 （隐含语句是如果无法继续回溯则往上回到上一层过程中）；请认真阅读以下程序，然后自己再编一遍：uses crt;var a:array1.100 of byte; t,m:integer;procedure qu(n:byte);var k,l:integer; b:boolean; zz:char;begin if n=9 then begin t:=t+1; writeln(t); for k:=1 to 8 do begin for l:=1 to 8 do if (akl) then write(.:3) else write(O:3); writeln; end; writeln; zz:=readkey; end else begin for