程序设计算法与分析

程序设计算法分析信息学奥林匹克竞赛联赛知识辅导

上册

肖兆青

前言

上世纪人类科学技术的最伟大成果非计算机莫属。自从二十世纪中叶，第一台计算机问世以来，立即引起了当代科学、技术、生产、生活和教育事业等各方面的革命。半个多世纪以来，计算机技术得到了迅猛的发展，其势可谓日新月异，她应用的领域也越见广阔，几乎没有计算机不能涉及的方面。面对这一场巨大的技术革命，计算机知识的教育已成了从小学、中学到大学的一门必不可少的课程。邓小平同志早就指示，计算机教育要从娃娃抓起，所以作为基础教育的中学，如何在普及计算机知识和技能的教学活动中，探索出一条在现代教育理论的指导下提高现代信息科技知识教学质量之路，是很值得我们研究的。

为了普及计算机知识，丰富学生课余生活，培养学生的创新思维能力，特别是对学有专长的资优学生进行个性化培养，我国每年都举办一次全国青少年信息学奥林匹克竞赛分区联赛，为全国青少年信息学奥林匹克竞赛、国际青少年信息学奥林匹克竞赛中国队组队赛、国际青少年信息学奥林匹克竞赛选拔人才。

从内容上看，这些颇具影响力和权威性的竞赛都是以程序设计为主的。有人问，计算机技术是多方面的，为什么不选基础教育课程内的文字处理、多媒体应用和网络知识，而偏偏选中程序设计呢？这是因为：

1.程序设计与软件工具的使用不同，它要求编程者以某种高级语言为媒

介，通过构造算法去解决由现实生活中抽象出来的各种问题，这些问题非一般软件工具所能解决。如果说计算机应用是“人脑延伸”的话，程序设计即为这种延伸的最高形式；

2.程序设计对人的能力要求是多方面的。编程者不仅要熟悉计算机语言

功能，而且还必须具备：

（1）扎实的数学基础和算法知识，能够对客观存在的事物及其所要解决的问题具有正确的认识和深刻的理解，包括弄清问题的需求，弄清事物的属性、行为及其彼此之间的关系；

（2）娴熟的编程技术，能够把对问题及其方法的认识描述出来，最终产生一个计算机能够理解和执行的计算机程序代码，并通过上机运行让计算机系统实现编程者解决问题的描述；

（3）较高的实践能力和创造能力，能够独立思考、提出质疑、拓延思路、洞悉规律，创造性地运用知识于不同的问题情景；

正因为程序设计能比较客观地反映人的综合素质，因此国际、国内的信息学奥林匹克竞赛都将其作为考核内容。过去是这样，现在是这样，将来恐怕亦不会随计算机技术的发展而发生改变。计算机程序设计技术将会愈来愈成为现代学生投身信息化环境，从根本上掌握现代信息技术，将来

1

能自由驾驭信息化时代的重要基础。计算机程序设计人才的培养，其意义不仅在收获人才，更重要的是凸现了青少年人才的培养规律，为各个领域的人才辈出提供了重要的启示。

由于程序设计的算法知识具有一定的难度要求，所以对于一些学有余力的资优学生将更具有挑战性，学习程序设计的算法知识是培养资优学生的自主学习能力和创造性思维能力的绝好平台。由于算法知识的益智性和数学味对培养资优学生的推理归纳能力、发散思维能力、构造创新能力具有事半功倍的效果，事实证明，凡是在程序设计的算法知识学习中能够自由翱翔的资优学生，他在学习其它相关领域的知识时也会感到非常的得心应手。

在对学生进行程序设计知识训练的过程中有一条非常重要，就是我们特别要注意培养学生通过自学取得独立获取知识和运用知识的能力。比如数据结构和算法的知识对学生们进一步提高程序设计能力非常关键，但由于知识的难度高、内容多，学生的水平差距可能会拉开很大，而我们的课时有可能很有限，靠教师教根本教不过来。所以我感到教师的作用更多的应该是放在精选知识点和例题上，给学生铺出一条仅用一块块不连续的大石块点缀的通路来，而这条道路的夯实和拓宽很多必须通过学生自学来解决。特别是现在计算机的知识更新很快，新的方法、新的技术层出不穷，要适应日新月异的信息时代的要求，学生掌握独立获取知识和运用知识的能力才是今后人生中能胜任终身学习的任务所必不可少的。

