信息学奥赛基础算法教案

基础算法教案目录

第一课算法简介..................................................1

第二课多精度数值处理............................................2

第三课排列与组合...............................................12

第四课枚举法...................................................18

第五课递归与回溯法.............................................51

第六课递推法...................................................84

第七课贪心法...................................................99

第八课分治法..................................................128

第九课模拟法..................................................140

习题...........................................................159

第一课算法简介

算法是一组（有限个）规则，它为某个特定问题提供了解决问题的运算

序列。在信息学竞赛中，就是计算机解题的过程。在这个过程中，无论是形

成解题思路还是编写算法，都是在实施某种算法。前者是推理实现的算法，

后者是操作实现的算法。

计算机解题的核心是算法设计。一个算法应该具有以下五个重要特征：

①有穷性：一个算法必须能在执行有限步之后结束；

②确切性：算法的每一步骤必须确切定义；

③输入：一个算法有零个或多个输入，以描述运算对象的初始情况。

所谓0个输入是指算法本身给出了初始条件；

④输出：一个算法有一个或多个输出，以反映对输入数据处理后的结

果。没有输出的算法是毫无意义的；

⑤可行性：算法原则上能够精确的运行，而且其运算规模是可以承受

的。

为了获得一个既有效又优美的算法，必须首先了解一些基本的常用算法

设计思路。下面，我们就对构成算法所依据的一些基本方法展开讨论，如递

推法，递归法，枚举法，分治法，模拟法，贪心法等。

第二课多精度数值处理

课题：多精度数值的处理

目标：

知识目标：多精度值的加、减、乘、除

能力目标：多精度值的处理，优化！

重点：多精度的加、减、乘

难点：进位与借位处理

板书示意：

1）输入两个正整数，求它们的和

2）输入两个正整数，求它们的差

3）输入两个正整数，求它们的积

4）输入两个正整数，求它们的商

授课过程：

所谓多精度值处理，就是在对给定的数据范围，用语言本身提供的数据

类型无法直接进行处理（主要指加减乘除运算），而需要采用特殊的处理办法

进行。看看下面的例子。

例1从键盘读入两个正整数，求它们的和。

分析：从键盘读入两个数到两个变量中，然后用赋值语句求它们的和，

输出。但是，我们知道，在pascal语言中任何数据类型都有一定的表示范围。

而当两个被加数据大时，上述算法显然不能求出精确解，因此我们需要寻求

另外一种方法。在读小学时，我们做加法都采用竖式方法，如图1。

这样，我们方便写出两个整数相加的算法。

856A,A?A）

+255+B3B2B।

1111C4c3c2cl

图1图2

如果我们用数组A、B分别存储加数和被加数，用数组C存储结果。则上

例有

A[1]=6,A[2]=5,A[3]=8,B[1]=5,B[2]=5,B[3]=2,C[4]=1,C[3]=1,

C[2]=1,C[1]=1,两数相加如图2所示。由上图可以看出：

C[i]:=A[i]+B[i];

ifC[i]>10thenbeginC[i]:=C[i]mod10;C[i+1]:=C[i+1]+1end;

因此，算法描述如下：

procedureadd（a,b;varc）;

｛a,b,c都为数组，a存储被加数，b存储加数，c存储结果）

vari,x:integer;

begin

i:=1

while（i<二a数组长度>0）or（i<=b数组的长度）dobegin

x:=a[i]+b[i]+xdiv10;｛第i位相加并加上次的进位）

c[i]:=xmod10;｛存储第i位的值）

i：=i+1｛位置指针变量）

end

end;

通常，读入的两个整数用可用字符串来存储，程序设计如下：

programexaml;

const

max=200;

var

a,b,c:array[1..max]of0..9;

n:string;

Iena,Ienb,Ienc,i,x:integer;

begin

write('Inputaugend:');readIn(n);

Iena:=length(n);｛加数放入a数组)

fori:=1toIenadoa[Iena-i+1]:=ord(n[i])-ordCO");

writeCInputaddend:')；readIn(n);

