pascal-算法例题 - 图文(3)

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

--（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页

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

程，即深度优先搜索问题。

我们可以定义一个递归过程：MOVE（M，X，Y，Z）：表示把X上M片以Y为媒介移动到Z上，这里M<=N，X，Y，Z表示A，B，C三个不同的塔柱。每次移动一片底层盘片，都必须先把其上所有的盘都移走。这里产生的节点是唯一的，即只有一个答案。程序如下： var n:integer;

procedure move(m:integer;x,y,z:char); begin if m=1 then writeln(x:4,’==>’,z) else begin move(m-1,x,z,y);

writeln(x:4,’==>’,z); move(m-1,y,x,z);

end; end; begin readln(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:array[1..4] of integer; q,r:integer; begin

fournum(s,p[1],p[2],p[3],p[4]); pdsame:=true;

for q:=1 to 3 do begin

for r:=q+1 to 4 do begin

if p[q]<>p[r] then pdsame:=false; end; end; end;

procedure kblk(m:integer); {递归过程，卡布列克运算} var num:array[1..4] of integer;

第 13 页 共 31页

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

i,j,k,x,y:integer; begin

if m=6174 then begin

writeln('total times: ',t); end else begin

fournum(m,num[1],num[2],num[3],num[4]); for i:=1 to 3 do begin

for j:=i+1 to 4 do begin

if num[i]

num[i]:=num[j]; num[j]:=k; end; end; end;

x:=num[1]*1000+num[2]*100+num[3]*10+num[4]; y:=num[4]*1000+num[3]*100+num[2]*10+num[1]; writeln(x,' - ',y,' = ',x-y); t:=t+1; kblk(x-y); end; end;

begin {主程序} readln(n);

if (n<1000) or (n>9999) 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），直到找到一个S[J]<=K，则交换S[I]与S[J]的位置，并把I后移（I：=I+1）；（C）、把I向右移（I：=I-1），直到找到一个S[I]>=K，则交换S[I]与S[J]的位置，并把J前移（J：=J-1）；（D）、重复B、C直到I=J。 （3）依次把S1、S2作为当前集合，以第一个数作为标准数K，重复第2步，直到S1、S2及其产生的子集元素个数为1。 详细过程举例如下：

原序： [26 5 37 1 61 11 59 15 48 19] 一： [19 5 15 1 11] 26 [59 61 48 37] 二： [11 5 15 1] 19 26 [59 61 48 37] 三： [1 5] 11 [15] 19 26 [59 61 48 37] 四： 1 5 11 [15] 19 26 [59 61 48 37] 五： 1 5 11 15 19 26 [59 61 48 37]

第 14 页 共 31页

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

六： 1 5 11 15 19 26 [37 48] 59 [61] 七： 1 5 11 15 19 26 37 48 59 [61] 八： 1 5 11 15 19 26 37 48 59 61 快速排序法是所有排序方法中速度最快、效率最高的方法。程序如下： uses crt;

var n:array[1..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:=n[x];{标准数} i:=x; {I，J为指针} j:=y; repeat

j:=j+1;

repeat {从J往左找到一个n[j]<=k} j:=j-1;

until (n[j]<=k) or (i>j); if i<=j then begin b:=n[i]; {交换} n[i]:=n[j]; n[j]:=b;

i:=i+1; {左指针右移} end; i:=i-1;

repeat {从I往右找到一个n[i]>=k} i:=i+1;

until (n[i]>=k) or (i>j); if i<=j then begin b:=n[i]; {交换} n[i]:=n[j]; n[j]:=b; j:=j-1; end; until i>j;

if j-x>0 then dg(x,j); {如果集合中不止一个数则进入下一层递归，X，J为新边界} if y-i>0 then dg(i,y); {如果集合中不止一个数则进入下一层递归，I，Y为新边界} end;

begin

clrscr;

for a:=1 to 10 do read(n[a]); dg(1,10);

for a:=1 to 10 do write(n[a]:4); end. 习题

1、楼梯有N级台阶，上楼可以一步上一级，也可以一步上两级，请编一递归程序，打印出所有从第1级上到第N级的走法。提示：S（N）=S（N-1）+S（N-2）。 2、编一递归程序，求组合数Cn 。 已知：Cn?Cn?1?Cn?1

第 15 页 共 31页

mmm?1m