基础算法教案

基础算法教案目录

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

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

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

第四课枚举法..............................................................................9

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

第六课递推法.............................................................................42

第七课贪心法.............................................................................50

第八课分治法.............................................................................64

第九课模拟法.............................................................................70

习题......................................................................................79

第一部分基础算法蕤拿

第一课算法简介

算法是一组（有限个）规则，它为某个特定问题提供了解决问题的运算序列。在信息学竞赛

中，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写算法，都是在实施某

种算法。前者是推理实现的算法，后者是操作实现的算法。

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

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

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

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

法本身给出了初始条件；

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

是毫无意义的；

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

为了获得一个既有效又优美的算法，必须首先了解一些基本的常用算法设计思路。下面，我

们就对构成算法所依据的一些基本方法展开讨论，如递推法，递归法，枚举法，分治法，模拟法,

贪心法等。

第二课多精度数值处理

课题：多精度数值的处理

目标：

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

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

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

难点：进位与借位处理

板书示意：

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

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

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

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

授课过程：

所谓多精度值处理，就是在对给定的数据范围，用语言本身提供的数据类型无法直接进行处

理（主要指加减乘除运算），而需要采用特殊的处理办法进行。看看下面的例子。

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

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

道，在pascal语言中任何数据类型都有一定的表示范围。而当两个被加数据大时，上述算法显然

不能求出精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，

如图lo

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

856A、A[A]

+255+B3B2B)

1111C4c3c2G

图1图2

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

A[l]=6,A[2]=5,A[3]=8,B[l]=5,B[2]=5,B[3]=2,C[4]=l,C[3]=l,C[2]=l,两数

相加如图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:=l

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;

lena,lenb,lenc,i,x:integer;

begin

writeInputaugend:');readln(n);

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

fori:=1tolenadoa[lena-i+l]:=ord(n[i])-ord(，0J);

writeInputaddend:');readln(n);

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

fori:=1tolenbdob[lenb-i+l]:=ord(n[i])-ord(,01);

i:=l;

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

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

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

i:=i+1

end;

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

beginlenc:=i;c[i]:=1end

elselenc:=i-l;

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

writein

end.

例2高精度减法。

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

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

大，同时需要处理借位。

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

ifa[i]<b[i]thenbegina[i+l]:=a[i+l]-l;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,nl,n2:string;

lena,lenb,lenc,i,x:integer;

begin

write(?Inputminuend/);readln(nl);

write(，Inputsubtrahend/);readln(n2);

｛处理被减数和减数｝

if(length(nl)<length(n2))or(length(nl)=length(n2))and(nl<n2)then

begin

n:=nl;nl:=n2;n2:=n;

writeC-')｛nl<n2,结果为负数｝

end;

lena:=length(nl);lenb:=length(n2);

fori:=1tolenadoa[lena-i+l]:=ord(nl[i])-ord(，;

fori:=1tolenbdob[lenb-i+l]:=ord(n2[i])-ord(,0,);

i:=l;

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;

lenc:=i;

while(c[lenc]=0)and(lenc>l)dodec(lenc);｛最高位的0不输出｝

fori:=lencdownto1dowrite(c[i]);

writein

end.

例3高精度乘法。

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

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

法运算时，必须进行错位相加，如图3,图4。

856A3A2Ai

X25XB3B2Bi

4280C4C3C2C1

1712C5C4C3C2

21400C6c5c4c3c2cl

图3图4

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

Ci=Ci+Ci+…

由此可见，Ci跟乘积有关，跟上次的进位有关，还跟原CI的值有关，分析下标

规律，有

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

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

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

programexam3;

const

max=200;

var

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

nl,n2:string;

lena,lenb,lenc,i,j,x:integer;

begin

writeInputmultiplier/);readln(nl);