要培养专长就必须打破课堂教学和现有知识结构的限制，因材施教，鼓励冒尖，为资优学生们减负松绑，提供最佳的学习环境。不能要求一刀切，必要的时候要针对个别特殊情况开小灶，为资优学生们在扎实基础上的特长发挥创造条件。课堂教学最大的弊端是讲求整齐划一，它在一定程度上抑制了学生特长的发挥。从计算机程序设计知识的学习看青少年人才培养规律，启示很多。但最重要的问题还是教育观念的改变。

本人在进行了数年的《资优学生培养模式研究》课题的实践中，写下了这本关于信息学奥林匹克竞赛分区联赛中需要用到的一些程序设计算法知识的讲义，现在整理出来，抛砖引玉，供同行们批评指导。

2

第一讲深度优先搜索

搜索是计算机程序设计竞赛中最常用的一种策略，对于那些一时难以找到规律或公式，或者根本没有规律或公式可循的问题，我们可以利用计算机高速运算的特点，用穷举策略来进行搜索。所谓穷举策略，原则地说，就是第一步只考虑问题的部分条件，根据这些条件，找到所有的满足这些部分条件的解，称之谓可行解；然后用尚未考虑的条件去一一检验那些可行解，筛去不符合条件的解，留下符合条件的解，那就是整个问题的解。

搜索可分为深度优先搜索和广度优先搜索。在深度优先搜索中，深度越大的结点越先得到扩展；而广度优先搜索则是深度越小的结点越先得到扩展。深度优先搜索的数据结构是堆栈；而广度优先搜索的数据结构是队列。下面我们首先学习深度优先搜索。

可以用深度优先搜索来处理的问题是各种各样的。如果搜索的深度已知或固定，则可用枚举法来进行；如果搜索的深度很深或不固定，则可用递归法和回溯法来进行。

第一节枚举法

枚举法是一种我们十分熟悉的方法，它是用单重循环或多重循环嵌套的方法来穷举出所有可能出现的情况，然后对每种情况进行判断，找出满足条件的解来。由于用循环语句来进行穷举就必须预先知道循环变量的个数，这样才能设计循环嵌套的层数，所以它只能用于那些搜索的深度已知或固定的情况。当然，在解决一个具体的问题时，为了节省计算机的时间和空间资源，还要求我们尽可能地减少循环的层数和判断的次数，使程序的算法更加优化。

例1-1-1 值班安排问题

问题描述：

有A、B、C、D、E五个人，安排值周一、周二、周三、周四、周五的班，每人值一天，共有多少种不同的安排，编程打印输出各种安排。

算法分析：

由于是要求五个人安排在五天中值班，每个人都可以安排在周一到周五的任意一天中值班，只能也必须安排一次，所以本题是求排列枚举的问题，只要列出这五个人在五天中的全排列情况即求得了本题的解。

如果用五重循环来对这五个人在五天中进行安排，当然可以解得本题的解，但能不能再对算法进行一下优化呢？回答是肯定的。因为在外循环中的人排定了某个值班时间后，处于内循环的人就不能重复再排在这个时间了，因为一天只能排一个人值班。这样我们只要加入一些判断条件就可

3

以使越到内层循环次数越少，而第五个人的安排更是不必循环了，因为这时只剩下唯一的一个时间而不容挑选了。剩下的问题是如何用数学方法来适当表述第五个人的安排时间，我们可以巧妙地利用周一到周五这五天时间的有序性，以1、2、3、4、5这五个数值分别代表这五天，则第五个人的安排时间就等于15减去前四个人的安排时间值之和，因为15是这五天时间值总和。

参考程序：

PROGRAM ex1_1_1(input,output);

VAR

a,b,c,d,e : byte;

n : word;

BEGIN

n := 0;

for a := 1 to 5 do

for b := 1 to 5 do

if a <> b then {排除a、b两人同一天值班的情况}

for c := 1 to 5 do

if (a <> c) and (b <> c) then

for d := 1 to 5 do

if (a <> d) and (b <> d) and (c <> d) then

begin

e := 15-a-b-c-d;

{此处优化可省去一重循环，因为五天序数和为15} n := n+1;