lenb:=length(n);｛被加数放入b数组)

fori:=1toIenbdob[Ienb-i+1]:=ord(n[i])-ordCO");

i：=1；

while(i<=lena)or(i<=lenb)dobegin

x:=a[i]+b[i]+xdiv10;｛两数相加，然后加前次进

位)

c[i]:=xmod10;｛保存第i位的值｝

i:=i+1

end;

ifx>=10then｛处理最高进位｝

beginler)c:=i;c[i]:=1end

eIselenc:=i-1;

fori:=lencdownto1dowrite(c[i]);｛输出结果｝

writeIn

end.

例2高精度减法。

从键盘读入两个正整数，求它们的差。

分析：类似加法，可以用竖式求减法。在做减法运算时，需要注意的是:

被减数必须比减数大，同时需要处理借位。

因此，可以写出如下关系式

ifa[i]<b[i]thenbegina[i+1]:=a[i+1]-1;a[i]:=a[i]+10end

c[i]:=a[i]-b[i]

类似，高精度减法的参考程序：

programexam2;

const

max=200;

var

a,b,c:array[1..max]of0..9;

n,n1,n2:string;

Iena,Ienb,Ienc,i,x:integer;

begin

write('Inputminuend:;readIn(n1);

writeCInputsubtrahend:')；readIn(n2);

(处理被减数和减数｝

if(Iength(n1)<Iength(n2))or(Iength(n1)=Iength(n2))and

(nKn2)then

begin

n:=n1;n1:=n2;n2:=n;

writeC)｛iTKnZ,结果为负数｝

end;

Iena:=Iength(n1);Ienb:=Iength(n2);

fori:=1toIenadoa[Iena-i+1]:=ord(n1[i])-ord('0');

fori:=1toIenbdob[Ienb-i+1]:=ord(n2[i])-ord('0T);

i：=1；

while(i<=lena)or(i<=lenb)dobegin

x:=a[i]-b[i]+10+x;｛不考虑大小问题，先往高位

借10｝

c[i]:=xmod10;｛保存第i位的值｝

X:=xdiv10-1;｛将高位借掉的1减去｝

i:=i+1

end;

Ienc:=i;

while(c[Ienc]=0)and(Ienc>1)dodec(Ienc);｛最高位的。不

输出｝

fori:=lencdownto1dowrite(c[i]);

writeIn

end.

例3高精度乘法。

从键盘读入两个正整数，求它们的积。

分析：类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，

同时对每一位进乘法运算时，必须进行错位相加，如图3,图4。

856A3A?A]

X25XB3B2B]

4280C4C3C2Ci

1712C5C4C3C2

21400C6c5c4c3c2cl

图3图4

分析c数组下标的变化规律，可以写出如下关系式

Ci~Ci+Ci+♦,,

由此可见，ci跟乘积有关，跟上次的进位有关，还跟原C,

的值有关，分析下标规律，有

x:=A[i]*B[j]+xDIV10+C[i+j-1];

C[i+j-1]:=xmod10;

类似，高精度乘法的参考程序：

programexam3;

const

max=200;

var

a,b,c:array[1..max]of0..9;

n1,n2:string;

Iena,Ienb,Ienc,i,j,x:integer;

begin

writeCInputmu11ipIier:');readIn(n1);

