pascal-算法例题 - 图文

中山纪念中学信息学奥林匹克算法设计题选

[例1]有一个数列N，已知：N（1）=1，N（X）=N（X-1）*3-1（X>1），求N（100）；

我们已经知道，由递归关系，我们要求N（100），就必须知道N（99）??N（1），而最终N（1）是已知的，所以这个递归关系我们就可以用PASCAL语言很好地表现出来。以下我们用递归函数来完成，请大家注意递归的实现方法，即自己调用自己。 Var n100:integer; 定义程序主体中的变量 Function dg(n:integer):integer; 定义自定义函数DG，形式参数1个，用以记录现在是推Begin 算到了第几个数。 If n:=1 then dg:=1 递归出口是当N等于1时，DG的值为1 Else begin Dg:=dg(n-1)*3-1; 如果N不等于1，我们就继续递归，这就是递归关系式 End; End; Begin 程序主体 N100:=dg(100); 调用递归函数 Writeln(n100); End. 由上可以看出，用递归函数来实现算法，程序主体可以变得非常简单，只需少数几句即可。而递归函数就显得至关重要了，由上述程序可以看出，递归函数的实现实际上就是一个自己调用自己的函数。直到调用到已知的数为止。递归问题我们还将在递归过程中详细分析。

由上可见，递归过程实际上只有一句，IF 条件 THEN 出口 ELSE 调用下一次递归；

递归过程

我们从一个例题中来看看递归的实际实现及运行过程。

[例2]打印‘A’、‘B’、‘C’、‘D’、‘E’这五个字符任意排列的所有情况。

分析，此题可用五重循环来做，但那样就把此题给复杂化了，运行速度也要慢很多，而此题用递归过程来做的话就要简单许多。我们把递归过程定为每次从五个字符中取一个字符，当然这个字符必须与已经取得的字符全不相同，而我们取得的字符存放在一个字符串中，并把它作为形式参数（这一点至关重要，否则答案将完全错误）。当我们已经取完五个字符后，在取第六个字符时，递归过程就将结束。这就是递归的出口。这样我们就能把所有结果找出来。程序如下： Var t:longint; 计算答案总数的计数器 Procedure dg(n:integer;s:string); 递归过程有两个形式参数，N表示当前取第N个字符，SVar I:char; 存放已经取得的N-1个字符； Begin If n=6 then begin N等于6时，递归到了一个答案 T:=t+1; 答案总数加1 Writeln(t:5,’ ‘,s); 把答案数及答案打印出来 End else begin 从此句中返回调用此过程的上一过程 For I:=’A’ to ‘E’ do begin 从A—E五个字符中取一个 If pos(I,s)=0 then begin 如果这个字符在已经取得的N-1个字符中没有出现 Dg(n+1,s+I); 就调用下一次递归，即调用自己，只不过参数N变为N+1， End; 即下次将取第N+1个字符（相对于当前来说），而输入End; 的S参数也变为已经加入第N个字符的新字符串。 End; End; Begin 程序主体开始 T:=0; 答案总数初值为0 Dg(1,’’); 调用递归过程，输入值1表示要找第1个字符，’’表示已End. 经找到的0个字符 上述程序的运行过程如下： 过程步骤 N的值 S的值 第 9 页 共 31页