writeln('No.',n:2,' :',' A : ',a,' B : ',b,

' C : ',c,' D : ',d,' E : ',e);

if n mod 24 = 0 then readln

end

END.

例1-1-2 取彩球问题

问题描述：

在 红、黄、蓝、黑、白 五种颜色的五个彩球中，取出三个彩球的各种取法共有多少种，编程打印输出各种取法。（求组合枚举）

算法分析：

此题与值班安排问题的区别是这五种颜色的彩球不要求区分取出的顺序，对于取出红、黄、蓝三个球和取出黄、蓝、红三个球认为是同一种取

4

法，所以本题是求组合枚举的问题。

组合枚举与排列枚举的主要区别是每重循环的循环变量不需要在全部五种颜色中进行取球，因为至少要考虑两种情况下不必重复取球：一是外层循环变量已取过的颜色不必再取，二是要让出若干个位置让内层循环的变量取球。

参考程序：

PROGRAM ex1_1_2(input,output);

CONST

s:array[1..5]of string=('Red','Yellow','Blue','Black','White'); VAR

i,j,k,n : byte;

BEGIN

n := 0;

for i := 1 to 3 do

{设第1个位置只考虑放前三种颜色的球，因为须留出后两位置的颜色} for j := i+1 to 4 do {循环终值为4是为了留出最后1个球的颜色} for k := j+1 to 5 do begin {k和j的初值要排除已取过的颜色} n := n+1; {n是不同取法的种类数计数变量}

writeln('No.',n:2,' : ',s[i]:8,s[j]:8,s[k]:8)

end;

readln

END.

例1-1-3 填数问题

问题描述：

在如图所示的圆圈中，不重复地填入数字1、2、3、4、5、6。要求每条边上三个数之和都相同，编程打印输出各种填法。

算法分析：

此题是通过排列枚举加筛选条件来进行求解。我们可将1到6这六个数在a、b、c、d、e、f这六个位置进行排列枚举，再通过筛选条件：a+b+c、c+d+e、e+f+a三者是否相等（考虑a、c、e为三角形的三个顶点位置）来找出符合条件的所有解。

5

参考程序：

PROGRAM ex1_1_3(input,output);

VAR

s,n,a,b,c,d,e,f : integer;

BEGIN

n := 0;

for a := 1 to 6 do

for b := 1 to 6 do

if b <> a then

for c := 1 to 6 do

if (c <> a) and (c <> b) then

for d := 1 to 6 do

if (d <> a) and (d <> b) and (d <> c) then

for e := 1 to 6 do

if (e <> a) and (e <> b) and (e <> c) and

(e <> d) then

begin

f := 21-a-b-c-d-e; {因为六数之和为 21}

s := a+b+c; {考虑a、c、e为顶点排列} if (c+d+e = s) and (a+f+e = s) then begin n := n+1; {统计解的个数}

writeln('No.',n:2,' : ',a:4);

writeln(b:10,f:4);

writeln(c:8,d:4,e:4); {呈三角形输出}

readln

end

end

END.

例1-1-4 构造三角形问题

问题描述：

有长度为3、4、5、6、7、8、9的小木棍各一根，从中选取三根作为三角形的边长，问能构成多少种不同类型的三角形，编程打印输出各种不同类型的三角形。

算法分析：

此题可通过组合枚举加筛选条件来进行求解。我们可设i、j、k为三角形的3个边，并让其在3到9这7种规格的小木棍间以满足组合枚举规

6

律的方式进行循环取值。对取出的每一组组合值再用筛选条件——三角形的任意两边和应大于第三边来进行筛选，求出所有满足条件的解。

参考程序：

PROGRAM ex1_1_4(input,output);

VAR

i,j,k,n : byte;

BEGIN

n := 0; {n用于统计解的个数}

for i := 3 to 7 do {留出8、9让后两边取值}

for j := i+1 to 8 do {留出9让最后一条边取值}

for k := j+1 to 9 do {k和j的初值要排除已取过的边值} if (i+j > k) and (i+k > j) and (j+k > i) then begin

n := n+1; {筛选条件：三角形的任意两边和应大于第三边} writeln('No.',n:2,' :',i:5,j:5,k:5);

if n mod 24 = 0 then readln

end;

readln

END.