write('Inputmu11ipIicand:;readIn(n2);

lena:=length(n1);Ienb:=length(n2);

fori:=1toIenadoa[Iena-i+1]:=ord(n1[i])-ord('0");

fori:=1toIenbdob[Ienb-i+1]:=ord(n2[i])-ordC0');

fori:=1toIenadobegin

x:=0;

forj:=1toIenbdobegin｛对乘数的每一位进行

处理)

x:=+xdiv10+c[i+j-1];｛当前乘积+上次乘

积进位+原数｝

c[i+j-1]:=xmod10;

end;

c[i+j]:=xdiv10;｛进位｝

end;

lenc:=i+j;

while(c[Ienc]=0)and(Ienc>1)dodec(Ienc);

fori:=lencdownto1dowrite(c[i]);

writeIn

end.

例4高精度除法。

从键盘读入两个正整数，求它们的商(做整除)。

分析：做除法时，每一次上商的值都在0〜9,每次求得的余数连接以后

的若干位得到新的被除数，继续做除法。因此，在做高精度除法时，要涉及

到乘法运算和减法运算，还有移位处理。当然，为了程序简洁，可以避免高

精度乘法，用0〜9次循环减法取代得到商的值。这里，我们讨论一下高精度

数除以单精度数的结果，采取的方法是按位相除法。

参考程序：

programexam4;

const

max=200;

var

a,c:array[1..max]of0..9;

x,b:longint;

n1,n2:string;

Iena:integer;

code,i,j:integer;

begin

writeCInputdividend:;readIn(n1);

writeCInputdivisor:;readIn(n2);

lena:=length(n1);

fori:=1toIenadoa[i]:=ord(n1[i])一ordCO')；

vaI(n2,b,code);

｛按位相除｝

x:=0;

fori:=1toIenadobegin

c[i]:=(x*10+a[i])divb;

x:=(x*10+a[i])modb;

end;

｛显示商｝

j:=1;

while(c[j]=O)and(j<lena)doinc(j);｛去除高位的0｝

fori:=jtoIenadowrite(c[i]);

writeIn

end.

实质上，在做两个高精度运算时候，存储高精度数的数组元素可以不仅仅

只保留一个数字，而采取保留多位数(例如一个整型或长整型数据等)，这样,

在做运算(特别是乘法运算)时，可以减少很多操作次数。例如图5就是采

用4位保存的除法运算，其他运算也类似。具体程序可以修改上述例题予以

解决，程序请读者完成。

示例：123456789+45=1'2345'6789+45

=274'3484

1div45=0,1mod45=1

...取12345div45=274:12345mod45=15

A取156789div45=3484

答案为2743484,余数为156789mod45=9

图5

第三课排列与组合

课题：排列与组合

目标：

知识目标：如何利用程序就各种排列和组合

能力目标：排列组合的运用

重点：求出n的全排列和从m中取n个的组合

难点：算法的理解

板书示意：

1）求全排列的算法

2）求组合数的算法

授课过程：

例5：有3个人排成一个队列，问有多少种排对的方法，输出每一种方案？

分析：如果我们将3个人进行编号，分别为1、2、3,显然我们列出所有

的排列，123,132,213,231,312,321共六种。可用循环枚举各种情况，

参考程序：

programexam5;

var

i,j,k:integer;

begin

forI:=1to3do

forj:=1to3do

fork:=1to3do

if(i+j+k=6)and(i*j*k=6)thenwriteIn(i,j,k)；

end.

上述情况非常简单，因为只有3个人，但当有N个人时怎么办？显然用

循环不能解决问题。下面我们介绍一种求全排列的方法。

设当前排列为P|P2,Pn,则下一个排列可按如下算法完成：

1.求满足关系式PjT<巳的J的最大值，设为I,即

l=max{j|PJH<Pj,j=2..n)

2.求满足关系式Pk的k的最大值，设为j,即

J=max{K|Pi-i<Pk,k—1..n]

3.PiT与Pj互换得(P)=P,P2,Pn

4.(P)=P,P2,PTPi,…，Pn部分的顺序逆转，得RP2，…，P.-1Pn

Pn-1,Pi便是下--^排列。

例：设Plp2p3P4=3421

1.I=max{jIP,T<Pj,j=2..n}=2

2.J—max{K|P-<Pk,k—1..n}—2

3.R与P2交换得到4321

4.4321的321部分逆转得到4123即是3421的下一个排列。

程序设计如下：

programexam5;

const

maxn=100;

vari,j,m,t:integer;

p:array[1..maxn]ofinteger;

count:integer;{排列数目统计变量}

begin

writeCm:');readIn(m);

fori:=1tomdobeginp[i]:=i;write(i)end;

writeIn;

count:=1;

repeat

{求满足关系式巳的J的最大值，设为I}

i:=m;

while(i>1)and(p[i-1]>=p[i])dodec(i);

ifi=1thenbreak;

{求满足关系式PiT<Pk的k的最大值，设为j}

j：=m;

while(j>0)and(p[i-1]>=p[j])dodec(j);

ifj=0thenbreak;

{Pi与P,互换得(P)=P,P2,-,Pm}

t:=p[i-1];p[i-1]:=p[j];p[j]:=t;

{Pi,-,Pm的顺序逆转}

forj:=1to(m-i+1)div2dobegin

t:=p[i+j-1];p[i+j-1]:=p[m-j+1];p[m-j+1]:=t

end;

｛打印当前解｝

fori:=1tomdowrite(p[i]);

inc(count);

writeIn;

untiIfalse;

writeIn(count)

End.

例6：求N个人选取M个人出来做游戏，共有多少种取法？例如：N=4,

M=2时，有12,13,14,23,24,34共六种。

分析：因为组合数跟顺序的选择无关。因此对同一个组合的不同排列，

只需取其最小的一个(即按从小到大排序)。因此，可以设计如下算法：

1.最后一位数最大可达N,倒数第二位数最大可达N7,…，依此类推,

倒数第K位数最大可达N-K+1。

若R个元素组合用CG…CR表示，且假定C,<C2<-<CR,C《=N-R+I,

1=1,2,Ro

2.当存在CKN-R+J时，其中下标的最大者设为I,即

l=max｛J|C/N-R+J),则作G:=&+1,与之对应的操作有

