计算机算法设计题选.doc

中山纪念中学信息学奥林匹克算法设计题选
算法设计题选
（一）、算法设计：
一、筛选法

1：求1—100间的所有素数。
分析：用筛选法，先把2—100的数存到一个数组中，然后先把2的所有倍数删除掉（即让此数变为0），再删3的倍数，继续往上就是5的倍数，7的倍数……，最后，剩下的数(即数组中不为0的数)就是素数。
Var n:array[2..100] of integer;
I,j,k:integer;
Begin
For I:=2 to 100 do n[I]:=I;
I:=2;
Repeat
J:=1;
Repeat
J:=j+1;
K:=I*j;
if n[k]>0 then N[k]:=0;
Until (j+1)*i>100;
Repeat
i:=i+1;
until (n[i]>0) or (i>50);
Until i>50;
for i:=2 to 100 do if n[i]>0 then write(n[i]:4);
end.

另外，该题也可利用集合来做，同样用筛选法：
var ss:set of 2..100;
i,j,k:integer;
begin
ss:=[2..100];
for i:=2 to 50 do begin
j:=1;
repeat
j:=j+1;
k:=i*j;
if k in ss then ss:=ss-[k];
until k+i>100;
end;
for i:=2 to 100 do if i in ss then write(i:3);
end.
集合SS用来存放数

把SS中2至50的倍数全部删除

2：不相同的余数问题，即“秦王暗点兵”或“韩信点兵”：
有一楼房的楼梯级数很奇特，一步跨二级多一级，一步跨三级多二级，如果分用四、五、六、七去除级数分别余三、三、五、五。问这楼房共有多少级阶梯？（已知不超过400级）。
分析：已知级数不超过400级，我们可仿照求素数的方法，把1—400存进一个数组中，然后这些数用2、3、4、5、6、7分别去除，如果余数分别不为1、2、3、3、5、5就删除它，最后，最小的一个没有被删除的数就是解。
Var n:array[1..400] of integer;
I,j,k:integer;
Const a:array[1..6] of integer=(2,3,4,5,6,7);
b:array[1..6] of integer=(1,2,3,3,5,5);
Begin
For I:=1 to 400 do n[I]:=I;
for i:=1 to 6 do begin
for k:=1 to 400 do begin
if n[k]>0 then begin
if k mod a[i]<>b[i] then begin
n[k]:=0;
end;
end;
end;
end;
i:=0;
repeat
i:=i+1;
until n[i]>0;
write(n[i]:4);
end.

除数
余数

找最小的一个没有被删除的数
分析：用上述方法由于要删除的数非常多，因此速度较慢，我们可以反过来想，把满足余数条件的数加上记号，最后，最小的一个加上了六个记号的数就是答案。
Var n:array[1..400] of integer;
I,j,k:integer;
const a:array[1..6] of integer=(2,3,4,5,6,7);
b:array[1..6] of integer=(1,2,3,3,5,5);
Begin
For I:=1 to 400 do n[I]:=0;
for k:=1 to 400 do begin
for i:=1 to 6 do begin
if k mod a[i]=b[i] then n[k]:=n[k]+1;
end;
end;
i:=0;
repeat
i:=i+1;
until n[i]=6;
write(i:4);
end.

这样，速度要快很多。大家思考一下下题：《孙子算法》有题：今有物，不知其数。三、三数之，剩二；五、五数之，剩三；七、七数之，剩二。问物几何？（最小正数解）。