例1-1-5 地图涂色问题

问题描述：

下面的地图共有12个区域，用四种不同的颜色去着色，要求相邻区域的颜色不可相同，编程打印输出各种不同的着色方案。

算法分析：

此题虽然看上去很复杂，但实际上仍然是12个区域用4种颜色的排列枚举再加筛选条件就可解决的问题，而筛选条件就是相邻区域的颜色不能相同。我们可以考虑用12 重循环代表12 个区域，让其在4种颜色间进行循环，外循环从最中间的1开始，以后的各层循环只需考虑外循环部分的取值和当前的循环如区域相邻则取值不能相同即可。

7

另外，为了用循环语句输出12 个区域的颜色值，应考虑用下标变量来做12 层循环的循环变量，这样输出时只要将颜色数组的值输出就可以了。

参考程序：

PROGRAM ex1_1_5(input,output);

VAR

a : array[1..12] of byte;

n,i : byte;

BEGIN

n := 0;

for a[1] := 1 to 4 do

for a[2] := 1 to 4 do

if a[2] <> a[1] then {两个区域若相邻则不能同色，否则同色无妨} for a[3] := 1 to 4 do

if (a[3] <> a[2]) and (a[3] <> a[1]) then

for a[4] := 1 to 4 do

if (a[4] <> a[3]) and (a[4] <> a[1]) then

for a[5] := 1 to 4 do

if (a[5] <> a[4]) and (a[5] <> a[1]) then

for a[6] := 1 to 4 do

if (a[6] <> a[5]) and (a[6] <> a[1]) and

(a[6] <> a[2]) then

for a[7] := 1 to 4 do

if (a[7] <> a[6]) and (a[7] <> a[2]) then

for a[8] := 1 to 4 do

if (a[8] <> a[7]) and (a[8] <> a[2]) and

(a[8] <> a[3]) then

for a[9] := 1 to 4 do

if (a[9] <> a[8]) and (a[9] <> a[3]) and

(a[9] <> a[4]) then

for a[10] := 1 to 4 do

if (a[10] <> a[9]) and (a[10] <> a[4]) and

(a[10] <> a[5]) then

for a[11] := 1 to 4 do

if (a[11] <> a[10]) and (a[11] <> a[5]) and

(a[11] <> a[6]) and (a[11] <> a[7]) then for a[12] := 1 to 4 do

8

if (a[12] <> a[7]) and (a[12] <> a[8]) and

(a[12] <>a[9]) and (a[12] <> a[10]) and

(a[12] <> a[11]) then begin

n := n+1;

write('No.',n,' : ');

for i := 1 to 12 do

write('(',i,':',a[i],')');

writeln;

if n mod 24 = 0 then readln

end

END.

9

第二节递归法

对于搜索的深度很深或深度不固定的情况，则无法用枚举的方法来设置循环嵌套的层数，这时可以考虑用递归法来完成搜索任务。递归是一种常用算法，它是搜索的另一种实现方式。如果在算法设计中采用一个函数或过程直接或间接地调用它自身来解决问题的方法，则称该方法为递归算法。递归算法必须要设计好一个或若干个确定的递归终止条件。

下面我们先从4个求排列和组合的例子来分析递归算法的解题过程和解题方法，掌握递归算法的解题思路和原理，熟悉用递归算法求解问题的一般规律。

例1-2-1 有重复值的全排列问题

问题描述：

由键盘输入一个正整数n，在1到n之间作n重嵌套的循环穷举并打印输出，即输出1到n中有重复值的n个数字的全排列。

例如当n=2时的输出应为：

1、1；1、2；

2、1；2、2 共4种。

算法分析：

我们可以用一个数组 a : array[1..n] of byte；来存放每轮等待输出的n个值，剩下的问题就是如何将每轮的值准确无误地赋给a数组，并在打印输出过一轮的值之后又能准确地变换为下一轮的一组值。