G+1:=G+1，Ci+2:=Ci+i+1,***.,CR:—CR-I+1

参考程序：

programexam6;

constmaxn=10;

vari,j,n,m:integer;

c:array[1..maxn]ofinteger：｛c数组记录当前组合｝

Begin

WriteCn&m:');readIn(n,m);

fori:=1tomdobegin｛初始化，建立第一个组合｝

c[i]:=i;

write(c[i]);

end;

writeIn;

whilec[1]<n-m+1dobegin

j：=m;

while(c[j]>n-m+1)and(j>0)dodec(j);｛求l=max｛J|

Cj<N-R+J}}

c[j]:=c[j]+1;

fori:=j+1tomdoc[i]:=c[i-1]+1;（建立下一个

组合｝

fori:=1tomdowrite（c[i]）;writeIn｛输出｝

end;

End.

第四课枚举法

课题：枚举法

目标：

知识目标：枚举算法的本质和应用

能力目标：枚举算法的应用！

重点：利用枚举算法解决实际问题

难点：枚举算法的次数确定

板书示意：

1）简单枚举（例7、例8、例9）

2）利用枚举解决逻辑判断问题（例10、例11）

3）枚举解决竞赛问题（例12、例13、例14）

授课过程:

所谓枚举法，指的是从可能的解集合中一一枚举各元素，用题目给定的检

验条件判定哪些是无用的，哪些是有用的.能使命题成立，即为其解。一般

思路：

•对命题建立正确的数学模型；

•根据命题确定的数学模型中各变量的变化范围(即可能解的范围)；

•利用循环语句、条件判断语句逐步求解或证明；

枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又

一时找不到其他更好的算法时可以采用枚举法。

例7：求满足表达式A+B=C的所有整数解，其中A,B,C为1~3之间的整

数。

分析：本题非常简单，即枚举所有情况，符合表达式即可。算法如下:

forA7to3do

forB:=1to3do

forC:=1to3do

ifA+B=Cthen

WriteIn(A,,B,,C);

上例采用的就是枚举法。所谓枚举法，指的是从可能的解的集合中一一

枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能

使命题成立的，即为解。

从枚举法的定义可以看出，枚举法本质上属于搜索。但与隐式图的搜索有

所区别，在采用枚举法求解的问题时，必须满足两个条件：

①预先确定解的个数n；

②对每个解变量A1,A2,……，An的取值，其变化范围需预先确定

A.E{Xn,……，X1p}

A,G{XH,……，Xiq)

An£{XMXnk)