中山纪念中学信息学奥林匹克算法设计题选 ‘’ 1.以参数1，’’输入递归过程DG，开始递归第一层 1 2.取到第一个字符，’A’ 1 ‘A’ 3.以参数(N+1,S+I), 即(2,’A’)调用第二层递归,即第一层过程尚未结束, 就2 ‘A’ 调用第二层递归过程, 此时,第一层过程保留在内存中,程序执行到循环语句的’A’, 程序返回此过程中时,将继续执行此循环语句,而此时此循环已被挂起 4.进入第二层递归,取到第二个字符,此时’A’已不能取, 只能取’B’ 2 ‘AB’ 3.以参数(N+1,S+I), 即(3,’AB’)调用第三层递归,即第一层及第二层过程尚3 ‘AB’ 未结束, 就调用第三层递归过程, 此时,第一,二层过程保留在内存中, 5.进入第三层递归,取到第三个字符,此时’A’和’B’已不能取, 只能取’C’ 3 ‘ABC’ ???? 接上. 以参数(N+1,S+I), 即(5,’ABCD’)调用第五层递归,即第一层到第四层5 ‘ABCD’ 过程尚未结束, 就调用第五层递归过程, 此时,第一至四层过程留在内存中, 接上. 进入第五层递归,取到第五个字符,此时只能取’E’ 5 ‘ABCDE’ 接上. 以参数(N+1,S+I),即(6,’ABCDE’)调用第六层递归,即第一层到第五层6 ‘ABCDE’ 过程尚未结束, 就调用第六层递归过程, 此时,第一至四层过程留在内存中 接上. 进入第六层递归过程, 此时N=6条件满足,将不执行下一层递归,而是6 ‘ABCDE’ 打印出第一个答案’ABCDE’, 并结束此次递归过程, 这意味着,程序将回到调用第六层递归的第五层递归的循环语句中 接上. 程序回到第五层递归过程中, 而此时, 循环已经执行到’E’, 无其它字5 ‘ABCD’ 母可加入,所以第五层递归将被自然结束,返回第四层递归过程的循环语句,注意: 此时,N已经变成5, 而S为’ABCD’, 与开始进入第五层递归是一致的,这就是把N和S作为形式参数的意义之处 接上. 程序回到第四层递归中, 此时的循环执行到’D’, 还有’E’可取 4 ‘ABCE’ 接上. 取完’E’后,程序又调用第五层递归,此时可取’D’, 5 ‘ABCED’ 接上. 进入第六层递归,打印已经取得的新答案:’ABCED’ 接上. 取得新答案后, 返回第五层, 没有字符可取, 正常结束再返回第四层, 3 ‘ABD’ 仍没有字符可取,再返回第三层,此时,第三层刚取完’C’,可取’D’ 接上,再重复上述过程,N及S的取值情况如下: 4 ‘ABDC’ 5 ‘ABDCE’ 4 ‘ABDE’ 5 ‘ABDEC’ 3 ‘ABE’ 4 ‘ABEC’ 5 ‘ABECD’ ?????? ?? ?? 从上述分析中，可以看出整个递归过程完全是动态的，不停地在各层递归过程之间调用，也包括返回第一层的情况，这样就能把所有答案都找出来。下面我们以取‘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）

第 10 页 共 31页

中山纪念中学信息学奥林匹克算法设计题选

--（16）这16个节点是按顺序生成的，结果共有6个，这6个节点产生的顺序也可看出是按数字大小来产生的。整个递归过程共产生了三层节点，每个目标节点都是直线产生，每条能够走通的路线都一定能产生出目标节点，这就是递归，同样，这就是我们所说的深度优先搜索问题，即搜索方向是直向深处的节点的。

另外，上述图中，程序经过每个节点的顺序我们也能很清楚的说出了：（开始）1?2?3?4?3?2?5?6?5?2?1?7?8?9?8?7?10?11?10?7?1?12?13?14?13?12?15?16?15?12?1（结束）。

上述到达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); 递归过程有两个形式参数，N表示剩下Var I:integer; 的整数是多少，S存放已经取得的数字 C:string; Begin N等于0时，递归到了一个答案 If n=0 then begin 答案总数加1 T:=t+1; 答案打印(去掉最后一个加号) Writeln(t:5,’ ’,a,’= ‘,copy(s,1,length(s)-1)); 从此句中返回调用此过程的上一过程 End else begin 从1—N的整数中取一个整数 For I:=1 to n do begin 转换为字符串 Str(I,c); 调用下一次递归，即调用自己，只不过 Shu(n-i,s+c+’+’); 参数N变为N-i，即下次将用N-I来减，End; 输入的S参数也变为已经加入新取的 End; 这一个数字及加号。 End; 程序主体开始 Begin 答案总数初值为0 T:=0; 读入A Readln(a); 调用递归过程，输入值A及’’（空字符 Shu(a,’’); 串） End.

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); 如果M等于1就结束递归，否则用公式M*DGend; （M-1）调用M-1的阶乘 begin 第 11 页 共 31页

中山纪念中学信息学奥林匹克算法设计题选 readln(n); writeln(dg(n)); 调用递归函数 end. 上述程序中设计了一个递归函数，虽然只有一个语句，但其作用却是非常大的。它的作用过程请大家根据已经掌握的递归知识自已分析一下。

下面我们看一个数据结构的概念——树，树的定义如下： 一个树是N个元素的有限集合。 （1）每个元素称为结点；

（2）有一个特别的结点称为树的根或根结点；

（3）除根结点外，其余结点能分成M（M>=0）个不相交的集合，而每个集合又都是树，这些集合称为这个

树的子树（即可把某一非根结点发出的所有结点作为一个子树）。

在第（3）点中，又引用了树的概念，这就是递归。我们可用下图来说明树与子树的关系： 1

2 3

4 5 6 7

8 9 10 11 12 从上述树中可以看出，根结点为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。所以，我们可得到以下公式：

1F(n)?{F(n?1)?F(n?2)n?1,2 n?2程序如下： 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上??。这样就是一个递归过

第 12 页 共 31页