3：狼追兔子，兔子躲进了10个环形分布的洞的某一个中。狼在第1个洞中没有找到兔子，就间隔1个洞，到第3个洞中去找，也没找到兔子，就间隔2个洞，到第6个洞中去找。以后狼每次多隔1个洞去找兔子，……。这样狼一直找不到兔子。请问兔子可能躲在哪个洞中？
分析：该题看似简单，只要每次把狼找过的洞删除就行了，但是，这种删除操作的结束状态（条件）是什么呢？而且，狼的搜索过程中，如果要间隔11个洞时，我们是否可以认为就是间隔1个洞？
实际上，第一个问题应该是当狼回到第1个洞，并且又上间隔1个洞去找兔子时，就应该结束删除操作，因为此后的搜索是重复以前的搜索了，此时，那些没有被删除过的洞就是答案。这里，大家一定不能想当然地认为：结束条件就是只剩下一个洞的时候！题目中并没有说明只有一个答案，事实上是有四个洞的！
第二个问题也是可行的。因为只有10个洞，间隔11个洞和间隔1个洞的作用是相同的。
var d:array[1..10] of integer;
i,j,k,l:integer;
begin
for i:=1 to 10 do d[i]:=1;
i:=1;
j:=1;
repeat
d[i]:=0;
j:=j+1;
if j>10 then j:=j-10;
i:=i+j;
if i>10 then i:=i-10;
until (i=1) and (j=1);
for i:=1 to 10 do if d[i]>0 then write(i);
end.

习题
1、 作800—1000的素数表。
答案：809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997
2、 一位数学家和一些游客共81人不幸落入强盗手中，强盗把俘虏排成一队，宣布每天处理所有第2的N次方个俘虏（N>=0），而只放走剩下的最后一个。由于数学家身怀重任，不得不选择了一个恰当的位置而最终被放走。请问他归初排在第几个位置。 答案：80
3、 有一堆礼物，工作人员无论是分成二个一份，还是三个、四个、五个、六个一份，总是多一个。请问这堆礼物至少多少个？ 答案：61
4、 一付扑克中拿出所有的黑桃A……K按顺序排好。第一次翻出第一张牌——A，放在一边，再拿出第二张放到牌的最下面。以后每次都翻出一张牌，再把一张牌放到最后，问第八次翻出的牌是哪一张？ 答案：4

二、排序方法

本小节讨论几种排序方法。何为排序呢？就是把一些数字按递增或递减的顺序排列。例如：4，3，5，1，2这五个数，按从小到大的顺序排列是：1，2，3，4，5；按从大到小的顺序排列是：5，4，3，2，1。

1、双数组排序法：
用一个数组存放未经排序的数，然后按顺序找出未经排序数中的最大数，按顺序存放到另一个数组中，要考虑的问题是：怎样把未经排序数组中已经找出的数删除。
程序如下：
uses crt;
var n,m:array[1..10] of integer;
i,j,max,k:integer;
begin
clrscr;
for i:=1 to 10 do read(n[i]);{读入10个数}
for i:=1 to 10 do begin
max:=0;
for j:=1 to 10 do begin {从数组N找到最大的数}
if n[j]>max then begin
max:=n[j];
k:=j; {记住该位置}
end;
end;
m[i]:=max;{存入数组M中}
n[k]:=-30000;{删除该数，把值变为-30000}
end;
for i:=1 to 10 do write(m[i]:3);{打印已排好序的数}
end.

2、插入法排序：
插入法排序是把存放在数组中的未经排序的数逐个插入到另外一个数组中。如何找到每个数的正确位置呢？我们应该用动态查找的方法，从已排序的数组中从最左边开始查找，直到找到一个数大于等于待插入的数时，该数之前就是我们要找的位置。此方法可用数组来完成，也可用链表来完成。程序如下：
把数先存放在一个数组中，再逐个插入到另一个数组中：
uses crt;
var n,m:array[1..10] of integer;
i,j,k,l:integer;
begin
clrscr;
for i:=1 to 10 do read(n[i]); {读入10个数存放到数组N中}
m[1]:=n[1]; {在数组M中存放第一个数}
for i:=2 to 10 do begin {把数组N中第2到第10个数逐个插入到数组M中}
j:=0;
repeat
j:=j+1;
until (j=i) or (m[j]>=n[i]); {找到待插入的数在M中的位置}
if j=i then m[j]:=n[i] else begin
for l:=i-1 downto j do m[l+1]:=m[l]; {把该位置后的数后移}
m[j]:=n[i]; {把待插入的数放在正确位置}
end;
end;
for i:=1 to 10 do write(m[i]:3); {打印}
end.