例7中的解变量有3个：A,B,Co其中

A解变量值的可能取值范围A£{1,2,3)

B解变量值的可能取值范围B£{1,2,3}

C解变量值的可能取值范围C《{1,2,3}

则问题的可能解有27个

(A,B,C)e{(1,1,1),(1,1,2),(1,1,3),

(1,2,1),(1,2,2),(1,2,3),

(3,3,1),(3,3,2),(3,3,3)}

在上述可能解集合中，满足题目给定的检验条件的解元素，即为问题的解。

如果我们无法预先确定解的个数或各解的值域，则不能用枚举，只能采用

搜索等算法求解。由于回溯法在搜索每个可能解的枚举次数一般不止一次，

因此，对于同样规模的问题，回溯算法要比枚举法时间复杂度稍高。

例8给定一个二元一次方程aX+bY=c。从键盘输入a,b,c的数值，求X在

[0,100],丫在[0,100]范围内的所有整数解。

分析：要求方程的在一个范围内的解，只要对这个范围内的所有整数点进

行枚举，看这些点是否满足方程即可。参考程序：

programexam8;

var

a,b,c:integer;

x,y:integer;

begin

write('Inputa,b,c:')；readIn(a,b,c);

forx:=0to100do

fory:=0to100do

ifa*x+b*y=cthenwriteIn(x,'',y);

end.

从上例可以看出，所谓枚举法,指的是从可能的解集合中一一枚举各元素,

用题目给定的检验条件判定哪些是无用的，哪些是有用的.能使命题成立,

即为其解。

例9巧妙填数

将1〜9这九个数字填入九个空格中。每一横行的三个数字组成一个三位

数。如果要使第二行的三位数是第一行的两倍，第三

行的三位数是第n23一行的三倍，应怎样填数。如图6:

3

图6

分析：本题目有9个格子，要求填数，如果不考虑问题给出的条件，共

有9!=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用

枚举法。

但仔细分析问题，显然第一行的数不会超过400,实际上只要确定第一行

的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。因此设计

参考程序：

programexam9;

var

i,j,k,s:integer;

functionsum(s:integer):integer;

begin

sum:=sdiv100+sdiv10mod10+smod10

end;

functionmuI(s:integer):Iongint;

begin

muI:=(sdiv100)*(sdiv10mod10)*(smod10)

end;

begin

fori:=1to3do

forj:=1to9do

ifj<>ithenfork:=1to9do

if(k<>j)and(k<>i)thenbegin

s:=i*100+j*10+k;｛求第一行数｝

if3*s<1000then

if(sum(s)+sum(2*s)+sum(3*s)=45)and

(muI(s)*muI(2*s)*muI(3*s)=362880)then｛满足条件，并数

字都由1~9组成｝

begin

writeIn(s);

writeln(2*s);

writeln(3*s);

writeIn;

end;

end;

end.

例10在某次数学竞赛中，A、B、C、D、E五名学生被取为前五名。请据

下列说法判断出他们的具体名次，即谁是第几名？

条件1：你如果认为A,B,C,D,E就是这些人的第一至第五名的名次排列,

便大错。因为：

没猜对任何一个优胜者的名次。

也没猜对任何一对名次相邻的学生。

条件2:你如果按D,A,E,C,B来排列五人名次的话，其结果是：

说对了其中两个人的名次。

还猜中了两对名次相邻的学生的名次顺序。

分析：本题是一个逻辑判断题，一般的逻辑判断题都采用枚举法进行解决。

5个人的名次分别可以有5!=120种排列可能，因为120比较小,因此我

们对每种情况进行枚举，然后根据条件判断哪些符合问题的要求。

根据已知条件，A<>1,B<>2,C<>3,D<>4,E<>5,因此排除了一种可能性，只

有4!=24种情况了。

参考程序：

ProgramExamlO;

Var

A,B,C,D,E:Integer;

Cr:Array[1..5]OfChar;

Begin

ForA:=1To5Do

ForB:=1To5Do

ForC:=1To5Do

ForD:=1To5Do