我们可以从1开始将递归层数参量带入递归过程，而在递归子程序中可设计一重1到n的i循环来控制同一深度的a数组值的变化，并在该循环中即将递归深入一层。下面我们来分析一下程序的执行过程： 由于递归是按深度进行的，所以对应一个相同的i，首先是进行逐层递归，而各递归层的a数组元素是赋的相同的i值。直至达到递归终止条件（深度s > n）时为止，打印输出第一轮a数组的值（全是1）。终止递归后返回上一层（n层），循环变量i的值加1后再递归，又会满足递归终止条件而打印输出第二轮a数组的值……直至将1到n的变化完成（这时打印输出了n轮a数组的值，每组值只是a[n]的值不同，其他都是1）。再递归终止返回时由于n层的i循环已经结束，所以再继续返回至n-1层。将n-1层的i值加1后再递归，……以此类推，直至第一层的i循环完成1到n的变化后，并各层的a数组元素值都为n时，打印输出最后一轮全为n值的a数组值。输出完成后的返回将是连续返回n层，回到主程序结束程序的运行。

参考程序：

PROGRAM ex1_2_1(input,output);

10

11 VAR

a : array[1..9] of byte;

n : byte;

PROCEDURE sub(s : byte);

var

i,j : byte; begin if s > n then begin

for j := 1 to n do write(a[j]:2); writeln

end

else for i := 1 to n do

begin

a[s] := i; {递归前a 数组s 元素赋值i，

sub(s+1) 且递归一次，赋值一次}

end

end;

BEGIN

repeat {输入n 的值，范围控制在1到9之间} write('N = '); readln(n)

until n in [1..9];

sub(1); readln {递归初始值从1开始}

END.

从以上程序我们可以看到，递归程序的特点是它既有递进过程，又有回归过程，而且在任何一个深度时，它的所有变量和参数的值由于采用的是传值方式，所以都在各层保存着，这是因为Pascal 系统在递归递进的过程中会将同一变量或参数在不同深度的值，都依次压入系统的堆栈。由于堆栈结构先进后出的特点，所以深度浅的数据先进栈，深度深的数据后进栈；在递归的回归过程中，由于堆栈结构后进先出的特点，深度深的数据先出栈，深度浅的数据后出栈。这就给我们在递归过程中能对数据进行有条不紊的处理提供了可靠的保证。

Pascal 系统为我们提供了一种监视窗口的功能，我们可通过跟踪并观察变量和参数a 、s 、i 变化的方法来弄清楚以上程序的机理及来龙去脉。

例1-2-2 无重复值的全排列问题

问题描述： {s > n 是递归终止条件：表示s > n 时终止递归，打印a 数组内容，打印后并未结束，而是退回递归前的i 循环的下一个i 值……继续递归、打印}

由键盘输入一个正整数n，在1到n之间进行n重嵌套的，每重1到n的排列穷举，且每个数组元素所赋的值，必须是各不相同的，即求出无重复值的全排列。

例如n=2时的输出为：

1、2；

2、1 共2种。

算法分析：

此题与上一题的区别是每轮的输出数组元素中不能有相同的值。为了排除相同值的出现，我们可以设置一个标志数组 b : array[1..9] of boolean；其值为true时可用，为false时不可用。

初始时，先对b数组全置true；进入递归过程后，首先判断b[i]的值是否为true，若为true才能给a数组元素赋i值，否则继续判下一个b[i]的情况；在对a数组的某个元素赋了一个i值后，立即将其对应的b[i]值置false,以保证在以后的递进过程中不赋重复的i值，……直至满足递归终止条件后打印输出满足题意的一组解；另外要注意，在退出递归的回归过程中，每退出一层都要立即将该层原来设置的用过的b[i]标志恢复为true,以便于在再一次递归进入时可将i用于下一组输出的a数组元素的赋值之中。

参考程序：

PROGRAM ex1_2_2(input,output);

VAR {设置一个标志数组b，true为可用，用过置为false}

a : array[1..9] of byte;

b : array[1..9] of boolean;

n : byte;

PROCEDURE sub(s : byte);

var

i,j : byte;

begin {实质上在递归过程中i是外循环，s是内循环，通过j输出} if s > n

then begin

for j := 1 to n do write(a[j]:2); writeln

end

else for i := 1 to n do

if b[i] then {条件成立表示i可用，否则判下一个i值} begin

a[s] := i;

b[i] := false; {对赋过的i其b[i]标志置false}

sub(s+1); {每层赋了一个值后即递归进入下一层}

12

b[i] := true {退出后标志恢复，进入返回层i循环} end

end;

BEGIN

fillchar(b,sizeof(b),true);

