pascal-算法例题 - 图文

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

算法设计题选

（一）、算法设计：

一、筛选法

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; 集合SS用来存放数 i,j,k:integer; begin ss:=[2..100]; for i:=2 to 50 do begin 把SS中2至50的倍数全部删除 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. 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); 余数 第 1 页 共 31页

中山纪念中学信息学奥林匹克算法设计题选 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; 第 2 页 共 31页

中山纪念中学信息学奥林匹克算法设计题选 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);{打印已排好序的数}

第 3 页 共 31页

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

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，所以值不变： 第二步：把第一个值与其后第二个进行比较，这时3<5，所以值交换： 第三步：把第一个值与其后第三个进行比较，这时5<9，所以值交换： ?? 当第一个值与其后所有值比较完后，第一个值已经是最大的，数组值为： 这时，重复上述第一步的操作，只是把第一个值换成第二个值，第一个值即第二个值与其后第一个值进行比较，这时1<3，所以交换其值： 第二个值与其后所有值比较完后，数组值为： 再重复进行第三个值与其后值的比较，直到第五个值与第六个值比较完后，这时数组的值已经变为： 至此，数组已经按从大到小的顺序排好了。 程序如下 ：[例6、1] Var n:array[1..10] of integer; 说明一个数组型变量 第 4 页 共 31页

3，1，5，9，2，6 3，1，5，9，2，6 5，1，3，9，2，6 9，1，3，5，2，6 ?? 9，1，3，5，2，6 9，3，1，5，2，6 9，6，1，3，2，5 9，6，5，3，2，1 中山纪念中学信息学奥林匹克算法设计题选 I,j,t:integer; Begin For I:=1 to 10 do Readln(n[I]); 从键盘读入10个数据存放在数组N中 For I:=1 to 9 do begin 参加比较的第一个数据为第1至第9个。 For j:=I+1 to 10 do begin 第二个数据为第一个数据之后所有的数据 If n[I]

四、选择排序： 设数组中有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]

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。

第 5 页 共 31页

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

详细过程举例如下：