3、冒泡法排序
冒泡法：这是最常用的一种排序方法，其实质是：先把数据存放在数组中，然后从第一个开始，分别与其后所有数据进行比较，如果第一个比其后某个数据小，则交换它们的值，一直到第一个与其后所有数据比较完，这时第一个数据就是最大的一个；然后再把第二个数据再与其后数据进行比较，比较完后，第二个数据则为第二大的，这样直到倒数第二个数据比较完后，整个数组就已经按从大到小的顺序排列了。其作用示意如下：
假设我们已经把6个数据分别存放在N[1]至N[6]中，其值分别为：3,1,5,9,2,6。
交换前的值为：
3，1，5，9，2，6
第一步，把第一个值与其后第一个进行比较，这时3>1，所以值不变：
3，1，5，9，2，6
第二步：把第一个值与其后第二个进行比较，这时3<5，所以值交换：
5，1，3，9，2，6
第三步：把第一个值与其后第三个进行比较，这时5<9，所以值交换：
9，1，3，5，2，6
……
……
当第一个值与其后所有值比较完后，第一个值已经是最大的，数组值为：
9，1，3，5，2，6
这时，重复上述第一步的操作，只是把第一个值换成第二个值，第一个值即第二个值与其后第一个值进行比较，这时1<3，所以交换其值：
9，3，1，5，2，6
第二个值与其后所有值比较完后，数组值为：
9，6，1，3，2，5
再重复进行第三个值与其后值的比较，直到第五个值与第六个值比较完后，这时数组的值已经变为：
9，6，5，3，2，1
至此，数组已经按从大到小的顺序排好了。

程序如下 ：[例6、1]
Var n:array[1..10] of integer;
I,j,t:integer;
Begin
For I:=1 to 10 do Readln(n[I]);
For I:=1 to 9 do begin
For j:=I+1 to 10 do begin
If n[I]<n[j] then begin
T:=n[I];
N[I]:=n[j];
N[j]:=t;
End;
End;
End;
For I:=1 to 10 do begin
Write(n[I]:5);
End;
End.
说明一个数组型变量

从键盘读入10个数据存放在数组N中
参加比较的第一个数据为第1至第9个。
第二个数据为第一个数据之后所有的数据
如果n[I]<n[j]则用以下三句来交换其位置

打印排序后的结果

四、选择排序：
设数组中有N个数，取I=1，2，3，……N-1，每次找出后N-I+1个数字中最小的与第I个数字交换位置。程序如下：
uses crt;
var n:array[1..10] of integer;
i,j,k,t,min:integer;
begin
clrscr;
for i:=1 to 10 do read(n[i]);
for i:=1 to 9 do begin
min:=30000;
for j:=i to 10 do begin {在第I到第10个数中找到最小的一个}
if n[j]<min then begin
min:=n[j];
k:=j; {记录该位置}
end;
end;
t:=n[i];
n[i]:=n[k];
n[k]:=t;
end;
for i:=1 to 10 do write(n[i]:4);
end.

5、快速排序：
（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]
六： 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、设有一块1X1正方形钢板，现需将它分成N个小正方形的钢板。
例如：

输出格式例：0.25X0.25:7
0.75X0.75:1 （表示分割成0.25X0.25的正方形7个，0.75X0.751个）
分析： （1）将一个正方形分成4个，则可增加3个正方形。
（2）以6、7、8个正方形时为基础，则可得到增加的结果：
6 7 8
9 10 11
12 13 14
…………
因此由上述递增关系可推得一个递归关系。

2、在平面上有N条直线，且无三线共点，问这些直线能组成多少种不同的交点数。例如：
分析：（1）N条无三条直线交于一点的直线最多可能有Cn2个交点，即1/2*N*(N-1)个交点。
（2）对于N条直线，如果N条全部平行，则交点数为0；
如果一条不平行，则交点数为N-1；
如果有两条不与其它平行，则有两种情况，一种这两条直线平行，则交点有（N-2）*2；一种是这两条直线不平行，则交点有（N-2）*2+1。
(3)由上述可知：N条直线如果有R条直线平行，相当于（N-R）条直线的各种情况再加上R*（N-R）个交点。也就是说：
我们已知： 2条直线的交点情况是：0，1；
3条直线的交点情况是：0，2，3；
4条直线的交点情况可分为：（1）4条直线平行，0个交点；（2）3条直线平行，1条直线的情况+3*1=3个交点；（3）2条直线平行，2条直线的情况+2*2个交点，也就是有0+4，1+4两种情况；（4）1条直线平行，3条直线的情况+1*3，也就是有3，5，6三种情况。综合上述分析，可知：4条直线的交点情况有：0，3，4，5，6五种情况。
也就是说，要计算N条直线的情况，应先计算N-1、N-2、……、2条直线的情况。我们可以用数组来存放2、3、……N条直线的各种情况。

