《信息学奥赛基础算法教案.doc》由会员分享，可在线阅读，更多相关《信息学奥赛基础算法教案.doc（389页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date信息学奥赛基础算法教案第一课 算法简介基础算法教案 目录第一课 算法简介1第二课 多精度数值处理1第三课 排列与组合6第四课 枚举法9第五课 递归与回溯法25第六课 递推法42第七课 贪心法50第八课 分治法64第九课 模拟法70习题79第一课 算法简介算法是一组（有限个）规则，它为某个特定问题提供了解决问题的运算序列。在信息学竞赛中，就是计算机解题的过程。在这个过程
2、中，无论是形成解题思路还是编写算法，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。计算机解题的核心是算法设计。一个算法应该具有以下五个重要特征： 有穷性：一个算法必须能在执行有限步之后结束； 确切性：算法的每一步骤必须确切定义； 输入：一个算法有零个或多个输入，以描述运算对象的初始情况。所谓0个输入是指算法本身给出了初始条件； 输出：一个算法有一个或多个输出，以反映对输入数据处理后的结果。没有输出的算法是毫无意义的； 可行性：算法原则上能够精确的运行，而且其运算规模是可以承受的。为了获得一个既有效又优美的算法，必须首先了解一些基本的常用算法设计思路。下面，我们就对构成算法所依
3、据的一些基本方法展开讨论，如递推法，递归法，枚举法，分治法，模拟法，贪心法等。第二课 多精度数值处理课题：多精度数值的处理目标：知识目标：多精度值的加、减、乘、除能力目标：多精度值的处理，优化！重点：多精度的加、减、乘难点：进位与借位处理板书示意：1） 输入两个正整数，求它们的和2） 输入两个正整数，求它们的差3） 输入两个正整数，求它们的积4） 输入两个正整数，求它们的商授课过程：所谓多精度值处理，就是在对给定的数据范围，用语言本身提供的数据类型无法直接进行处理（主要指加减乘除运算），而需要采用特殊的处理办法进行。看看下面的例子。例1 从键盘读入两个正整数，求它们的和。分析：从键盘读入两个数
4、到两个变量中，然后用赋值语句求它们的和，输出。但是，我们知道，在pascal语言中任何数据类型都有一定的表示范围。而当两个被加数据大时，上述算法显然不能求出精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，如图1。这样，我们方便写出两个整数相加的算法。 8 5 6 + 2 5 5 1 1 1 1 图1 A3 A2 A1+ B3 B2 B1 C4 C3 C2 C1 图2如果我们用数组A、B分别存储加数和被加数，用数组C存储结果。则上例有A1=6, A2=5, A3=8, B1=5,B2=5, B3=2, C4=1,C3=1, C2=1,C1=1,两数相加如图2所示。由上
5、图可以看出：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 beginx := ai + bi + x div 10; 第i位相加并加上次的进位ci := x mod 10; 存储第i位的值i := i + 1 位置指针变量 endend;通常，读入的两个整数用可用字符串来存储，程
6、序设计如下：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:
7、=ord(ni)-ord(0); i:=1; 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); 输出结果 writelnend.例2 高精度减法。从键盘读入两个正整数，求它们的差。分析：类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大，同时需要处理借位。因此，可以写出如下关系式if aibi then begin ai+1:=ai+1-1;ai:=ai+10 endci:=ai-bi类似，高精度减法的
8、参考程序：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
9、,结果为负数 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); i:=1; while (i=lena) or(i1) do dec(lenc); 最高位的0不输出 for i:=lenc downto 1 do write(ci); writelnend.例3 高精度乘法。从键盘读入两个正整数，求它们的积。分析：类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同
10、时对每一位进乘法运算时，必须进行错位相加，如图3, 图4。 8 5 6 2 5 4 2 8 0 1 7 1 2 2 1 4 0 0 图3A 3 A 2 A 1 B 3 B 2 B 1 C4C3 C2 C1 C”5C”4C”3C”2 C 6 C 5 C 4 C 3 C 2 C 1 图4分析C数组下标的变化规律，可以写出如下关系式C i = C i +C ”i +由此可见，C i跟Ai*Bj乘积有关，跟上次的进位有关，还跟原C i的值有关，分析下标规律，有x:= Ai*Bj+ x DIV 10+ Ci+j-1;Ci+j-1 := x mod 10; 类似，高精度乘法的参考程序：program ex
11、am3;const max=200;var a,b,c:array1.max of 0.9; n1,n2:string; lena,lenb,lenc,i,j,x:integer;begin write(Input multiplier:); readln(n1); write(Input multiplicand:); readln(n2); 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)-or
12、d(0); for i:=1 to lena do begin x:=0; for j:=1 to lenb do begin 对乘数的每一位进行处理 x := ai*bj + x div 10 + ci+j-1; 当前乘积+上次乘积进位+原数 ci+j-1 := x mod 10; end; ci+j:= x div 10; 进位 end; lenc:=i+j; while (clenc=0) and (lenc1) do dec(lenc); for i:=lenc downto 1 do write(ci); writelnend.例 高精度除法。从键盘读入两个正整数，求它们的商（做整除
13、）。分析：做除法时，每一次上商的值都在，每次求得的余数连接以后的若干位得到新的被除数，继续做除法。因此，在做高精度除法时，要涉及到乘法运算和减法运算，还有移位处理。当然，为了程序简洁，可以避免高精度乘法，用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:);
14、 readln(n1); write(Input divisor:); readln(n2); 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) ; write
15、lnend.实质上，在做两个高精度运算时候，存储高精度数的数组元素可以不仅仅只保留一个数字，而采取保留多位数（例如一个整型或长整型数据等），这样，在做运算（特别是乘法运算）时，可以减少很多操作次数。例如图5就是采用4位保存的除法运算，其他运算也类似。具体程序可以修改上述例题予以解决，程序请读者完成。示例：123456789 45 = 1 2345 6789 45= 274 3484 1 div 45 = 0 ， 1 mod 45=1 取12345 div 45 = 274 12345 mod 45 = 15 取156789 div 45 = 3484 答案为2743484, 余数为156789
16、 mod 45 = 9图5 第三课 排列与组合课题：排列与组合目标：知识目标：如何利用程序就各种排列和组合 能力目标：排列组合的运用重点：求出n的全排列和从m中取n个的组合难点：算法的理解板书示意：1） 求全排列的算法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
17、 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.n2求满足关系式Pi -1 Pk的k的最大值，设为j，即J=maxK | Pi-1 Pk , k = 1.n3Pi -1与Pj互换得 (P) = P1 P2 ,Pn4(P
18、) = P1 P2 , Pi-1 Pi, Pn部分的顺序逆转，得P1 P2 , Pi-1 Pn Pn-1, Pi便是下一个排列。例：设P1 P2 P3 P4 =34211I= maxj | Pj-1 Pj , j = 2.n = 22J=maxK | Pi-1 Pk , k =1.n = 23P1与P2交换得到432144321的321部分逆转得到4123即是3421的下一个排列。程序设计如下：program exam5;const maxn = 100;var i,j,m,t : integer; p : array1.maxn of integer; count :integer; 排列数
19、目统计变量begin write(m:);readln(m); for i:=1 to m do begin pi:=i; write(i) end; writeln; count:=1; repeat求满足关系式Pj-1 1) and (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)
20、 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
21、位数最大可达N-K+1。若R个元素组合用C1C2 CR表示，且假定C1C2 CR, CR=N-R+I, I=1,2,R。2当存在CjN-R+J时，其中下标的最大者设为I，即I=maxJ | CjN-R+J，则作Ci := Ci +1,与之对应的操作有Ci+1 := Ci +1 ，Ci+2 := Ci +1+1 ，. ，CR := CR-1 +1参考程序：program exam6;const maxn=10;var i,j,n,m :integer; c :array1.maxnof integer; c数组记录当前组合BeginWrite(n & m:); readln(n,m); for
22、i:=1 to m do begin初始化，建立第一个组合 ci:=i; write(ci); end; writeln; while c1n-m+1) and ( j0) 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
23、）2） 利用枚举解决逻辑判断问题（例10、例11）3） 枚举解决竞赛问题（例12、例13、例14）授课过程：所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。一般思路：l 对命题建立正确的数学模型；l 根据命题确定的数学模型中各变量的变化范围（即可能解的范围）；l 利用循环语句、条件判断语句逐步求解或证明；枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法。例7：求满足表达式A+B=C的所有整数解，其中A，B，C为13之间的整数。分析：本题非常简单，即枚举所有情况，符
24、合表达式即可。算法如下：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，X1pAiXi1，Xi
25、qAnXn1，Xnk例7中的解变量有3个：A，B，C。其中A解变量值的可能取值范围A1，2，3B解变量值的可能取值范围B1，2，3C解变量值的可能取值范围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）在上述可能解集合中，满足题目给定的检验条件的解元素，即为问题的解。如果我们无法预先确定解的个数或各解的值域，则不能用枚举，只能采用搜索等算法求解。由于回溯法在搜索每个可能解的枚举次数一般不止一次，因此，对于同样规模的问题，回溯算法要比枚举法时间复杂度稍
26、高。例8 给定一个二元一次方程aX+bY=c。从键盘输入a,b,c的数值，求X在0，100，Y在0，100范围内的所有整数解。分析：要求方程的在一个范围内的解，只要对这个范围内的所有整数点进行枚举，看这些点是否满足方程即可。参考程序：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.从上例可以看出，所谓枚举法,指的是从可能的解
27、集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。例9 巧妙填数 1 9 2 3 8 4 5 7 6 将19这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍, 第三行的三位数是第一行的三倍, 应怎样填数。如图6: 图6分析：本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。因此设计参考程序
28、： 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 10end;function mul(s:integer):longint;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) the
29、n 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)=362880) 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 就是这些人的
30、第一至第五名的名次排列, 便大错。因为:没猜对任何一个优胜者的名次。也没猜对任何一对名次相邻的学生。条件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 :
31、Integer; Cr :Array1.5 Of Char;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 BeginABCDE没猜对一个人的名次 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)+Or
32、d(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在一起交谈,他们只会中、英、法、日四种语言
33、中的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不会日语,
34、 所以D只可能等于1、2、4；B不会英语，所以B只可能等于2、3；见下表。如果我们对A、B、C、D分别进行枚举，根据判定条件，即可找到答案。(CHN,ENG)(CHN,FRH)(CHN,JPN)( ENG,FRH)( ENG,JPN)ABCD程序如下：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
35、. 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; Mig
36、ht := 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 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; beg
37、in 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人