ForE:=1To5DoBegin

｛ABCDE没猜对一个人的名次｝

If(A=1)Or(B=2)Or(C=3)Or(D=4)Or(E=5)ThenContinue;

If[A,B,C,D,E]<>[1,2,3,4,5]ThenContinue;｛他们名次互不

重复｝

[DAECB猜对了两个人的名次｝

IfOrd(A=2)+Ord(B=5)+Ord(C=4)+Ord(D=1)+Ord(E=3)02Then

Continue;

｛ABODE没猜对一对相邻名次)

If(B=A+1)Or(C=B+1)Or(D=C+1)Or(E=D+1)ThenContinue;

｛DAECB猜对了两对相邻人名次｝

IfOrd(A=D+1)+Ord(E=A+1)+Ord(C=E+1)+Ord(B=C+1)02Then

Continue;

Cr[A]:='A';Cr[B]:='B';Cr[C]:='C';

Cr[D]:='D';Cr[E]:='E';

WRITELN(CR[1],'',CR[2],'',CR[3],'',CR[4],'',CR[5]);

End;

End.

例11：来自不同国家的四位留学生A,B,C,D在一起交谈,他们只会中、英、

法、日四种语言中的2种，情况是，没有人既会日语又会法语;A会日语，但D

不会,A和D能互相交谈,B不会英语，但A和C交谈时却要B当翻译,B,C,D三

个想互相交谈，但找不到共同的语言，只有一种语言3人都会，编程确定

A,B,C,D四位留学生各会哪两种语言。

分析：将中、法、日、英四种语言分别定义为CHN、FRH、JPN、ENG,则四

种语言中取两种共有(CHN,ENG),

(CHN,FRH),(CHN,JPN),(ENG,FRH),(ENG,JPN),(FRH,JPN)六种组合，分别

定义为1、2、3、4、5、6o据已知，没有人既会日语又会法语；因此，组合6

不会出现；A会日语，所以A只可能等于3、5；D不会日语，所以D只可能

等于1、2、4；B不会英语，所以B只可能等于2、3；见下表。如果我们对A、

B、C、D分别进行枚举，根据判定条件，即可找到答案。

(CHN,EN(CHN,FR(CHN,JP(ENG,F(ENG,J

G)WN)RH)PN)

AXXX

BXXX

C

DXX

程序如下:

programEXAM11;

type

Language=(CHN,ENG,FRH,JPN);

TNoSet=setofLanguage;

const

No:array[1..5]ofTNoSet=

([CHN,ENG],[CHN,FRH],[CHN,JPN],[ENG,FRH],

[ENG,JPN]);

var

A,B,C,D:1..5;

Can1,Can2,Can3,Can4:BooIean;

functionMight(Lang:Language):Boolean;

var

BooI:Boolean;

begin

BooI:=faIse;

ifNo[A]*No[A]*No[C]=[Lang]thenBooI:=True;

ifNo[A]*No[B]*No[D]=[Lang]thenBooI:=True;

ifNo[A]*No[C]*No[D]=[Lang]thenBooI:=True;

ifNo[B]*No[C]*No[D]=[Lang]thenBooI:=True;

Might:=BooI

end;

procedurePrint(A,B,C,D:Integer);

procedureShow(P:Integer;Ch:Char);

var

I:Integer;

Lang:Language;

begin

Write(ch,':');

forLang:=CHNtoJPNdo

ifLanginNo[P]then

caseLangof

CHN:WriteCCHN':5);

FRH:WriteCFRH':5);

JPN:WriteCJPN':5);

ENG:WriteCENG':5);

end;

Writein;

end;

begin

Show(A,'A')；

Show(B,旧);

Show(C,S;

Show(D,'D')；

end;

begin

forA:=3to5do

ifA<>4thenforB:=2to3do

forC:=1to5do

forD:=1to4doifD<>3thenbegin

｛A和D能互相交谈｝

Can1:=No[A]*No[D]<>[];

｛A和C交谈时却要B当翻译｝

Can2:=(No[A]*No[C]=[])and(No[A]*No[B]<>[])

and(No[B]*No[C]<>口)；

｛B,C,D三个想互相交谈，但找不到共同的语言)

Can3:=No[B]*No[C]*No[D]=口；

｛只有一种语言3人都会｝

Can4:=Ord(Might(CHN))+Ord(Might(ENG))

+Ord(Might(FRH))+Ord(Might(JPN))=1;

ifCar)1andCan2andCan3andCan4thenPrint(A,B,C,D);