原序： [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.

第 6 页 共 31页

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

三、数论问题

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条无三条直线交于一点的直线最多可能有Cn个交点，即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）个交点。也就是说：

第 7 页 共 31页

2

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

我们已知： 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）是已知的了。

而实际上，上述推算过程就是递归过程。即要完成某个计算，必须先完成其前的另一个计算，以此类推，直到推到一个已知的值为止。

第 8 页 共 31页

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

[例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页

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

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

我们可以定义一个递归过程：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

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

3、一个凸N边形，通过N边形内部互不相交的对角线，把N边形拆分成若干个三角形，不同拆分方案的数目用H（N）表示。已知递归函数如下：

H（N+1）=H（2）*H（N）+H（3）*H（N-1）+??+H（N）*H（2），（为什么？） H（2）=1。

请编写计算H（N）的递归程序。

4、阿克曼函数（ACKMANN）A（X，Y）中，X、Y定义域是非负整数，函数值定义为： A（X，Y）=Y+1 （X=0） A（X，0）=A（X-1，1） （X>0,y=0） A(X,Y)=A(X-1,A(X,Y-1)) (X,Y>0) 设计一个递归程序，求A（X，Y）。

5、某人写了N封信和N个信封，结果所有的信都装错了信封。求共有多少种情况。提示：

D（N）=（N-1）*（D（N-1）+D（N-2））， D（1）=0，D（2）=1。为什么？

6、编写一个程序，生成1，2，3，4，5五个数字的全排列。

7、编写一个程序，生成1，2，3，4，5，6六个数字中任选出四个数字的全排列。

六、回 溯

回溯算法与递归算法实现方法完全相同，所用的自定过程或函数几乎完全相同，只是在我们对它的理解以及这些函数/过程运行时有所不同。

我们知道，回溯算法是解搜索问题的首要方法。搜索算法中的深度优先搜索就是比较简单的递归或回溯过程，即每次搜索的策略是：能进则进，不能进则退。这样每次递归或回溯到目标状态时就是一个答案，即这种搜索法能把满足条件的所有答案都找出来。因而这种算法就是用来搜索一个问题的所有答案。 1、回溯：八皇后问题：在一个8X8的国际象棋棋盘上放置8个皇后，使它们不能互相攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）。试求出所有方法。 分析：这是一个最经典的回溯问题。实际上，回溯与递是同曲异工，过程的编写完全相同，只不过递归一定能沿着一条路径走到一个答案；而回溯则不然，有时在一条路上找不到答案，这时需要程序往回走，再走其它分支。该问题我们已经在PASCAL语言中详细分析了，这里不再多说。 无论是递归还是回溯，它们的过程都是类似以下： IF 递归结束条件满足 THEN 打印此时结果 否则 继续往下递归； IF 回溯结束条件满足 THEN 打印此时结果 否则 继续往下回溯 （隐含语句是如果无法继续回溯则往上回到上一层过程中）； 请认真阅读以下程序，然后自己再编一遍： uses crt;

var a:array[1..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;

第 16 页 共 31页

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

writeln(t);

for k:=1 to 8 do begin

for l:=1 to 8 do if (a[k]<>l) then write('.':3) else write('O':3); writeln; end; writeln; zz:=readkey; end else begin

for k:=1 to 8 do begin

b:=true;

for l:=1 to n-1 do if (a[l]=k) or (abs(a[l]-k)=abs(l-n)) then b:=false; if b then begin

a[n]:=k; qu(n+1); end; end; end; end;

begin clrscr; t:=0; qu(1); writeln;

writeln(' total ',T,'');readln; end. 2、回溯：分派整数1、2、3??8给以下各方框，并保证没有两个相邻的方框（垂直相邻，斜对角相邻或水平相邻）含有连续的整数。写一个程序，找出所有的分派方案。 分析：此题与八皇后问题相似，大家自己把程序编出。 3、回溯：在一个NXN的方格网上从某一点（I，J）开始，沿水平、垂直或对角线向前进，最后回到（I，J），形成一个不相交的封闭的折线，设此封闭折线不与方格网的边界相交，求此封闭折线所围成的面积。面积的计算方法是统计折线上以及它所围成的封闭区域中的水平线与垂直线交点的数目。如图中围住了41个点（包括折线本身上的点），因而面积为41。 输入格式：文件读入，格式如下（定义走法：U向上，D向下，L向左，R向右，UL、UR、DL、DR依次累推）： 5 2 表示起点为（5，2） R 2 表示向右走三点 DR 2 表示向下右走三点 D 3 表示向下走四点 L 1 表示向左走一点 D 2 表示向下走二点

第 17 页 共 31页

中山纪念中学信息学奥林匹克算法设计题选 分析：（1）、用一个二维数组来存放该网格，折线经过的点的值存为1，不经过的点存为0。注意：该题的判错很重要，如何判断折线是否相交？如何判断折线是否闭合？ （2）存好数组后，我们得到一个0、1数字矩阵，这时应该如何判断折线图形的面积呢？ （3）实际上，题目中重点说明了该图形不与边界相交，我们完全可以从某个边界点入手，把它压入栈，然后将其周围所有相邻元素中不为1的点的值改为2，表示该点已经被处理。 （4）再把本次改成2的点逐个压入栈进入回溯下一层，将其周围所有不为1的相邻点的值也改为2，直到所有这样的点都被处理完。这时我们得到的网格是数字0、1、2组成的矩阵，所有数字为2的点都没有被折线包围。数字为0，1的点的总数就是所要求的面积。 4、回溯：有一个由N个数组成的序列，有0，1两种数，要求在任一个数前1的个数不得超过0的个数，求出所有这样的序列。 分析：用回溯过程来产生这个序列，每次可把0或1加入已产生序列的未尾，但当加入数字1时，使得当前的1的个数超过0的个数，这就表示该处不能加入数字1。 注意：结果序列如果用数组存放可作为全局变量；如果用一个字符串来存放就只能作为回溯过程的输入参数之一。 5、回溯：以下列方式向5X5矩阵中填入数字。设数字I(1<=I<=25)已被置于座标位置（X,Y），则数字I+1的座标位置应为（E，W），（E，W）可根据以下关系由（X，Y）算出： （1）（E，W）=（X±3，Y）； （2）（E，W）=（X，Y±3）； （3）（E，W）=（X±2，Y±2）。 编写一个程序，当数字1被指定于某个起始位置时，列举出其它24个数字应在的位置；列举出该条件下的所有可能方案，输出所有可能的情况。 6、回溯：编一程序，从键盘输入数字R，计算机自动检查在下列算式的“（）”中能否填上“+”或“-”号凑成相应的等式。如能凑成，则打印出这些算式。如不能则打印“NO ANSWER”。 1( )2( )3( )4( )5( )6( )7( )8( )9=R 7、一笔画问题：一个平面图如下，仅有两点为奇结点（某个点连接的线数为奇数则为奇结点，否则为偶结点），其余为偶结点，以这两个点为起、终点。给出一条经过各边一次且仅一次的路径。打印所有结果。

3 5 4

1 9 10 2

7 6 8

8、有NXM张邮票边在一起，但其中某一张被挖掉了。如下图就5X4的邮票的形状和编号，其中第11张被挖掉了，现在要求从这些邮票中撕出4张连在一起的邮票，请打印出所有答案。 1 2 3 4 5 6 7 8 9 10 12 13 14 15 16

第 18 页 共 31页

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

17 18 19 20 输入格式： 5 4 表示5行4列 3 3 表示第3行第3列的邮票被撕掉了，如果输入0 0则表示没有撕掉邮票。

输出格式 1-2-3-4 以下若干行为各种方案 1-5-9-13 5-9-13-17 1-5-6-7 1-6-7-10 ??

七、排列组合问题：

一、排列：如：1、2、3三个数字，排列成一队，共有多少种排法。可知，有以下几种：

123，132，213，231，312，321 共六种情况。

实际上，我们可以把三个数字的全排列看成是：先取第一个数字（有三种情况），再取第二个数字（有两种情况），然后取第三个数字，则只有一种情况了。所以，三个数字的全排共有3*2*1种情况。这就是乘法原则。

乘法原则：如果一件事可分成若干个小步骤来完成，每步又有数种可能性，则该事件的可能性总数为所有小步骤的可能性之积！例如：有以下图表示三个声城市之间的路径：

由上图可见，A到B有两条路可走，B到C有三条路可走，则A到C有多少种走法呢？ 根据乘法原则可知：是2*3=6条走法。

再如，有6个人，选出三个来排成一列，共有多少种排法呢？

我们知道，选第一个人时，有6种可能性；然后选第二个人时，有5种可能性；再选第三个人时，有4种可

A B C 能性。所以，从6个人中选3个人排成一列，共有：6*5*4=120种排法。

排列问题我们用P来表示，Pnm表示从N个物件中选出M个来排列的所有情况。如：P63表示从6个物件中选出3个的排列情况。并且我们可以得到以下公式：

Pnm?n*(n?1)*(n?2)......(m?1) 如：P63?6*5*4?120

共M个数相乘 共3个数相乘

3例：从5个人中选出3个人排成一列，共有P5?5*4*3?60种排法。

二、组合：组合问题与排列问题非常相似，如：从5个人中选出3个人来，共有多少种选法？从N个人中选出M

3个人来表示为：Cn，所以上题可表示为求：C5。

m请大家注意上题，并没有提到排成一列的问题，也就是说，只要把人选出来，并不用排列他们。这就是组合问题，而这样情况总数会少掉多少呢？我们知道，从5个人中选3个人排列，共有P5?5*4*3?60种排法。这实际上是从5个人中选出3个人来，然后再把他们排列一下，每次有P33?6种排法。所以，如果只是选出3个人的组合，就应该是P/P3533种。所以我们可以得到下列公式：

3333PnmC?m。这就是组合的公式。

Pmmn所以，从5个人中选出3个人来，共有：C5?P5/P3?60/6?10种选法。如：从1至5五个数字中选出3个的所有选法有：123，124，125，134，135，145，234，235，245，345。 除了乘法原则外，我们在做排列组合问题时，还经常用到以下原理或原则：

加法原则：如果一件事的完全有几种大情况，每种大情况都又有几种可能性，则该事件的可能性总数为这几

第 19 页 共 31页

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

种大情况的可能性之和。

鸽笼原理：也叫抽屈原理。即有N+1只鸽子，N个鸽笼，如果要把所有的鸽子都装进鸽笼，则至少有一个鸽笼中至少有两只鸽子。

例：有2名女生，5名男生，再要从中选出四人，且至少要一个女生，问共有多少种选法？ 分析：该题可分成两种情况：

131、 只选一个女生：又分成两部分，一是选女生，有C2?2种选法；二是选男生，有C5?10种选法。所以

13只选一个女生的选法有：C2*C5?20种。

22、 选二个女生：第一部分选女生，只有一种选法，就是两个人都选；第二部分是选男生，有C5?10种。

所以选两个女生时的选法有10种。

所以，该题的答案应该是上述两种情况的选法数相加，共有30种选法。

八、概率问题：

一件事中，各种情况都有可能发生，其中某种或某些情况发生的可能性是多少呢？这就是概率问题。答案是指定某种或某些情况发生的种数除以所有情况的种数，所得的大于等于0，小于等于1的一个小数。

例如上题中，如果改为有2名女生、5名男生，从中选出4个人，问其中一定有一个女生的概率是多少？

134答案是：所有的可能性是：C7 *C5?20。所以，概率为20/30=0.66。?35；有一个女生的可能性是：C2

九、分治策略

1、分治策略：求N个数A1，A2，A3??AN中的最大值MAX和最小值MIN。 分析：分治策略是指这样一种算法：把一个大问题分解成若干个小问题，比如：计算教室面积时，可把它分成若干小块，分别计算面积后再相加。步骤为：分割——求解——合并，共三步。 该题如果N等于1时，MAX=MIN=A1，如果N=2时，MAX=A1，MIN=A2或MAX=A2，MIN=A1，这是非常简单的，所以此题可把所有的数作为一个序列，每次从中取出开头两个数，求共MAX，MIN，然后再从剩余的数中取开头两个数，求其MAX、MIN后与前一次的MAX、MIN比较，可得出新的MAX、MIN，这样重复下去，直到把所有的数取完（注意最后一次取可能是只有一个数），MAX，MIN也就得到了。这就是典型的分治策略。注意：这样做与把所有数字排序后再取MAX、MIN要快得多。 2、分治策略：找出N个整型元素中的第K个最小元素。 分析：当然，此题用排序方法做也要花不少时间，如果用分治策略，可这样考虑：按某个元素M（称为分划元素）把这N个元素分成3个子序列，S1中存放小于M的数，S2中存放等于M的数，S3中存放大于M的数。我们可以很容易地知道这三个子序列中元素的个数，即可以确定我们要找的第K个最小元素在哪个子序列中。这样，就等于是让我们再在某个子序列中找某个数，把一个大问题划成了小问题了，递归地做下去，最后就能找到第K个最小元素。分划元素可简单地取序列中的第一个数。

N

3、分治策略：计算X。

N2N/2N2P1

分析：如果N为偶数，则X=（X）；如果N为奇数，则X=X*X，（2P+1=N）转化成了偶数次方。这样递

0

归地做下去，直到计算X为止。

十、动态规划

1、动态规划：（最优策略）在一个需要多步决策的过程中，每一步都可能有若干种方案可供选择，一旦每一步的方案都选择好后，即构成了一个解决问题的决策策略。问题往往有一种标准，需要衡量决策的优劣，以确

第 20 页 共 31页

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

定一种最优化的决策。这种问题用枚举法把所有决策都找出来再进行判断当然也可以做到，但往往在时间与内存空间上出问题。这种情况都用动态规划法来解，以求得最优策略。 最优策略可解释为：无论过程的初始状态或初始决策怎样，以后的最优策略只取决于由最初策略所确定的当前状态。例如：从城市A1出发经过A2，A3，A4到达A5，如果这条路线是从A1到A5的最短路线，则由A2经A3，A4到达A5也一定是从A2到A5的最短路线。根据最优原理的原则，动态规划在每种状态下列出各种可能的局部解，然后按某些条件，从局部解中挑出那些有可能产生最佳解的结果而舍弃其余，从而大大缩小了计算量。 例：如上图：顶点（1）为起点，顶点（12）为终点，试找出从起点至终点的一条最短路径。 分析：由上图可知，要找（1）到（12）的最短路线，必须分四步走，D1到D2有四个选择，D2到D3有三个

选择，D3到D4有三个选择，D4到D5只有一个选择。要找到的（1）到（12）的最短路径，也同样应该是该条路线中某个点到（12）的最短路径。因此，我们可以反其道而行之，从（12）出发，找出到每一个点的最短路线。例如：

（1）（12）到（11）的最短路线为5，（12）—（10）：2，（12）—（9）：4 （2）（12）—（8）：7；（12）—（7）：5；（12）—（6）：6

（3）（12）—（5）：15；（120—（4）：18；（12）—（3）：8；（12）—（2）：7 （4）（12）—（1）：15

并且可知：路线为：（1）—（3）—（6）—（10）—（12） 程序如下，请看懂后自己再编一次：

const d:array[1..12,1..12] of integer=(

(0,9,7,3,2,0,0,0,0,0,0,0), (9,0,0,0,0,4,2,11,0,0,0,0), (7,0,0,0,0,2,7,0,0,0,0,0), (3,0,0,0,0,0,0,11,0,0,0,0), (2,0,0,0,0,0,11,8,0,0,0,0), (0,4,2,0,0,0,0,0,6,4,0,0), (0,2,7,0,11,0,0,0,4,3,0,0), (0,11,0,11,8,0,0,0,0,5,6,0), (0,0,0,0,0,6,4,0,0,0,0,4), (0,0,0,0,0,4,3,5,0,0,0,2), (0,0,0,0,0,0,0,6,0,0,0,5), (0,0,0,0,0,0,0,0,4,2,5,0)); var lenmin:array[1..12] of integer; father:array[1..12] of integer; x,y,z,min:integer; begin

lenmin[12]:=0; father[12]:=0;

for x:=11 downto 1 do begin min:=10000;

for y:=x to 12 do begin if d[x,y]<>0 then begin

if lenmin[y]+d[x,y]

第 21 页 共 31页

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

end; end;

lenmin[x]:=min; father[x]:=z; end; x:=1;

writeln(lenmin[1]); repeat

write(x,'-->'); x:=father[x]; until x=0; end.

2、动态规划：设有由N个不相同的整数组成的数列，记为A1，A2，??AN，且AI<>AJ（I<>J）。请找出此数列中最长递增子序列。N及N个数由键盘输入。

分析：该题中动态规划与分治结合起来的作用是：

（1）找出由数组中第一个数出发的最长递增子序列，并记下起始点及长度为暂时结果；

（2）从上述子序列后第一个数再开始找其最长递增子序列，如果长度大于（1）中的长度则把此子序列的起始点及长度记下暂时结果。

（3）继续（2），直到数组中的数用完，把记下的结果从数组中找出子序列打印出来即可。 3、动态规划：下图是城市道路的示意图。每条边上的数字为该段街道的长度。求从A地到B地（只允许往右或往上走）的最短路径及长度。

4、动态规划：某工厂购进1000台机器，准备生产P1和P2两种产品。若生产产品P1，每台机器每年可收入4500元，但机器损坏率达65%。若生产产品P2，每台机器每年可收入3500元，但损坏率仅有35%。三年后机器全部淘汰，购入新机器。应该如何安排生产（计划以一年为周期），使三年收入最多？ 分析：假设X1、Y1表示第一年时生产P1的机器台数和生产P2的机器台数，则X2，Y2，X3，Y3以此类推。可知： X1+Y1=1000 X2+Y2=0.35*X1+0.65*Y1 X3+Y3=0.35*X2+0.65*Y2

而三年的总收入为：Z=4500*（X1+X2+X3）+3500*（Y1+Y2+Y3） （1）设在第二年后还剩N台机器，则第三年的收入为： Z(3,N) =4500*X3+3500*Y3 =4500*X3+3500*（N-X3） =1000*X3+3500N 显然我们知道：0<=X3<=N，则Z3最大时，X3=N（Y3=0），此时，

Zmax(3，N)=4500*N。

（2）设在第一年后还剩N台机器，则第二年后（最后两年）的收入为： Z（2，N）=4500*X2+3500*（N-X2）+Zmax(3, 0.35*X2+0.65*(N-X2)) =1000*X2+3500*N+4500*（0.65*N-0.3*X2） =（3500+2925）*N-（1350-1000）*X2

第 22 页 共 31页

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

<=6425*N 显然，当X2=0，X3=0.65*N时，Z（2，N）取最大值。

（3）最后考虑整个三年的生产，设开始时有N台机器，则三年的收入总和为： Z（1，N）=4500*X1+3500（N-X1）+Zmax(2， 0.35*X1+0.65*(N-X1)) =1000*X1+3500*N+6425*（0.65*N-0.3*X1） =（3500+6425*0.65）*N-（0.3*6425-1000）*X1 <=（3500+6425*0.65）*N 综上所述，当X1=0，X2=0，X3=0.65*0.65*N时，收入取得最大值。即： 生产P1的机器台数 生产P2的机器台数 第1年 0 1000 第2年 0 650 第3年 422 0

此时三年收入最大。 5、动态规划：如下图是一个交通示意图，边上的数字表示路的长度。求每个点到V6的最短路径。

分析：先建立距离矩阵，D：0表示不通。 V1 V2 V3 V4 V5 V6 V1 0 3 5 0 0 0 V2 3 0 4 6 5 0 V3 5 4 0 4 3 0 V4 0 6 4 0 0 4 V5 0 5 3 0 0 5 V6 0 0 0 4 5 0 D（I，J）表示I点到J点的距离。 设L（I）为第I个点到V6的最短路径，则有：L（I）=min{(D(I,J)+L(J))} ，（I<>J）J为与I相通的所有的点。 如： L(6)=0 L(5)=min{(d(5,2)+L(2),(d(5,3)+L(3)),(d(5,6)+L(6))} =min{5+L(2), 3+L(3), 5+L(6)} L(4)=?? ?? 反复运算，直到L(1)--L(6)的值都不再改变为止。程序如下 uses crt;

const d:array[1..6,1..6] of integer=((0,3,5,0,0,0), {距离矩阵} (3,0,4,6,5,0), (5,4,0,4,3,0), (0,6,4,0,0,4), (0,5,3,0,0,5), (0,0,0,4,5,0)); var l:array[1..6] of integer; {存放最短距离} i,j,m:integer;

gb:boolean; {用来判断最短距离是否改变} begin

clrscr;

for i:=1 to 5 do l[i]:=10000; {先假设每个点到V6的最短距离很小}

第 23 页 共 31页

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

l[6]:=0; {V6到V6的最短距离为0} repeat

gb:=false;

for i:=1 to 5 do begin {计算L（1）??L（5）} m:=1000;

for j:=1 to 6 do begin {通过与第I个点相通的所有点中计算L（I）} if d[i,j]>0 then begin

if d[i,j]+l[j]

if m

until not gb; {直到L（I）不再改变} for i:=1 to 6 do write(l[i]:4); end. 6、动态规划：某印刷厂有六项加工任务，对印刷车间和装订车间所需时间见下表（时间单位：天） 任务 J1 J2 J3 J4 J5 J6 印刷车间 3 12 5 2 9 11 装订车间 8 10 9 6 3 1 问应该如何安排加工顺序使加工时间最少。 7、动态规划：若有四项任务：J1，J2，J3，J4，要先后使用机器M1，M2，使用机器的时间见下表： 任务 J1 J2 J3 J4 机器M1 3 4 8 10 机器M2 5 2 9 15 问怎样安排才能使所花时间最短。 8、动态规划：求下面图中任一点到V10点的最短路径。

9、动态规划：N枚硬币C1，C2，C3??，CN（N由键盘输入）中有一块不合格，不合格的硬币较正常为重。现用一天平找出不合格的一块，要求在最坏的情况下，用的天平次数最少。 10、动态规划：预测某产品连续四个月的市场需求量依次为220，240，200，190件，相邻的前后两个月生产能力的改变要付出代价，其数值等于改变量平方的两倍。每月多生产的部分，每件产品要付出12单位的代价

第 24 页 共 31页

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

把它们作废处理。若当月生产能力为200件，应如何合理地安排下面四个月的生产使效益最好。 11、动态规划：7万元投资到A、B、C三个项目上，其利润见下表： 投资额（万元） 1 2 3 4 5 6 7 A 0.11 0.13 0.15 0.24 0.24 0.30 0.35 B 0.12 0.16 0.21 0.25 0.25 0.29 0.34 C 0.08 0.12 0.20 0.26 0.26 0.30 0.35 问应如何分配投资额，使获得的利润最大。

十一、贪婪法

1、贪婪法：背包问题：假定有N个物体和一个背包，物体重量为Wi，价值Pi，而背包的载重能力为M。若将物体i的Xi部分（1<=i<=n,0<=Xi<=1）装入背包中，则有价值Pi*Xi，应怎样选择各种物体，使背包里所放的物体的总价值最高。 分析：这个问题如果只是把价值最高的物体优先放入包中的话，这显然是不对的，因为他没有考虑到物体的重量，所以我们应该把物体的单位价值计算出来，排序后按由大到小的顺序取物体，直到背包装满为止。这就是贪婪法，也就是得到最贪心的解。 2、贪婪法：如下图所示，一个正方形的四角分别放若干棋子，每一次可以从任一角去掉X枚棋子，同时在其余每一个角上添加X枚棋子。初始状态时角A上有一枚棋子，其余三角没有棋子。编程寻找一种方案，用最少的步数实现四个角从初始状态到目标状态的转换。目标状态从键盘输入（按A、B、C、D的顺序读入四个数字）。 A B D C 分析：我们将A、B、C、D四个角分别标号，用A1、A2、A3、A4分别表示初始状态，即初始状态为（A1、A2、A3、A4）；而用（D1、D2、D3、D4）来表示目标状态。 现在我们来看：如果把A1减少一枚棋子的话，其余三角就各增加一枚，各角增量可表示为E1=（-1，1，1，1）；同样的，其余各角的增量可分别表示为：E2=（1，-1，1，1）、E3=（1，1，-1，1）、E4=（1，1，1，-1）。 也就是说，从某个位置i取走X个棋子的增量变化为：X*Ei。并由此可得初始状态与目标状态的关系式：(A1，A2，A3，A4)+X1*E1+X2*E2+X3*E3+X4*E4 =(D1,D2,D3,D4) 即为以下四元一次方程： -X1+X2+X3+X4=D1-1 X1-X2+X3+X4=D2 X1+X2-X3+X4=D3 X1+X2+X3-X4=D4

解此方程，可得解： X1=(-D1+D2+D3+D4+1)/4 X2=(D1-D2+D3+D4-1)/4 X3=(D1+D2-D3+D4-1)/4 X4=(D1+D2+D3-D4-1)/4

若X1、X2、X3、X4全为正整数，则说明初始状态经过X1*E1，X2*E2，X3*E3，X4*E4的变化就可以达到目标状态。如果没有整数解呢？

但有一点要注意的就是：当前的第i角的棋子数量Ai必须大于等于Xi时，才能进行第i角上移走Xi个棋子的操作。否则，就必须分几次操作。

为了使移棋子次数尽量少，我们应该尽量在棋子数量足够多的角上移走棋子，然后就不必在该角上移走棋子了（可用一数组存放每个角还要移走多少枚棋子）；而如果没有一个角的棋子足够多，我们就应该移棋子数最多的那个角，把该角的棋子全部移走，并且在存放各角还要移走棋子数量的数组中减去该角已经移走的棋子的数量。如此重复下去，直到数组中各数值为0，即目标状态实现时为止。

此题的贪婪所在就在于每次移走尽可能多的棋子。

第 25 页 共 31页

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

每个节点的这种数据就是通过估价函数来计算得到的。估价函数就是自己定义的，用来计算某个节点相对于目标节点来说的数值化概念。一般的，我们定义一个节点如果估价函数的值越大就说明这个节点越接近目标节点，也就具有最优先的被展开权。实际上，我们已经接触过这样的概念——在等代价搜索法中，我们不是每次展开所有未展开节点，而是展开那个代价最小（大）的节点，这里的代价就是估价函数的简化形式之一。 那么，估价函数到底应该个什么函数呢？我们知道，一个函数最重要的是自变量有哪些。同样，对于宽度优先搜索来说，那些节点到底有哪些因素表示与目标节点的接近呢？毫无疑问，层是一个重要因素，如果两个节点与目标节点的距离相同，但层数不同，则层数少的节点是占优的，这就如：在第3层和第6层都能一步到达目标点了，你会选哪个点呢？ 另外，一个节点与目标节点相比，怎样才是接近呢？这是一个具体的问题，应该根据具体题目来确定这一点。 假定估价函数为g(x)，层函数为c(x)，与目标节点距离函数为m(x)，我们可以得到这样一个等式：g(x)=c(x)+K*m(x) （K为某一常数）。当然，估价函数也可考虑为：层数与所花代价为自变量。 下面我们以具体题目进行分析： 1、有一个NXN的迷宫，每一格或者是空，或者是实，如果有一人位于迷宫（x,y）格中，则他仅能到达相邻的空格（即上、下、左、右）。

现有一人从（1，1）出发，目标是（N，N），他随身带有K（o<=K<=N）个炸弹，一个炸弹的威力能把与他相邻的一个实格炸成空格。

编一程序，求出R个被炸的实格点（格）位置（0<=R<=K）和此人从起始点到目标点的路径，并要求R是满足条件中的最小值。 输入格式： （1）键盘输入N，K； （2）键盘输入如下NXN的迷宫，如下图（N=5时，1表示实点，0表示空点）： 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 0 1 1 1 0 0 1 0 左上角座标为（1，1），右下角为（N，N），因此，（1，1）必须为空点。

输出格式（用“-”号表示路径，用“*”号表示被炸的点），如下是一种路径： - - - - 1 0 1 1 - 0 0 1 - - 1 0 1 - 1 1 1 0 - * 0 分析：该题初看似乎无从下手，其实可这样考虑： （1）从任一位置走到另一位置，如果走向空位，可认为所花代价为1；如果走向实位，则要花掉一个炸弹，可认为所花代价为1*100。这样，估价函数就是：g(x)=从起点起已用炸弹数*100+从起点起已走空位数。每次从未展开的节点中找到代价最小的节点再展开即可，当找到目标节点时，搜索结束。 （2）这个过程可简单描述如下：从（1，1）开始，可往下、右展开两个节点，此两个节点代价相等，任取一个展开，又可得到两个新节点（注意不要走回头路），加上原来一个未展开的节点共3个，找到其中代价最小的继续展开，??，这样，当目标节点（N，N）出现时，结束搜索，并打印答案。 （3）由上可知，每个节点不仅要存放自己的座标，还要存放其父节点的位置，以及代价。 2、讨论以下积木游戏：B B B W W W E 。表示黑子（B）三个，白子（W）三个，空格一个（E），走法如下： （1）一个棋子移入相邻的空格代价是1； （2）一个棋子最多跳过两个其他棋子进入空格，其代价等于跳过棋子的数目。 目标上所有白棋移到黑棋左边，并且代价最小。 分析：毫无疑问，估价函数应该与代价及当前状态与目标状态距离有关。而当前状态与目标状态距离可认为是：所有B的右边的W总数和。例如状态：BWWBWEB，三个B的右边的W分别有3、1、0个，和为4。 这样，我们把估价函数定义为g(x)=已花代价+当前状态与目标状态距离，g(x)越小则应该越先展开。 3、请利用A*算法解决8数码问题。

第 31 页 共 31页

本文来源：https://www.bwwdw.com/article/359.html