3、哈夫曼编码：给定一个字符串（假定全由26个小写字母中的前若干个字母组成，总长度不超过50个字符），对字符串每个字符进行编码，编码原则如下：
（1）只能用0，1字符串对字符进行编码；
（2）要求根据编码识别字符串时不会出现混乱、无法识别的情况；
（3）要求字符串编码后的总长度最短。
例如：对于字符串：abbabcdefcdabeg，其编码方式可以如下：
a-000, b-001, c-010, d-011, e-100, f-101, g-110
这时总长度为45。
但其编码方式也可以如下：
a-01, b-00, c-100, d-101, e-110, f-1110, g-1111
这时总长度为42。
分析： （1）字符串中共有多少个不同的字符，以及每个字符出现的次数。毫无疑问，要使总长度最小，出现次数越多的字符的编码应该越短。
（2）位数少的编码与位数多的编码如何才能不混乱呢？应该从左边前若干位进行区别。例如，编码有一个为“0”时，就不能出现“00”，“01”，“001”，“010”等等编码。当编码中有一个为10时，就不能出现100，101，1000等编码。

四、递 归

这里我们将再一次讨论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（N>1）；（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（X>1），求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 begin
Dg:=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 begin
For 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
把答案数及答案打印出来
从此句中返回调用此过程的上一过程
从A—E五个字符中取一个
如果这个字符在已经取得的N-1个字符中没有出现
就调用下一次递归，即调用自己，只不过参数N变为N+1，即下次将取第N+1个字符（相对于当前来说），而输入的S参数也变为已经加入第N个字符的新字符串。

程序主体开始
答案总数初值为0
调用递归过程，输入值1表示要找第1个字符，’’表示已经找到的0个字符
上述程序的运行过程如下：
过程步骤
N的值
S的值
1.以参数1，’’输入递归过程DG，开始递归第一层
1
‘’
2.取到第一个字符，’A’
1
‘A’
3.以参数(N+1,S+I), 即(2,’A’)调用第二层递归,即第一层过程尚未结束, 就调用第二层递归过程, 此时,第一层过程保留在内存中,程序执行到循环语句的’A’, 程序返回此过程中时,将继续执行此循环语句,而此时此循环已被挂起
2
‘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条件满足,将不执行下一层递归,而是打印出第一个答案’ABCDE’, 并结束此次递归过程, 这意味着,程序将回到调用第六层递归的第五层递归的循环语句中
6
‘ABCDE’
接上. 程序回到第五层递归过程中, 而此时, 循环已经执行到’E’, 无其它字母可加入,所以第五层递归将被自然结束,返回第四层递归过程的循环语句,注意: 此时,N已经变成5, 而S为’ABCD’, 与开始进入第五层递归是一致的,这就是把N和S作为形式参数的意义之处
5
‘ABCD’
接上. 程序回到第四层递归中, 此时的循环执行到’D’, 还有’E’可取
4
‘ABCE’
接上. 取完’E’后,程序又调用第五层递归,此时可取’D’,
5
‘ABCED’
接上. 进入第六层递归,打印已经取得的新答案:’ABCED’

接上. 取得新答案后, 返回第五层, 没有字符可取, 正常结束再返回第四层, 仍没有字符可取,再返回第三层,此时,第三层刚取完’C’,可取’D’
3
‘ABD’
接上,再重复上述过程,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）--（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);
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 begin
For 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
答案打印(去掉最后一个加号)
从此句中返回调用此过程的上一过程
从1—N的整数中取一个整数
转换为字符串
调用下一次递归，即调用自己，只不过参数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;
func