write(，Inputmultiplicand:?;readln(n2);

lena:=length(nl);lenb:=length(n2);

fori:=1tolenadoa[lena-i+l]:=ord(nl[i])-ord(，0*);

fori:=1tolenbdob[lenb-i+l]:=ord(n2[i])-ord(，0?);

fori:=1tolenadobegin

x:=0;

forj:=ltolenbdobegin｛对乘数的每一位进行处理｝

x:=a[i]*b[j]+xdiv10+c[i+jT];｛当前乘积+上次乘积进位+原数｝

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

end;

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

end;

lenc:=i+j;

while(c[lenc]=0)and(lenc>l)dodec(lenc);

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;

nl,n2:string;

lena:integer;

code,i,j:integer;

begin

writeCInputdividend:');readln(nl);

writeCInputdivisor:');readln(n2);

lena:=length(nl);

fori:=ltolenadoa[i]:=ord(nl[i])-ord('O');

val(n2,b,code);

｛按位相除｝

x:=0;

fori:=1tolenadobegin

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

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

end;

｛显示商｝

j：=l；

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

fori:=jtolenadowrite(c[ij);

writein

end.

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

而采取保留多位数(例如一个整型或长整型数据等)，这样，在做运算(特别是乘法运算)时，可

以减少很多操作次数。例如图5就是采用4位保存的除法运算，其他运算也类似。具体程序可以

修改上述例题予以解决，程序请读者完成。

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

=274'3484

,/1div45=0,1mod45=1

.•.取12345div45=274T12345mod45=15

/.取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:=lto3do

if(i+j+k=6)and(i*j*k=6)thenwritein(i,j,k);

end.

上述情况非常简单，因为只有3个人，但当有N个人时怎么办？显然用循环不能解决问题。

下面我们介绍一种求全排列的方法。

设当前排列为PiBp,„则下一个排列可按如下算法完成：

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

I=max{j|PM<Pj,j=2..n}

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

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

3.P-与P,互换得(P)=P,P2,PiP,i-,P„

4.(P)=PiR,…，PiPi,…，P”部分的顺序逆转，得RP2PiP.*,…，P,便是下

一个排列。

例:设PiP2P3P”=3421

1.1=max{j|PJH<Pj,j=2..n}=2

2.J=max{KPHI<Pk,k=l..n}=2

3.Pi与Pz交换得到4321

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

程序设计如下：

programexam5;

const

maxn=100;

vari,j,m,t:integer;

p:array[1..maxn]ofinteger;

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

begin

write('m:');readln(m);

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

writein;

count:=1;

repeat

{求满足关系式PM<Pj的J的最大值，设为1}

i:=m;

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

ifi=lthenbreak;

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

j：=m；

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

ifj=0thenbreak;

{Ps与Pj互换得(P)=PiP2,PJ

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

{Pi,匕的顺序逆转}

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

t：=p[i+j-l]；p[i+j-l]：=p[m-j+l];p[m-j+l]:=t

end;

{打印当前解}

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

inc(count);

writein;

untilfalse;

writein(count)

End.

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

14,23,24,34共六种。

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

(即按从小到大排序)。因此，可以设计如下算法：

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

可达N-K+lo

若R个元素组合用C©…CR表示，且假定R9<・・YCR,CK=N-R+L1=1,2,-,RO

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

I=max{JIC<N-R+J},则作G:=G+1,与之对应的操作有

Ci+i:=Ci+1，Ci+2:=Ci+1+1，….，CR:=CR-I+1

参考程序:

programexam6;

constmaxn=10;

vari,j,n,m:integer;

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

Begin

Write('n&m:');readln(n,m);

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

c[i]:=i;

write(c[i]);

end;

writein;

whilec[l]<n-m+ldobegin

j：=m;

while(c[j]>n-m+l)and(j>0)dodec(j);｛求I初ax｛JCj<N-R+J｝｝

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

fori:=j+ltomdoc[i]:=c[i-l]+l;｛建立下一个组合｝

fori:=1tomdowrite(c[i]);writeln｛输出｝

end;

End.

第四课枚举法

课题：枚举法

目标：

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

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

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

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

板书示意：

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

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

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

授课过程：

所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无

用的,哪些是有用的.能使命题成立,即为其解。一般思路：

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

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

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

枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更好

的算法时可以采用枚举法。

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

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

forA:=1to3do

forB:=1to3do

forC:=1to3do

ifA+B=Cthen

Writein(A,'+，,Bf'='，C);

上例采用的就是枚举法。

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

举法求解的问题时，必须满足两个条件：

①预先确定解的个数n；

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

AC{X"，……，XIp}

AjS{Xu,……，Xiq}

A„e{Xm,....,X„k}

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

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

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

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

则问题的可能解有27个

(A,B,C)G{(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)}

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

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

由于回溯法在搜索每个可能解的枚举次数一般不止一次，因此，对于同样规模的问题，回溯算法

要比枚举法时间复杂度稍高。

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

100］范围内的所有整数解。

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

是否满足方程即可。参考程序：

programexam8;

var

a,b,c:integer;

x,y:integer;

begin

write(*Inputa,b,c:');readln(a,b,c);

forx:=0to100do

fory:=0to100do

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

end.

从上例可以看出，所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验

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

例9巧妙填数

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

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

192

384

576

图6

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

在这些方案中符合问题条件的即为解。因此可以采用枚举法。

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

件算出其他两行的数了。这样仅需枚举400次。因此设计参考程序：

programexam9;

var

i,j,k,s:integer;

functionsum(s:integer):integer;

begin

sum:=sdiv100+sdiv10mod10+smod10

end;

functionmul(s:integer):longint;

begin

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

end;

begin

fori:=1to3do

forj:=1to9do

ifjOithenfork:=lto9do

if(kOj)and(kOi)thenbegin

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

if3*s<1000then

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

(mul(s)*mul(2*s)*mul(3*s)=362880)then｛满足条件，并数字都由1~9组成｝

begin

writein(s);

writein(2*s);

writein(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根<>2,C〈〉3,D<>4,E<>5,因此排除了一种可能性,只有4!=24种情况了。

参考程序：

ProgramExamlO;

Var

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

Cr:Array[1..5]OfChar;

Begin

ForA:=lTo5Do

ForB:=lTo5Do

ForC:=lTo5Do

ForD:=lTo5Do

ForE:=lTo5DoBegin

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

If(A=l)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)+0rd(B=5)+0rd(C=4)+0rd(D=l)+0rd(E=3)02ThenContinue;

｛ABCDE没猜对一对相邻名次｝

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)02ThenContinue;

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、6。据已知，没有人既会日语又会法语;因此，组合6不会出现；A会日语，所以

A只可能等于3、5；D不会日语，所以D只可能等于1、2、4；B不会英语，所以B只可能等于2、

3；见下表。如果我们对A、B、C、D分别进行枚举，根据判定条件，即可找到答案。

(CHN,ENG)(CHN,FRH)(CHN,JPN)(ENG,FRH)(ENG,JPN)

AXXX

BXXX

C

DXX

程序如下：

programEXAM11;

type

Language二(CHN,ENG,FRII,JPN);

TNoSet=setofLanguage;

const

No:array[1..5]ofTNoSet=

([CHN,ENG],[CHN,FRH],[CFIN,JPN],[ENG,FRH],[ENG,JPN]);

var

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

Canl,Can2,Can3,Can4:Boolean;

functionMight(Lang:Language):Boolean;

var

Bool:Boolean;

begin

Bool:=false;

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

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

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

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

Might:=Bool

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:Write('CHN':5);

FRH:Write(，FRH,:5);

JPN:Write('JPN':5);

ENG:Write,ENG':5);

end;

Writein;

end;

begin

Show(A,'A');

Show(B,'B');

Show(C,'C');

Show(D,*D*);

end;

begin

forA:=3to5do

ifA<>4thenforB:=2to3do

forC:=1to5do

forD:=1to4doifD<>3thenbegin

｛A和D能互相交谈｝

Canl:=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;

ifCanlandCan2andCan3andCan4thenPrint(A,B,C,D);

end;

end.

例12古纸残篇

在一位数学家的藏书中夹有一张古旧的纸片。纸片上的字早已模糊不清了，只留下曾经写过

字的痕迹，依稀还可以看出它是一个乘法算式，如图7所示。这个算式上原来的数字是什么呢？

夹着这张纸片的书页上，“素数”两个字被醒目的划了出来。难道

说，这个算式与素数有什么关系吗？有人对此作了深入的研究，***

果然发现这个算式中的每一个数字都是素数，而且这样的算式是***

****

****

图7

唯一的。请你也研究一番，并把这个算式写出来。

分析：实际上，只要知道乘数和被乘数就可以写出乘法算式，所以我们可以枚举乘数与被乘

数的每一位。然后再判断是不是满足条件即可。计算量是4J1024,对于计算机来说，计算量非常

小。

参考程序：

ProgramExaml2;

Const

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

Var

Al,A2,A3,Bl,B2,X,Y,S:Longint;

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

是不是都是由素数组成｝

Begin

Kx:=True;

WhileSOODoBegin

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

Kx:二False;

Exit;

End;

S:=SDiv10;

End;

End;

Begin

ForAl:=1To4Do

ForA2:=lTo4Do

ForA3:=lTo4Do

ForBl:=lTo4Do

ForB2:=lTo4DoBegin

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

IfX*Su[Bl]<1000ThenContinue;

IfX*Su[B2]<1000ThenContinue;

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

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

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

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

(Kx(X*(Su[Bl]*10+Su[B2]))=False)ThenContinue;

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

Writein('\Su[Al],Su[A2],Su[A3]);

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

WriteinC-----------');

WriteinC',X*Su[B2]);

WriteinC\X*Su[Bl]);

WriteinC-----------，);

Writein('',X*(Su[Bl]*10+Su[B2]));

End;

End.

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

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

向12点。允许旋转时钟指针的方法有9种，每一种移动用一个数字号(1,2,…，9)表示。图

2-11示出9个数字号与相应的受控制的时钟，这些时钟在图中以灰色标出，其指针将顺时针旋转

••O•••O••

••OOOOO••

OOOOOOOOO

123

•OOO•OOO•

OO©•OO•••OO•

•OOO•OOO•

CDOO456

OOQOOOOOOOOO

••OOOOO••

••O•••O••

图8九种时钟状态

789

・一一受控制的时钟

图9九种被控制方式

90度。

输入数据：

由输入文件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所示。

eo06Oo©OOSOO

O(D(D0O

Gog5。Oo0oOO

QG9>=^>OOOeOO0OeOOO

QO,

图10示例移动方案

分析：

首先，我们分析•下表示时钟时针初始位置的数码j(0WjW3)与时刻的对应关系：

0——12点

1——3点

2—6点

3——9点

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

对于任意一个时钟i(lWiW9)来说，从初始位置j出发至少需要3=(4-j)mod4次操作,

才能使得时针指向12点。而对每种移动方法要么不采用，要么采用1次、2次或3次，因为操作

四次以后，时钟将重复以前状态。因此，9种旋转方案最多产生4’个状态。

移动方案选取与顺序无关。样例中，最佳移动序列为5849,同样4589序列也可达到目标。因

此，求解过程中可以直接选取序列中从小至大排列的移动序列即可。

设表示第i种旋转方法的使用次数(0Wp；W3,lWiW9)。

则可能的解的集合为｛Pi,P2,……，PJ,该集合共含49个状态。从图2.11中，我们可以分

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

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

11、2、4Ci二(P1+P2+P1)mod4

21、2、3、5C2=(Pi+P?+P3+P5)mod4

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

41、4、5、7Ci=(P1+P1+P5+P7)mod4

51、3、5、7、9Cs=(P1+P3+P5+P7+P9)mod4

63、5、6、9C6=(P3+Ps+P6+P9)mod4

74、7、8Ck(P1+P7+P8)mod4

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

96、8、9C9=(Pe+Ps+Pg)mod4

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

forpl:=0to3do

forp2:=0to3do

forp9:=0to3do

ifcl满足时钟1andc2满足时钟2and...andc9满足时钟9then

打印解路径;

显然，上述枚举算法枚举了所有『二262144个状态，运算量和运行时间颇大。我们可以采取缩

小可能解范围的局部枚举法，仅枚举第1、2、3种旋转方法可能取的4,个状态，根据这三种旋转

方法的当前状态值，山下述公式

Pporder(C1-P1-P2);

P.5=order(C2-P1-P2-P3