信息学奥赛基础算法教案

基础算法教案 第 0 页 共 82 页 基础算法教案基础算法教案 目录目录 第一课第一课 算算法简介法简介.1 第二课第二课 多多精精度度数值处理数值处理.1 第三课第三课 排列排列与与组组合合.6 第四课第四课 枚枚举举法法.9 第五课第五课 递归与回递归与回溯溯法法.25 第六课第六课 递递推推法法.42 第七课第七课 贪贪心法心法.50 第八课第八课 分分治治法法.64 第九课第九课 模模拟拟法法.70 习习题题.79 基础算法教案 第 1 页 共 82 页 第一课 算法简介 算法是一组（有限个）规则，它为某个特定问题提供了解决问题的运算序列。在信息学竞赛中， 就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写算法，都是在实施某种算法。 前者是推理实现的算法，后者是操作实现的算法。 计算机解题的核心是算法设计。一个算法应该具有以下五个重要特征： 有穷性：一个算法必须能在执行有限步之后结束； 确切性：算法的每一步骤必须确切定义； 输入：一个算法有零个或多个输入，以描述运算对象的初始情况。所谓 0 个输入是指算法本 身给出了初始条件； 输出：一个算法有一个或多个输出，以反映对输入数据处理后的结果。没有输出的算法是毫 无意义的； 可行性：算法原则上能够精确的运行，而且其运算规模是可以承受的。 为了获得一个既有效又优美的算法，必须首先了解一些基本的常用算法设计思路。下面，我们就 对构成算法所依据的一些基本方法展开讨论，如递推法，递归法，枚举法，分治法，模拟法，贪心法 等。 第二课 多精度数值处理 课题：多精度数值的处理 目标： 知识目标：多精度值的加、减、乘、除 能力目标：多精度值的处理，优化！ 重点：多精度的加、减、乘 难点：进位与借位处理 板书示意： 1） 输入两个正整数，求它们的和 2） 输入两个正整数，求它们的差 3） 输入两个正整数，求它们的积 4） 输入两个正整数，求它们的商 授课过程： 所谓多精度值处理，就是在对给定的数据范围，用语言本身提供的数据类型无法直接进行处理 （主要指加减乘除运算） ，而需要采用特殊的处理办法进行。看看下面的例子。 例 1 从键盘读入两个正整数，求它们的和。 分析：从键盘读入两个数到两个变量中，然后用赋值语句求它们的和，输出。但是，我们知道， 在 pascal 语言中任何数据类型都有一定的表示范围。而当两个被加数据大时，上述算法显然不能求出 精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，如图 1。 基础算法教案 第 2 页 共 82 页 这样，我们方便写出两个整数相加的算法。 如果我们用数组 A、B 分别存储加数和被加数，用数组 C 存储结果。则上例有 A1=6, A2=5, A3=8, B1=5,B2=5, B3=2, C4=1,C3=1, C2=1,C1=1,两数相加 如图 2 所示。由上图可以看出： Ci:= Ai+Bi; if Ci10 then begin Ci:= Ci mod 10; Ci+1:= Ci+1+1 end; 因此，算法描述如下： procedure add(a,b;var c); a,b,c 都为数组，a 存储被加数，b 存储加数，c 存储结果 var i,x:integer; begin i:=1 while (i0) or(i=b 数组的长度) do begin x := ai + bi + x div 10; 第 i 位相加并加上次的进位 ci := x mod 10; 存储第 i 位的值 i := i + 1 位置指针变量 end end; 通常，读入的两个整数用可用字符串来存储，程序设计如下： program exam1; const max=200; var a,b,c:array1.max of 0.9; n:string; lena,lenb,lenc,i,x:integer; begin write(Input augend:); readln(n); lena:=length(n); 加数放入 a 数组 for i:=1 to lena do alena-i+1:=ord(ni)-ord(0); write(Input addend:); readln(n); lenb:=length(n); 被加数放入 b 数组 for i:=1 to lenb do blenb-i+1:=ord(ni)-ord(0); i:=1; 8 5 6 + 2 5 5 1 1 1 1 图 1 A3 A2 A1 + B3 B2 B1 C4 C3 C2 C1 图 2 基础算法教案 第 3 页 共 82 页 while (i=lena) or(i=10 then 处理最高进位 begin lenc:=i;ci:=1 end else lenc:=i-1; for i:=lenc downto 1 do write(ci); 输出结果 writeln end. 例 2 高精度减法。 从键盘读入两个正整数，求它们的差。 分析：类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大， 同时需要处理借位。 因此，可以写出如下关系式 if aibi then begin ai+1:=ai+1-1;ai:=ai+10 end ci:=ai-bi 类似，高精度减法的参考程序： program exam2; const max=200; var a,b,c:array1.max of 0.9; n,n1,n2:string; lena,lenb,lenc,i,x:integer; begin write(Input minuend:); readln(n1); write(Input subtrahend:); readln(n2); 处理被减数和减数 if (length(n1)length(n2) or (length(n1)=length(n2) and (n1n2) then begin n:=n1;n1:=n2;n2:=n; write(-) n1n2,结果为负数 end; lena:=length(n1); lenb:=length(n2); for i:=1 to lena do alena-i+1:=ord(n1i)-ord(0); for i:=1 to lenb do blenb-i+1:=ord(n2i)-ord(0); 基础算法教案 第 4 页 共 82 页 i:=1; while (i1) do dec(lenc); for i:=lenc downto 1 do write(ci); writeln end. 例 高精度除法。 从键盘读入两个正整数，求它们的商（做整除） 。 分析：做除法时，每一次上商的值都在，每次求得的余数连接以后的若干位得到新的被除 数，继续做除法。因此，在做高精度除法时，要涉及到乘法运算和减法运算，还有移位处理。当然， 为了程序简洁，可以避免高精度乘法，用 09 次循环减法取代得到商的值。这里，我们讨论一下高精 度数除以单精度数的结果，采取的方法是按位相除法。 参考程序： program exam4; const max=200; var a,c:array1.max of 0.9; x,b:longint; n1,n2:string; lena:integer; code,i,j:integer; begin write(Input dividend:); readln(n1); write(Input divisor:); readln(n2); 基础算法教案 第 6 页 共 82 页 lena:=length(n1); for i:=1 to lena do ai := ord(n1i) - ord(0); val(n2,b,code); 按位相除 x:=0; for i:=1 to lena do begin ci:=(x*10+ai) div b; x:=(x*10+ai) mod b; end; 显示商 j:=1; while (cj=0) and (jlena) do inc(j); 去除高位的 0 for i:=j to lena do write(ci) ; writeln end. 实质上，在做两个高精度运算时候，存储高精度数的数组元素可以不仅仅只保留一个数字，而采 取保留多位数（例如一个整型或长整型数据等） ，这样，在做运算（特别是乘法运算）时，可以减少很 多操作次数。例如图 5 就是采用 4 位保存的除法运算，其他运算也类似。具体程序可以修改上述例题 予以解决，程序请读者完成。 第三课 排列与组合 课题：排列与组合 目标： 知识目标：如何利用程序就各种排列和组合 能力目标：排列组合的运用 重点：求出 n 的全排列和从 m 中取 n 个的组合 难点：算法的理解 板书示意： 1） 求全排列的算法 示例： 45 = 1 2345 6789 45 = 274 3484 1 div 45 = 0 ， 1 mod 45=1 取 12345 div 45 = 274 12345 mod 45 = 15 取 div 45 = 3484 答案为, 余数为 mod 45 = 9 图 5 基础算法教案 第 7 页 共 82 页 2） 求组合数的算法 授课过程： 例 5：有 3 个人排成一个队列，问有多少种排对的方法，输出每一种方案？ 分析：如果我们将 3 个人进行编号，分别为 1、2、3，显然我们列出所有的排列， 123，132，213，231，312，321 共六种。可用循环枚举各种情况，参考程序： program exam5; var i,j,k:integer; begin for I:=1 to 3 do for j:=1 to 3 do for k:=1 to 3 do if (i+j+k=6) and (i*j*k=6) then writeln(i,j,k); end. 上述情况非常简单，因为只有 3 个人，但当有 N 个人时怎么办？显然用循环不能解决问题。下面 我们介绍一种求全排列的方法。 设当前排列为 P1 P2 ,Pn，则下一个排列可按如下算法完成： 1求满足关系式 Pj-1 Pj的 J 的最大值，设为 I，即 I=maxj | Pj-1 Pj , j = 2.n 2求满足关系式 Pi -1 Pk的 k 的最大值，设为 j，即 J=maxK | Pi-1 Pk , k = 1.n 3Pi -1与 Pj互换得 (P) = P1 P2 ,Pn 4(P) = P1 P2 , Pi-1 Pi, Pn部分的顺序逆转，得 P1 P2 , Pi-1 Pn Pn-1, Pi便是下 一个排列。 例：设 P1 P2 P3 P4 =3421 1I= maxj | Pj-1 Pj , j = 2.n = 2 2J=maxK | Pi-1 =pi) do dec(i); if i=1 then break; 求满足关系式 Pi -1 0) and (pi-1=pj) do dec(j); if j=0 then break; Pi -1与 Pj互换得 (P) = P1 P2 ,Pm t:=pi-1;pi-1:=pj;pj:=t; Pi, Pm的顺序逆转 for j:=1 to (m-i+1) div 2 do begin t:=pi+j-1;pi+j-1:=pm-j+1;pm-j+1:=t end; 打印当前解 for i:=1 to m do write(pi); inc(count); writeln; until false; writeln(count) End. 例 6：求 N 个人选取 M 个人出来做游戏，共有多少种取法？例如：N=4，M=2 时，有 12，13，14，23，24，34 共六种。 分析：因为组合数跟顺序的选择无关。因此对同一个组合的不同排列，只需取其最小的一个（即 按从小到大排序） 。因此，可以设计如下算法： 1最后一位数最大可达 N，倒数第二位数最大可达 N-1，依此类推，倒数第 K 位数最大可达 N-K+1。 若 R 个元素组合用 C1C2 CR表示，且假定 C1C2 CR, CR=N-R+I, I=1,2,R。 2当存在 CjN-R+J 时，其中下标的最大者设为 I，即 I=maxJ | Cj0) do dec(j);求 I=maxJ | CjN-R+J cj:=cj+1; for i:=j+1 to m do ci:=ci-1+1;建立下一个组合 for i:=1 to m do write(ci);writeln输出 end; End. 第四课 枚举法 课题：枚举法 目标： 知识目标：枚举算法的本质和应用 能力目标：枚举算法的应用！ 重点：利用枚举算法解决实际问题 难点：枚举算法的次数确定 板书示意： 1） 简单枚举（例 7、例 8、例 9） 2） 利用枚举解决逻辑判断问题（例 10、例 11） 3） 枚举解决竞赛问题（例 12、例 13、例 14） 授课过程： 所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的, 哪些是有用的.能使命题成立,即为其解。一般思路： 对命题建立正确的数学模型； 根据命题确定的数学模型中各变量的变化范围（即可能解的范围） ； 基础算法教案 第 10 页 共 82 页 利用循环语句、条件判断语句逐步求解或证明； 枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算 法时可以采用枚举法。 例 7：求满足表达式 A+B=C 的所有整数解，其中 A，B，C 为 13 之间的整数。 分析：本题非常简单，即枚举所有情况，符合表达式即可。算法如下： for A := 1 to 3 do for B := 1 to 3 do for C := 1 to 3 do if A + B = C then Writeln(A, +, B, =, C); 上例采用的就是枚举法。所谓枚举法，指的是从可能的解的集合中一一枚举各元素，用题目给定 的检验条件判定哪些是无用的，哪些是有用的。能使命题成立的，即为解。 从枚举法的定义可以看出，枚举法本质上属于搜索。但与隐式图的搜索有所区别，在采用枚举法 求解的问题时，必须满足两个条件： 预先确定解的个数 n； 对每个解变量 A1，A2，An 的取值，其变化范围需预先确定 A1X11，X1p AiXi1，Xiq AnXn1，Xnk 例 7 中的解变量有 3 个：A，B，C。其中 A 解变量值的可能取值范围 A1，2，3 B 解变量值的可能取值范围 B1，2，3 C 解变量值的可能取值范围 C1，2，3 则问题的可能解有 27 个 （A，B，C）（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，Y 在0，100范 基础算法教案 第 11 页 共 82 页 围内的所有整数解。 分析：要求方程的在一个范围内的解，只要对这个范围内的所有整数点进行枚举，看这些点是否 满足方程即可。参考程序： program exam8; var a,b,c:integer; x,y:integer; begin write(Input a,b,c:);readln(a,b,c); for x:=0 to 100 do for y:=0 to 100 do if a*x+b*y=c then writeln(x, ,y); end. 从上例可以看出，所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件 判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。 例 9 巧妙填数 将 19 这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三 位数是第一行的两倍, 第三行的三位数是第一行的三倍, 应怎样填数。如图 6: 图 6 分析：本题目有 9 个格子，要求填数，如果不考虑问题给出的条件，共有 9！=种方案，在这些方 案中符合问题条件的即为解。因此可以采用枚举法。 但仔细分析问题，显然第一行的数不会超过 400，实际上只要确定第一行的数就可以根据条件算 出其他两行的数了。这样仅需枚举 400 次。因此设计参考程序： program exam9; var i,j,k,s:integer; function sum(s:integer):integer; begin sum:=s div 100 + s div 10 mod 10 + s mod 10 end; function mul(s:integer):longint; 1 9 2 3 8 4 5 7 6 基础算法教案 第 12 页 共 82 页 begin mul:=(s div 100) * (s div 10 mod 10) * (s mod 10) end; begin for i:=1 to 3 do for j:=1 to 9 do if ji then for k:=1 to 9 do if (kj) and (ki) then begin s := i*100 + j*10 +k; 求第一行数 if 3*s1000 then if (sum(s)+sum(2*s)+sum(3*s)=45) and (mul(s)*mul(2*s)*mul(3*s)=) then 满足条件，并数字都由 19 组成 begin writeln(s); writeln(2*s); writeln(3*s); writeln; 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 比较小，因此我们对每种情况进行枚举，然后根据条件判断 哪些符合问题的要求。 根据已知条件，A1,B2,C3,D4,E5,因此排除了一种可能性，只有 4！=24 种情况了。 参考程序： Program Exam10; Var A,B,C,D,E :Integer; Cr :Array1.5 Of Char; 基础算法教案 第 13 页 共 82 页 Begin For A:=1 To 5 Do For B:=1 To 5 Do For C:=1 To 5 Do For D:=1 To 5 Do For E:=1 To 5 Do Begin ABCDE 没猜对一个人的名次 If (A=1) Or (B=2) Or (C=3) Or (D=4) Or (E=5) Then Continue; If A,B,C,D,E1,2,3,4,5 Then Continue;他们名次互不重复 DAECB 猜对了两个人的名次 If Ord(A=2)+Ord(B=5)+Ord(C=4)+Ord(D=1)+Ord(E=3)2 Then Continue; ABCDE 没猜对一对相邻名次 If (B=A+1) Or (C=B+1) Or (D=C+1) Or (E=D+1) Then Continue; DAECB 猜对了两对相邻人名次 If Ord(A=D+1)+Ord(E=A+1)+Ord(C=E+1)+Ord(B=C+1)2 Then Continue; CrA:=A;CrB:=B;CrC:=C; CrD:=D;CrE:=E; WRITELN(CR1, ,CR2, ,CR3, ,CR4, ,CR5); 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) A B C D 程序如下： 基础算法教案 第 14 页 共 82 页 program EXAM11; type Language = (CHN,ENG,FRH,JPN); TNoSet= set of Language; const No: array 1 . 5 of TNoSet= (CHN,ENG, CHN,FRH, CHN,JPN, ENG,FRH, ENG,JPN); var A, B, C, D: 1 . 5; Can1, Can2, Can3, Can4: Boolean; function Might(Lang: Language): Boolean; var Bool: Boolean; begin Bool:=false; if NoA * NoA * NoC = Lang then Bool := True; if NoA * NoB * NoD = Lang then Bool := True; if NoA * NoC * NoD = Lang then Bool := True; if NoB * NoC * NoD = Lang then Bool := True; Might := Bool end; procedure Print(A, B, C, D: Integer); procedure Show(P: Integer; Ch: Char); var I: Integer; Lang: Language; begin Write(ch,:); for Lang := CHN to JPN do 基础算法教案 第 15 页 共 82 页 if Lang in NoP then case Lang of CHN: Write(CHN:5); FRH: Write(FRH:5); JPN: Write(JPN:5); ENG: Write(ENG:5); end; Writeln; end; begin Show(A, A); Show(B, B); Show(C, C); Show(D, D); end; begin for A := 3 to 5 do if A 4 then for B := 2 to 3 do for C := 1 to 5 do for D := 1 to 4 do if D 3 then begin A 和 D 能互相交谈 Can1 := NoA * NoD ; A 和 C 交谈时却要 B 当翻译 Can2 := (NoA * NoC = ) and (NoA * NoB ) and (NoB * NoC ); B,C,D 三个想互相交谈,但找不到共同的语言 Can3 := NoB * NoC * NoD = ; 只有一种语言 3 人都会 Can4 := Ord(Might(CHN) + Ord(Might(ENG) + Ord(Might(FRH) + Ord(Might(JPN) = 1; if Can1 and Can2 and Can3 and Can4 then Print(A,B,C,D); end; end. 例 12 古纸残篇 在一位数学家的藏书中夹有一张古旧的纸片。纸片上的字早已模糊不清了, 只留下曾经写过字的 痕迹, 依稀还可以看出它是一个乘法算式, 如图 7 所示。这个算式上原来的数字是什么呢？夹着这张 基础算法教案 第 16 页 共 82 页 * * * * * * * * * * * * * * * * * * 图 7 纸片的书页上,“素数”两个字被醒目的划了出来。难道说, 这个算式与素数有什么关系吗？有人对此 作了深入的研究, 果然发现这个算式中的每一个数字都是素数, 而且这样的算式是唯一的。请你也研 究一番, 并把这个算式写出来。 分析：实际上，只要知道乘数和被乘数就可以写出乘法算式， 所以我们可以枚举乘数与被乘数的每一位。然后再判断是不是满 足条件即可。计算量是 45=1024，对于计算机来说，计算量非常 小。 参考程序： Program Exam12; Const Su : Array1.4 Of Longint=(2,3,5,7); Var A1,A2,A3,B1,B2,X,Y,S :Longint; Function Kx(S:Longint):Boolean;判断一个数 是不是都是由素数组成 Begin Kx:=True; While S0 Do Begin If Not(S Mod 10) In 2,3,5,7) Then Begin Kx:=False; Exit; End; S:=S Div 10; End; End; Begin For A1:=1 To 4 Do For A2:=1 To 4 Do For A3:=1 To 4 Do For B1:=1 To 4 Do For B2:=1 To 4 Do Begin X:=SuA1*100+SuA2*10+SuA3;X 为被乘数 If X*SuB11000 Then Continue; If X*SuB21000 Then Continue; If X*(SuB1*10+SuB2)10000 Then Continue; 它们分别是两个四位数，一个五位数 If (Kx(X*SuB1)=False) Or (Kx(X*SuB2)=False) Or (Kx(X*(SuB1*10+SuB2)=False) Then Continue; 基础算法教案 第 17 页 共 82 页 满足其他数都是由质数构成 Writeln( ,SuA1,SuA2,SuA3); Writeln(* ,SuB1,SuB2); Writeln(-); Writeln( ,X*SuB2); Writeln( ,X*SuB1); Writeln(-); Writeln( ,X*(SuB1*10+SuB2); End; End. 例 13：时钟问题（IOI94-4） 在图 8 所示的 3*3 矩阵中有 9 个时钟，我们的目标是旋转时钟指针，使所有时钟的指针都指向 12 点。允许旋转时钟指针的方法有 9 种，每一种移动用一个数字号（1，2，9）表示。图 2-11 示出 9 个数字号与相应的受控制的时钟，这些时钟在图中以灰色标出，其指针将顺时针旋转 90 度。 输入数据： 由输入文件 INPUT.TXT 读 9 个数码，这些数码给出了 9 个时钟时针的初始位置。数码与时刻的对 应关系为： 012 点 图 8 九种时钟状态 图 9 九种被控制方式 基础算法教案 第 18 页 共 82 页 13 点 26 点 39 点 图 2-11 中的例子对应下列输入数据： 330 222 212 输出数据： 将一个最短的移动序列（数字序列）写入输出文件 OUTPUT.TXT 中，该序列要使所有的时钟指针指 向 12 点，若有等价的多个解，仅需给出其中一个。在我们的例子中，相应的 OUTPUT.TXT 的内容为： 5849 输入输出示例： INPUT.TXTOUTPUT.TXT 330 222 212 5489 具体的移动方案如图 10 所示。 分析： 首先，我们分析一下表示时钟时针初始位置的数码 j（0j3）与时刻的对应关系： 012 点 13 点 26 点 39 点 每移动一次，时针将顺时针旋转 90 度。由此我们可以得出： 对于任意一个时钟 i（1i9）来说，从初始位置 j 出发至少需要 Ci=（4-j） mod 4 次操作，才 能使得时针指向 12 点。而对每种移动方法要么不采用，要么采用 1 次、2 次或 3 次，因为操作四次以 后，时钟将重复以前状态。因此，9 种旋转方案最多产生 49个状态。 移动方案选取与顺序无关。样例中，最佳移动序列为 5849，同样 4589 序列也可达到目标。因此， 求解过程中可以直接选取序列中从小至大排列的移动序列即可。 设 pi表示第 i 种旋转方法的使用次数（0pi3，1i9） 。 则可能的解的集合为P1，P2，P9，该集合共含 49个状态。从图 2.11 中，我们可以分析出 图 10 示例移动方案 基础算法教案 第 19 页 共 82 页 9 个时钟分别被哪些方法所控制，见下表： 时钟号控制时钟方案检验条件 1 1、2、4 C1=(P1+P2+P4) mod 4 2 1、2、3、5 C2=(P1+P2+P3+P5) mod 4 3 2、3、6 C3=(P2+P3+P6) mod 4 4 1、4、5、7 C4=(P1+P4+P5+P7) mod 4 5 1、3、5、7、9 C5=(P1+P3+P5+P7+P9) mod 4 6 3、5、6、9 C6=(P3+P5+P6+P9) mod 4 7 4、7、8 C7=(P4+P7+P8) mod 4 8 5、7、8、9 C8=(P5+P7+P8+P9) mod 4 9 6、8、9 C9=(P6+P8+P9) mod 4 因此我们可以设计如下枚举算法： for p1:=0 to 3 do for p2:=0 to 3 do . . . for p9:=0 to 3 do if c1 满足时钟 1 and c2 满足时钟 2 and . and c9 满足时钟 9 then 打印解路径； 显然，上述枚举算法枚举了所有 49=个状态，运算量和运行时间颇大。我们可以采取缩小可能解范 围的局部枚举法，仅枚举第 1、2、3 种旋转方法可能取的 43个状态，根据这三种旋转方法的当前状态 值，由下述公式 P4=order(C1-P1-P2); P5=order(C2-P1-P2-P3); P6=order(C3-P2-P3); P7=order(C4-P1-P4-P5); P8=order(C8-P5-PP9); P9=order(C6-P3-P5-P6); 其中 04mod)4( 04mod )( cNc cc corder 得出其余 P4P9的相应状态值。然后将 P1，P2，P9代入下述三个检验条件 C5=(P1+P3+P5+P7+P9) mod 4 C7=(P4+P7+P8) mod 4 C9=(P6+P8+P9) mod 4 一一枚举，以求得确切解。 由此可见，上述局部枚