{标准过程：表示将b数组范围的所有数组元素赋初值true，表示可用} repeat write('N = '); readln(n) until n in [1..9];

sub(1); readln

END.

例1-2-3 无重复值的部分元素排列问题

问题描述：

打印输出从n个元素中选取m个元素的各种排列（1≤n、m≤9）。即求出从n个元素中选取m个元素的无重复值的部分元素排列。

例如当n=3、m=2时，其输出应为：

1、2； 1、3；

2、1； 2、3；

3、1； 3、2 共6种。

算法分析：

此题与上一题的区别仅仅是从n个元素中取值的个数不同，上一题是全取n个，而本题是只取其中的m个，所以我们只要将上一题的递归终止条件s > n改为s > m即可，当然j循环的打印输出终值也要相应改为m。另外在主程序的输入部分要增加判断m不能超出n的范围的语句，以保证输入的n和m的值能够正确运行。

参考程序：

PROGRAM ex1_2_3(input,output);

VAR

a : array[1..9] of byte;

b : array[1..9] of boolean;

n,m : byte;

PROCEDURE sub(s : byte);

var

i,j : byte;

begin

if s > m {与上题的区别仅在将两处的n改为m ，

then begin 这样外循环终值为n ,内循环终值为m }

for j := 1 to m do write(a[j]:2);

writeln

end

13

else for i := 1 to n do {取值范围仍然是1到n}

if b[i] then

begin

a[s] := i;

b[i] := false; sub(s+1); b[i] := true

end

end;

BEGIN

fillchar(b,sizeof(b),true);

repeat {输入部分要判断m不能超出n的范围}

write('N = '); readln(n);

write('M = '); readln(m)

until (n in [1..9]) and (m <= n);

sub(1); readln

END.

例1-2-4 部分元素的组合问题

问题描述：

打印输出从n个元素中选取m个元素的各种组合（1≤n、m≤9）。 例如当n=3、m=2时，输出结果应为：

1、2； 1、3；

2、3 共3种。

算法分析：

此题与上一题的区别是只要求出不同的组合即可，与各数字的排列顺序无关，即相同元素的不同顺序排列认为是相同的。

为了保证输出的每一组的m个元素各不相同，就要求递归时不同深度的a数组取值必须各不相同，我们可以让递归每进入一层，递归过程的参量就增加1来达到此目的，这就是每次递归都是以sub（s+1）进入的原因。但是本题的组合求解还有一个要求，就是相同元素的不同顺序排列不能出现，这就要求每一递归层的i初始值也要比前一层的i初始值递进，这样才能保证前面输出过的元素不再重复输出。这里我们可以把i的初始值设置为a[s-1]+1，即在上一层的a数组元素值上再加1，当然上题使用的标志数组b这里也不需要了。

参考程序：

PROGRAM ex1_2_4(input,output);

VAR

a : array[0..9] of byte; {求组合不需标志数组}

n,m : byte;

14

PROCEDURE sub(s : byte);

var

i,j : byte;

begin

if s > m

then begin

for j := 1 to m do write(a[j]:2); writeln

end

else for i := a[s-1]+1 to n do

{请与题ex1_2_1、题ex1_2_3比较，可以看到循环变量i在不同深度的初始值是不同的，它保证了i 的递进，使得每一行输出的数字各不相同} begin a[s] := i; sub(s+1) end

end;

BEGIN

repeat

write('N = '); readln(n);

write('M = '); readln(m)

until (n in [1..9]) and (m <= n);

sub(1); readln

END.

上面我们通过几个求排列和组合问题的简单例子讨论了用递归算法求解问题的基本规律，下面我们再举几个实际搜索应用的例子，来进一步巩固递归算法的知识。

例1-2-5 皇后问题

问题描述：

在n×n的国际象棋的棋盘上，放n个皇后，要做到各皇后相互之间不能攻击，问共有多少种不同的放置方法，要求打印输出各种放置方法。（2≤n≤9，“相互之间不能攻击”表示放置时每行每列每一条对角线都不能超过一个皇后）

算法分析：

本题可以用递归进行全排列搜索，再用筛选条件挑选出满足题意的解来。为了使程序结构清晰易读，我们设置了print过程用于输出满足条件的每一组解；设置了check函数用于判断在某个位置能否放置新的皇后。

