中山纪念中学信息学奥林匹克算法设计题选
详细过程举例如下：
原序： [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页