end;

end.

例12古纸残篇

在一位数学家的藏书中夹有一张古旧的纸片。纸片上的字早已模糊不清

了，只留下曾经写过字的痕迹，依稀还可以看出它是一个乘法算式，如图7

所示。这个算式上原来的数字是什么呢？夹着这张纸片的书页上，“素数”两

个字被醒目的划了出来。难道说，这个算式与素数有什么关系吗？有人对此

作了深入的研究，果然发现这个算式中的每一个

***

数字都是素数，而且这样的算式是唯一的。请你***

****

也研究一番，并把这个算式写出来。****

分析：实际上，只要知道乘数和被乘数就可闺7

以写出乘法算式，所以我们可以枚举乘数与被乘数的每一位。然后再判断是

不是满足条件即可。计算量是45=1024,对于计算机来说，计算量非常小。

参考程序：

ProgramExaml2;

Const

Su:Array[1..4]OfLongint=(2,3,5,7);

Var

A1,A2,A3,B1,B2,X,Y,S:Longint;

FunctionKx(S:Longint):BooIean;｛判断一个数

是不是都是由素数组成｝

Begin

Kx:=True;

WhileSOODoBegin

IfNot((SMod10)In[2,3,5,7])ThenBegin

Kx:=FaIse;

Exit;

End;

S:=SDiv10;

End;

End;

Begin

ForA1:=1To4Do

ForA2:=1To4Do

ForA3:=1To4Do

ForB1:=1To4Do

ForB2:=1To4DoBegin

X:=Su[A1]*100+Su[A2]*10+Su[A3];｛X为被乘数｝

IfX*Su[B1]<1000ThenContinue;

IfX*Su[B2]<1000ThenContinue;

IfX*(Su[B1]*10+Su[B2])<10000ThenContinue;

｛它们分别是两个四位数，一个五位数｝

If(Kx(X*Su[B1])=False)Or

(Kx(X*Su[B2])=False)Or

(Kx(X*(Su[B1]*10+Su[B2]))=FaIse)ThenContinue;

｛满足其他数都是由质数构成｝

WritelnC',Su[A1],Su[A2],Su[A3]);

WritelnC*',Su[B1],Su[B2]);

WritelnC-----------，);

WritelnC',X*Su[B2]);

WritelnCr,X*Su[B1]);

WritelnC-----------，);

WritelnC',X*(Su[B1]*10+Su[B2]));

End;

End.

例13：时钟问题(I0I94-4)

在图8所示的3*3矩阵中有9个时钟，我们的目标是旋转时钟指针，使所

有时钟的指针都指向12点。允许旋转时钟指针的方法有9种，每一种移动用

一个数字号(1,2,…，9)表示。图2-11示出9个数字号与相应的受控制

的时钟，这些时钟在图中以灰色标出，其指针将顺时针旋转90度。

••O•••O••

••OOOOO••

OOOOOOOOO

123

•OOO•OOO•

。。。•OO•••OO•

ooo•OOO•OOO•

456

ooo

OOOOOOOOO

••OOOOO••

••O•••O••

图8九种时钟状态

789

•——受控制的时钟

图9九种被控制方式

输入数据：

由输入文件INPUT.TXT读9个数码，这些数码给出了9个时钟时针的初始

位置。数码与时刻的对应关系为：

0——12点

1——3点

2——6点

3——9点

图2-11中的例子对应下列输入数据：

330

222

212

输出数据：

将一个最短的移动序列（数字序列）写入输出文件OUTPUT.TXT中，该序

列要使所有的时钟指针指向12点，若有等价的多个解，仅需给出其中一个。