本题的题意是所有的皇后都不能同行、同列或同斜线，由于我们将递归的深度参量s与行编号同值，所以放置的皇后就不可能同行，这样就不

15

须判断皇后是否同行，只要判是否同列和同斜线就行了。

另外，我们将数组a的下标值定为行编号的值，而数组各元素的值定为列编号的值，这样就可以用一个数组的存储容量同时解决了行和列的存储问题，节约了存储空间。

参考程序：

PROGRAM ex1_2_5(input,output);

VAR

a : array[1..9] of 1..9;

n,t : word;

PROCEDURE print;

var

j : byte;

begin

t := t+1; write('No.',t,' : '); {统计不同放置方法数}

for j := 1 to n do write('(',j,',',a[j],') ');

writeln; {输出皇后的放置位置，j表示行，a[j]表示列}

if t mod 24 = 0 then readln {换屏暂停}

end;

FUNCTION check(s,i : byte) : boolean;

var {本函数用于判断s行i列位置能否放新的皇后，能放为true} j : byte;

begin

check := false; {行循环变量j只要在当前行s前面的各行 for j := 1 to s-1 do 进行循环比较即可，因s行后还未放皇后} if (i = a[j]) or (abs(s-j) = abs(i-a[j])) then exit;

check := true {条件1:同列；条件2:同斜线(行差与列差绝对 end; 值相等表示了以位置s,i为交点的两条斜线)} PROCEDURE sub(s : byte);

var

i : byte;

begin

if s > n {递归终止条件。满足一次打印一组解}

then print {输出用子程序处理}

else for i := 1 to n do {在s行的各列查找能放皇后的位置} if check(s,i) then

begin {check子程序用于判断s,i 位置能否放皇后} a[s] := i; { a[s]记录新皇后的列位置，s是行位置}

16

sub(s+1) {递归搜索下一行}

end

end;

BEGIN

repeat

write('N = '); readln(n) {n的取值范围限定在2到9之间} until n in [2..9];

t := 0; {放置方法计数器置初值}

sub(1); {递归搜索从第1行开始}

readln

END.

例1-2-6 字母组合问题

问题描述：

由键盘输入正整数M、N、C，输出从第M个小写英文字母开始，顺序地取N个小写英文字符，在N个小写英文字母中，取C个字母的所有组合。算法分析：

这是一个典型的组合求解题，与题ex1_2_4相比仅仅是增加了英文字母的ASCII值和数值之间的转换问题。当然我们也可以用字母的有序值设置循环变量的值，这样虽然可以省去了英文字母的ASCII值和数值之间的转换，但是递归程序中的数值计算方面却会变得复杂得多。权衡利弊，还是采用数值方法来控制递归过程，到输出时再进行一次ASCII值和数值之间的转换来达到解题的目的。

参考程序：

PROGRAM ex1_2_6(input,output);

VAR

a : array[1..26] of byte;

m,n,c : byte;

t : longint;

PROCEDURE print; {输出过程在找到解的基础上将其转换为之母输出} var

j : byte;

begin

t := t+1;

write('No.',t,' : (');

for j := 1 to c-1 do {此95再加上m和a[j]的起始 write(chr(95+m+a[j]),','); 值1正好97,为’a’的ASCII码}

17

writeln(chr(95+m+a[c]),')');

if t mod 24 = 0 then readln

end;

PROCEDURE sub(s : byte);

var

i : byte;

begin

if s > c {递归终止条件为取得了c个数}

then print

else for i := a[s-1]+1 to n do{取数从上一层的取值加1开始} begin

a[s] := i; sub(s+1) {取数后即递归进入下一层}

end

end;

BEGIN

t := 0;

repeat {输入限定条件是m+n不能超出字母范围，组合数在取数范围} write('Input M,N,C : '); readln(m,n,c)

until (m + n <= 27) and (c <= n);

sub(1); readln

END.

例1-2-7 填数问题

问题描述：

在如下图所示的19个圆圈中，不重复地填入数字1至19，要使每条直线上的几个数字之和都相等，请输出一种填写方法。

算法分析：

本题初看时可能会觉得一下子难以找出规律，但从数学角度分析一下

18

就可以看出每条直线的数字和应为38。因为我们可以先求出1到19的数字和为190，然后再找出无重复元素且包含所有19个数的5条直线（比如水平的5条直线），就可以知道每条直线的和是190/5 = 38 ，题中把它设为常量k。

接下来我们就可以采用递归求无重复值排列的算法来求解，在求解过程中再加入筛选条件（即是否满足每条直线上的数字和都为38）就可以求出解来。由于直线数有15条之多，所以要尽量避免重复判断，本题中在每一个位置试放数字解题的过程中，因为后面的位置还未放数字，所以只要判断与前面位置能构成完整直线的线上数字之和是否为38就行了。如满足条件就进入下一层递归，试解下一位置的值；如不满足条件则表示该位置的取值无效，重新取下一个值再试；如果该位置与前面的位置不能构成一条完整直线，则取数有效，进入下一层递归，试解下一位置的值。

为了保证取过的数字不再被重复取用，我们可以设置一个标志数组。只要该数组元素的下标值（代表1到19这19个数之一）已被取用，就将该数组元素的值置为false，以后位置再试解取数时必须先判断该数对应的标志数组元素是否为true，为true才能取用，否则就不能用。当然对试用无效的数别忘了恢复其数组标值后再选其它数，以免该数被漏用。

当逐个找出19位置的解以后，就可以输出结果了。我们设置了print 过程来完成输出任务。为了输出结果能比较形象地表示图示的19个位置，程序中用输出5行数据，且每个数据以一定的场宽值来控制其输出位置的方法来输出，结果形象又直观。

根据题意只要求输出一种填写方法，所以输出完毕即用halt命令强制程序结束，不然可以输出更多组解来。

参考程序：

PROGRAM ex1_2_7(input,output);

CONST

k = 38; {此值由19 个数的总和除以5行得到,为每直线的和值} VAR

a : array[1..19] of 1..19; {用于存放19个位置所置的数}

b : array[1..19] of boolean;{标志数组:1到19中取过值为false} PROCEDURE print; {按图示格式打印输出19 个数}

begin

writeln(a[1]:6,a[2]:4,a[3]:4);

writeln(a[4]:4,a[5]:4,a[6]:4,a[7]:4);

writeln(a[8]:2,a[9]:4,a[10]:4,a[11]:4,a[12]:4);

writeln(a[13]:4,a[14]:4,a[15]:4,a[16]:4);

writeln(a[17]:6,a[18]:4,a[19]:4);

19

readln; halt {根据题意只要输出一种结果即可退出} end;

PROCEDURE sub(s : byte);

var

i : byte;

begin

if s > 19

then print {满足条件表示找到了一组解，即执行print过程} else for i := 1 to 19 do {在1到19中循环试解}

if b[i] then {标志数组元素允许才能试解}

begin

a[s] := i; {i被置数后其标志数组值相应置false}

b[i] := false;

case s of {以下判断只需考虑小于s的位置情况} 3 : if a[1]+a[2]+a[3] = k then sub(s+1);

7 : if a[4]+a[5]+a[6]+a[7] = k then sub(s+1);

8 : if a[1]+a[4]+a[8] = k then sub(s+1);

12 : if (a[8]+a[9]+a[10]+a[11]+a[12] = k) and (a[3]+a[7]+a[12] = k) then sub(s+1);

13 : if a[2]+a[5]+a[9]+a[13] = k then sub(s+1);

16 : if (a[13]+a[14]+a[15]+a[16] = k) and

(a[2]+a[6]+a[11]+a[16] = k) then sub(s+1);

17 : if (a[8]+a[13]+a[17] = k) and (a[3]+a[6] +a[10]+a[14]+a[17] = k) then sub(s+1); 18 : if (a[4]+a[9]+a[14]+a[18] = k) and (a[7] +a[11]+a[15]+a[18] = k) then sub(s+1); 19 : if (a[17]+a[18]+a[19] = k) and

(a[1]+a[5]+a[10]+a[15]+a[19] = k) and

(a[12]+a[16]+a[19] = k) then sub(s+1); else sub(s+1) {s不是上述值则取值有效直接递归} end;

b[i] := true

end {s取值不满足条件则恢复标志位，试解下一值} end;

BEGIN

fillchar(b,sizeof(b),true); {标志数组置初值true}

sub(1)

20

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