在我们的例子中,相应的OUTPUT.TXT的内容为：

5849

输入输出示例：

INPUT.TXTOUTPUT.TXT

3305489

222

212

具体的移动方案如图10所示。

。

。

O0O。sOSO

OG5[OOO^e>O0oOeOO0

Gt=^>OOOO0oOO0

e。

9I©OQ

.o

图io示例移动方案

分析：

首先，我们分析一下表示时钟时针初始位置的数码j（OWj皂3）与时刻

的对应关系:

0—12点

1——3点

2——6点

3——9点

每移动一次，时针将顺时针旋转90度。由此我们可以得出：

对于任意一个时钟i（1Wi三9）来说，从初始位置j出发至少需要G=（4-j）

mod4次操作，才能使得时针指向12点。而对每种移动方法要么不采用，要

么采用1次、2次或3次，因为操作四次以后，时钟将重复以前状态。因此，

9种旋转方案最多产生49个状态。

移动方案选取与顺序无关。样例中，最佳移动序列为5849,同样4589序

列也可达到目标。因此，求解过程中可以直接选取序列中从小至大排列的移

动序列即可。

设P.表示第i种旋转方法的使用次数（0WpiW3,1皂i皂9）。

则可能的解的集合为口，P2,……，PJ,该集合共含49个状态。从图2.11

中，我们可以分析出9个时钟分别被哪些方法所控制，见下表：

时钟号控制时钟方案检验条件

11、2、4Ci-(P1+P2+P4)mod4

21、2、3、5C2=(P1+P2+P3+P5)mod4

32、3、6C3-(P2+P3+P6)mod4

41、4、5、7CL(P1+P4+P5+P7)mod4

51、3、5、7、9C5-(P1+P3+P5+P7+P9)mod

4

63、5、6、906~(P3+P5+P6+P9)mod4

74、7、8C7-(P4+P7+P8)mod4

85、7、8、9C8=(P5+P7+P8+P9)mod4

96、8、9C9—(P6+P8-^P9)mod4

因此我们可以设计如下枚举算法:

forp1:=0to3do

forp2:=0to3do

forp9:=0to3do

ifd满足时钟1andc2满足时钟2and...andc9满足时

钟9then

打印解路径;

显然，上述枚举算法枚举了所有4~262144个状态，运算量和运行时间颇

大。我们可以采取缩小可能解范围的局部枚举法，仅枚举第1、2、3种旋转

方法可能取的4?个状态，根据这三种旋转方法的当前状态值，由下述公式

P4=order(C1-P1-P2);

P5=order(C2-P1-P2-P3)；

P6=order(C3-P2-P3)；

=---

P7order(C4PIP4P5)；

P8=order(C8-P5-PP9)；

P9=order(C6-P3-P5-P6)；

其中

,、fcmod4c>0

。力r(zc)=j(c+Nx4)mod4c<0

得出其余P“……Pg的相应状态值。然后将巴，P2,…，P9代入下述三个检

验条件

=

C5(P1+P3+P5+P7+P9)mod4

C7=(P4+P7+P8)mod4

C9—(Pe+Ps+PJmod4

一一枚举，以求得确切解。

由此可见，上述局部枚举的方法(枚举状态数为4?个)比较全部枚举的方

法(枚举状态数为4,个)来说，由于大幅度削减了枚举量，减少运算次数，

因此其时效显著改善，是一种优化了的算法。

程序如下：

programI0I94_4;

const

Inp=input.txt';

Outp='output.txt';

var

Clock,Map:array[1..3,1..3]ofInteger;

｛Clock：第((l+2)mod3)*3+J个时钟从初始时间到12点的最少移动次

数｝

｛Map:最短移动序列中，数字((I+2)mod3)*3+J的次数｝

procedureInit;

var

I,J:Integer;

begin

Assign(Input,Inp);Reset(Input);

forI:=1to3do

｛读入9个时钟指针的初始位置，求出每个时钟从初始到12点的最少

移动次数｝

forJ:=1to3d