信息学奥赛基础算法教案

第页基础算法教案目录TOC\o"1-1"\h\z\u第一课算法简介 1第二课多精度数值处理 1第三课排列与组合 6第四课枚举法 9第五课递归与回溯法 25第六课递推法 42第七课贪心法 50第八课分治法 64第九课模拟法 70习题 79第一课算法简介算法是一组（有限个）规则，它为某个特定问题供应了解决问题的运算序列。在信息学竞赛中，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写算法，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。计算机解题的核心是算法设计。一个算法应当具有以下五个重要特征：有穷性：一个算法必需能在执行有限步之后结束；准确性：算法的每一步骤必需准确定义；输入：一个算法有零个或多个输入，以描述运算对象的初始状况。所谓0个输入是指算法本身给出了初始条件；输出：一个算法有一个或多个输出，以反映对输入数据处理后的结果。没有输出的算法是毫无意义的；可行性：算法原则上能够精确的运行，而且其运算规模是可以承受的。为了获得一个既有效又优美的算法，必需首先了解一些基本的常用算法设计思路。下面，我们就对构成算法所依据的一些基本方法绽开探讨，如递推法，递归法，枚举法，分治法，模拟法，贪心法等。第二课多精度数值处理课题：多精度数值的处理目标：知识目标：多精度值的加,减,乘,除实力目标：多精度值的处理，优化！重点：多精度的加,减,乘难点：进位及借位处理板书示意：输入两个正整数，求它们的和输入两个正整数，求它们的差输入两个正整数，求它们的积输入两个正整数，求它们的商授课过程：所谓多精度值处理，就是在对给定的数据范围，用语言本身供应的数据类型无法直接进行处理（主要指加减乘除运算），而须要采纳特殊的处理方法进行。看看下面的例子。例1从键盘读入两个正整数，求它们的和。分析：从键盘读入两个数到两个变量中，然后用赋值语句求它们的和，输出。但是，我们知道，在pascal语言中任何数据类型都有肯定的表示范围。而当两个被加数据大时，上述算法明显不能求出精确解，因此我们须要寻求另外一种方法。在读小学时，我们做加法都采纳竖式方法，如图1。这样，我们便利写出两个整数相加的算法。856+2551111图1A3856+2551111图1A3A2A1+B3B2B1C4C3C2C1图2A[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;begini:=1while(i<=a数组长度>0)or(i<=b数组的长度)dobeginx:=a[i]+b[i]+xdiv10;{第i位相加并加上次的进位}c[i]:=xmod10;{存储第i位的值}i:=i+1{位置指针变量}endend;通常，读入的两个整数用可用字符串来存储，程序设计如下：programexam1;constmax=200;vara,b,c:array[1..max]of0..9;n:string;lena,lenb,lenc,i,x:integer;beginwrite('Inputaugend:');readln(n);lena:=length(n);{加数放入a数组}fori:=1tolenadoa[lena-i+1]:=ord(n[i])-ord('0');write('Inputaddend:');readln(n);lenb:=length(n);{被加数放入b数组}fori:=1tolenbdob[lenb-i+1]:=ord(n[i])-ord('0');i:=1;while(i<=lena)or(i<=lenb)dobeginx:=a[i]+b[i]+xdiv10;{两数相加，然后加前次进位}c[i]:=xmod10;{保存第i位的值}i:=i+1end;ifx>=10then{处理最高进位}beginlenc:=i;c[i]:=1endelselenc:=i-1;fori:=lencdownto1dowrite(c[i]);{输出结果}writelnend.例2高精度减法。从键盘读入两个正整数，求它们的差。 分析：类似加法，可以用竖式求减法。在做减法运算时，须要留意的是：被减数必需比减数大，同时须要处理借位。因此，可以写出如下关系式ifa[i]<b[i]thenbegina[i+1]:=a[i+1]-1;a[i]:=a[i]+10endc[i]:=a[i]-b[i]类似，高精度减法的参考程序：programexam2;constmax=200;vara,b,c:array[1..max]of0..9;n,n1,n2:string;lena,lenb,lenc,i,x:integer;beginwrite('Inputminuend:');readln(n1);write('Inputsubtrahend:');readln(n2);{处理被减数和减数}if(length(n1)<length(n2))or(length(n1)=length(n2))and(n1<n2)thenbeginn:=n1;n1:=n2;n2:=n;write('-'){n1<n2,结果为负数}end;lena:=length(n1);lenb:=length(n2);fori:=1tolenadoa[lena-i+1]:=ord(n1[i])-ord('0');fori:=1tolenbdob[lenb-i+1]:=ord(n2[i])-ord('0');i:=1;while(i<=lena)or(i<=lenb)dobeginx:=a[i]-b[i]+10+x;{不考虑大小问题，先往高位借10}c[i]:=xmod10;{保存第i位的值}x:=xdiv10-1;{将高位借掉的1减去}i:=i+1end;lenc:=i;while(c[lenc]=0)and(lenc>1)dodec(lenc);{最高位的0不输出}fori:=lencdownto1dowrite(c[i]);writelnend.例3高精度乘法。从键盘读入两个正整数，求它们的积。 分析：类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进乘法运算时，必需进行错位相加，如图3,图4。856×25856×254280171221400图3A3A2A1×B3B2B1C’4C’3C’2C’1C”5C”4C”3C”2C6C5C4C3C2C1图4Ci=C’i+C”i+…由此可见，Ci跟A[i]*B[j]乘积有关，跟上次的进位有关，还跟原Ci的值有关，分析下标规律，有x:=A[i]*B[j]+xDIV10+C[i+j-1];C[i+j-1]:=xmod10;类似，高精度乘法的参考程序：programexam3;constmax=200;vara,b,c:array[1..max]of0..9;n1,n2:string;lena,lenb,lenc,i,j,x:integer;beginwrite('Inputmultiplier:');readln(n1);write('Inputmultiplicand:');readln(n2);lena:=length(n1);lenb:=length(n2);fori:=1tolenadoa[lena-i+1]:=ord(n1[i])-ord('0');fori:=1tolenbdob[lenb-i+1]:=ord(n2[i])-ord('0');fori:=1tolenadobeginx:=0; forj:=1tolenbdobegin{对乘数的每一位进行处理}x:=a[i]*b[j]+xdiv10+c[i+j-1];{当前乘积+上次乘积进位+原数}c[i+j-1]:=xmod10;end;c[i+j]:=xdiv10;{进位}end;lenc:=i+j;while(c[lenc]=0)and(lenc>1)dodec(lenc);fori:=lencdownto1dowrite(c[i]);writelnend.例４高精度除法。从键盘读入两个正整数，求它们的商（做整除）。 分析：做除法时，每一次上商的值都在０～９，每次求得的余数连接以后的若干位得到新的被除数，接着做除法。因此，在做高精度除法时，要涉及到乘法运算和减法运算，还有移位处理。当然，为了程序简洁，可以避开高精度乘法，用0～9次循环减法取代得到商的值。这里，我们探讨一下高精度数除以单精度数的结果，实行的方法是按位相除法。 参考程序： programexam4;constmax=200;vara,c:array[1..max]of0..9;x,b:longint;n1,n2:string;lena:integer;code,i,j:integer;beginwrite('Inputdividend:');readln(n1);write('Inputdivisor:');readln(n2);lena:=length(n1);fori:=1tolenadoa[i]:=ord(n1[i])-ord('0');val(n2,b,code); {按位相除}x:=0;fori:=1tolenadobeginc[i]:=(x*10+a[i])divb;x:=(x*10+a[i])modb;end; {显示商}j:=1;while(c[j]=0)and(j<lena)doinc(j);{去除高位的0}fori:=jtolenadowrite(c[i]);writelnend.实质上，在做两个高精度运算时候，存储高精度数的数组元素可以不仅仅只保留一个数字，而实行保留多位数（例如一个整型或长整型数据等），这样，在做运算（特殊是乘法运算）时，可以减少许多操作次数。例如图5就是采纳4位保存的除法运算，其他运算也类似。详细程序可以修改上述例题予以解决，程序请读者完成。示例：123456789÷45=1’示例：123456789÷45=1’2345’6789÷45=274’3484∵1div45=0，1mod45=1∴取12345div45=274∵12345mod45=15∴取156789div45=3484∴答案为2743484,余数为156789mod45=9图5第三课排列及组合课题：排列及组合目标：知识目标：如何利用程序就各种排列和组合实力目标：排列组合的运用重点：求出n的全排列和从m中取n个的组合难点：算法的理解板书示意：求全排列的算法求组合数的算法授课过程：例5：有3个人排成一个队列，问有多少种排对的方法，输出每一种方案？分析：假如我们将3个人进行编号，分别为1,2,3，明显我们列出全部的排列，123，132，213，231，312，321共六种。可用循环枚举各种状况，参考程序：programexam5;var i,j,k:integer;begin forI:=1to3doforj:=1to3do fork:=1to3doif(i+j+k=6)and(i*j*k=6)thenwriteln(i,j,k);end.上述状况特别简单，因为只有3个人，但当有N个人时怎么办？明显用循环不能解决问题。下面我们介绍一种求全排列的方法。设当前排列为P1P2,…,Pn，则下一个排列可按如下算法完成：1．求满足关系式Pj-1<Pj的J的最大值，设为I，即I=max{j|Pj-1<Pj,j=2..n}2．求满足关系式Pi-1<Pk的k的最大值，设为j，即J=max{K|Pi-1<Pk,k=1..n}3．Pi-1及Pj互换得(P)=P1P2,…,Pn4．(P)=P1P2,…,Pi-1Pi,…,Pn部分的顺序逆转，得P1P2,…,Pi-1PnPn-1,…,Pi便是下一个排列。例：设P1P2P3P4=34211．I=max{j|Pj-1<Pj,j=2..n}=22．J=max{K|Pi-1<Pk,k=1..n}=23．P1及P2交换得到43214．4321的321部分逆转得到4123即是3421的下一个排列。程序设计如下：programexam5;constmaxn=100;vari,j,m,t:integer;p:array[1..maxn]ofinteger;count:integer;{排列数目统计变量}beginwrite('m:');readln(m);fori:=1tomdobeginp[i]:=i;write(i)end;writeln;count:=1;repeat{求满足关系式Pj-1<Pj的J的最大值，设为I}i:=m;while(i>1)and(p[i-1]>=p[i])dodec(i);ifi=1thenbreak; {求满足关系式Pi-1<Pk的k的最大值，设为j}j:=m;while(j>0)and(p[i-1]>=p[j])dodec(j);ifj=0thenbreak; {Pi-1及Pj互换得(P)=P1P2,…,Pm}t:=p[i-1];p[i-1]:=p[j];p[j]:=t;{Pi,…,Pm的顺序逆转}forj:=1to(m-i+1)div2dobegint:=p[i+j-1];p[i+j-1]:=p[m-j+1];p[m-j+1]:=tend;{打印当前解}fori:=1tomdowrite(p[i]);inc(count);writeln;untilfalse;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表示，且假定C1<C2<…<CR,CR<=N-R+I,I=1,2,…,R。2．当存在Cj<N-R+J时，其中下标的最大者设为I，即 I=max{J|Cj<N-R+J}，则作Ci:=Ci+1,及之对应的操作有Ci+1:=Ci+1，Ci+2:=Ci+1+1，….，CR:=CR-1+1参考程序：programexam6;constmaxn=10;vari,j,n,m:integer;c:array[1..maxn]ofinteger; {c数组记录当前组合}BeginWrite('n&m:');readln(n,m);fori:=1tomdobegin {初始化，建立第一个组合}c[i]:=i;write(c[i]);end;writeln;whilec[1]<n-m+1dobeginj:=m;while(c[j]>n-m+1)and(j>0)dodec(j); {求I=max{J|Cj<N-R+J}}c[j]:=c[j]+1;fori:=j+1tomdoc[i]:=c[i-1]+1; {建立下一个组合}fori:=1tomdowrite(c[i]);writeln {输出}end;End.第四课枚举法课题：枚举法目标：知识目标：枚举算法的本质和应用实力目标：枚举算法的应用！重点：利用枚举算法解决实际问题难点：枚举算法的次数确定板书示意：简单枚举（例7,例8,例9）利用枚举解决逻辑推断问题（例10,例11）枚举解决竞赛问题（例12,例13,例14）授课过程：所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。一般思路：对命题建立正确的数学模型；依据命题确定的数学模型中各变量的变化范围（即可能解的范围）；利用循环语句,条件推断语句逐步求解或证明；枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时可以采纳枚举法。例7：求满足表达式A+B=C的全部整数解，其中A，B，C为1~3之间的整数。分析：本题特别简单，即枚举全部状况，符合表达式即可。算法如下：forA:=1to3doforB:=1to3doforC:=1to3doifA+B=CthenWriteln(A,‘+’,B,‘=’,C);上例采纳的就是枚举法。所谓枚举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立的，即为解。从枚举法的定义可以看出，枚举法本质上属于搜寻。但及隐式图的搜寻有所区分，在采纳枚举法求解的问题时，必需满足两个条件：预先确定解的个数n；对每个解变量A1，A2，……，An的取值，其变化范围需预先确定A1∈{X11，……，X1p}Ai∈{Xi1，……，Xiq}An∈{Xn1，……，Xnk}例7中的解变量有3个：A，B，C。其中A解变量值的可能取值范围A∈{1，2，3}B解变量值的可能取值范围B∈{1，2，3}C解变量值的可能取值范围C∈{1，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]范围内的全部整数解。 分析：要求方程的在一个范围内的解，只要对这个范围内的全部整数点进行枚举，看这些点是否满足方程即可。参考程序：programexam8;vara,b,c:integer;x,y:integer;beginwrite('Inputa,b,c:');readln(a,b,c);forx:=0to100dofory:=0to100doifa*x+b*y=cthenwriteln(x,'',y);end.从上例可以看出，所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。例9奇妙填数192384576将1～9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。假如要使第二行的三位数是第一行的两倍,第三行的三位数是第一行的三倍,应怎样填数。如图6:图6分析：本题目有9个格子，要求填数，假如不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采纳枚举法。但细致分析问题，明显第一行的数不会超过400，事实上只要确定第一行的数就可以依据条件算出其他两行的数了。这样仅需枚举400次。因此设计参考程序：programexam9;vari,j,k,s:integer;functionsum(s:integer):integer;beginsum:=sdiv100+sdiv10mod10+smod10end;functionmul(s:integer):longint;beginmul:=(sdiv100)*(sdiv10mod10)*(smod10)end;beginfori:=1to3doforj:=1to9doifj<>ithenfork:=1to9doif(k<>j)and(k<>i)thenbegins:=i*100+j*10+k;{求第一行数}if3*s<1000thenif(sum(s)+sum(2*s)+sum(3*s)=45)and(mul(s)*mul(2*s)*mul(3*s)=362880)then{满足条件，并数字都由1~9组成}beginwriteln(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比较小，因此我们对每种状况进行枚举，然后依据条件推断哪些符合问题的要求。依据已知条件，A<>1,B<>2,C<>3,D<>4,E<>5,因此解除了一种可能性，只有4！=24种状况了。参考程序：ProgramExam10;VarA,B,C,D,E:Integer;Cr:Array[1..5]OfChar;BeginForA:=1To5DoForB:=1To5DoForC:=1To5DoForD:=1To5DoForE:=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)<>2ThenContinue;{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)<>2ThenContinue;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)A×××B×××CD××程序如下：programEXAM11;typeLanguage=(CHN,ENG,FRH,JPN);TNoSet=setofLanguage;constNo:array[1..5]ofTNoSet=([CHN,ENG],[CHN,FRH],[CHN,JPN],[ENG,FRH],[ENG,JPN]);varA,B,C,D:1..5;Can1,Can2,Can3,Can4:Boolean;functionMight(Lang:Language):Boolean;varBool:Boolean;beginBool:=false;ifNo[A]*No[A]*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:=Boolend;procedurePrint(A,B,C,D:Integer);procedureShow(P:Integer;Ch:Char);varI:Integer;Lang:Language;beginWrite(ch,':');forLang:=CHNtoJPNdoifLanginNo[P]thencaseLangofCHN:Write('CHN':5);FRH:Write('FRH':5);JPN:Write('JPN':5);ENG:Write('ENG':5);end;Writeln;end;beginShow(A,'A');Show(B,'B');Show(C,'C');Show(D,'D');end;beginforA:=3to5doifA<>4thenforB:=2to3doforC:=1to5doforD:=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;ifCan1andCan2andCan3andCan4thenPrint(A,B,C,D);end;end.例12古纸残篇在一位数学家的藏书中夹有一张古旧的纸片。纸片上的字早已模糊不清了,只留下曾经写过字的痕迹,依稀还可以看出它是一个乘法算式,如图7所示。这个算式上原来的数字是什么呢？夹着这张纸片的书页上,“素数”两个字被醒目的划了出来。莫非说,这个算式及素数有什么关系吗？有人对此作了深入的探讨,果真发觉这个算式中的每一个数字都是***×***************图7素数,***×***************图7分析：事实上，只要知道乘数和被乘数就可以写出乘法算式，所以我们可以枚举乘数及被乘数的每一位。然后再推断是不是满足条件即可。计算量是45=1024，对于计算机来说，计算量特别小。参考程序：ProgramExam12;ConstSu:Array[1..4]OfLongint=(2,3,5,7);VarA1,A2,A3,B1,B2,X,Y,S:Longint;FunctionKx(S:Longint):Boolean;{推断一个数是不是都是由素数组成}BeginKx:=True;WhileS<>0DoBeginIfNot((SMod10)In[2,3,5,7])ThenBeginKx:=False;Exit;End;S:=SDiv10;End;End;BeginForA1:=1To4DoForA2:=1To4DoForA3:=1To4DoForB1:=1To4DoForB2:=1To4DoBeginX:=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]))=False)ThenContinue;{满足其他数都是由质数构成}Writeln('',Su[A1],Su[A2],Su[A3]);Writeln('*',Su[B1],Su[B2]);Writeln('');Writeln('',X*Su[B2]);Writeln('',X*Su[B1]);Writeln('');Writeln('',X*(Su[B1]*10+Su[B2]));End;End.例13：时钟问题（IOI94-4）在图8所示的3*3矩阵中有9个时钟，我们的目标是旋转时钟指针，使全部时钟的指针都指向12点。允许旋转时钟指针的方法有9种，每一种移动用一个数字号（1，2，…，9）表示。图2-11示出9个数字号及相应的受限制的时钟，这些时钟在图中以灰色标出，其指针将顺时针旋转90度。图8九种时钟状态图9九种被图8九种时钟状态图9九种被限制方式由输入文件INPUT.TXT读9个数码，这些数码给出了9个时钟时针的初始位置。数码及时刻的对应关系为：0——12点1——3点2——6点3——9点图2-11中的例子对应下列输入数据：330222212输出数据：将一个最短的移动序列（数字序列）写入输出文件OUTPUT.TXT中，该序列要使全部的时钟指针指向12点，若有等价的多个解，仅需给出其中一个。在我们的例子中，相应的OUTPUT.TXT的内容为：5849输入输出示例：INPUT.TXTOUTPUT.TXT3302222125489详细的移动方案如图10所示。图10示例移动方案分析：图10示例移动方案首先，我们分析一下表示时钟时针初始位置的数码j（0≦j≦3）及时刻的对应关系：0——12点1——3点2——6点3——9点每移动一次，时针将顺时针旋转90度。由此我们可以得出：对于随意一个时钟i（1≦i≦9）来说，从初始位置j动身至少须要Ci=（4-j）mod4次操作，才能使得时针指向12点。而对每种移动方法要么不采纳，要么采纳1次,2次或3次，因为操作四次以后，时钟将重复以前状态。因此，9种旋转方案最多产生49个状态。移动方案选取及顺序无关。样例中，最佳移动序列为5849，同样4589序列也可达到目标。因此，求解过程中可以直接选取序列中从小至大排列的移动序列即可。设pi表示第i种旋转方法的运用次数（0≦pi≦3，1≦i≦9）。则可能的解的集合为{P1，P2，……，P9}，该集合共含49个状态。从图2.11中，我们可以分析出9个时钟分别被哪些方法所限制，见下表：时钟号限制时钟方案检验条件11,2,4C1=(P1+P2+P4)mod421,2,3,5C2=(P1+P2+P3+P5)mod432,3,6C3=(P2+P3+P6)mod441,4,5,7C4=(P1+P4+P5+P7)mod451,3,5,7,9C5=(P1+P3+P5+P7+P9)mod463,5,6,9C6=(P3+P5+P6+P9)mod474,7,8C7=(P4+P7+P8)mod485,7,8,9C8=(P5+P7+P8+P9)mod496,8,9C9=(P6+P8+P9)mod4因此我们可以设计如下枚举算法：forp1:=0to3do forp2:=0to3doforp9:=0to3do ifc1满足时钟1andc2满足时钟2and...andc9满足时钟9then打印解路径；明显，上述枚举算法枚举了全部49=262144个状态，运算量和运行时间颇大。我们可以实行缩小可能解范围的局部枚举法，仅枚举第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);其中得出其余P4……P9的相应状态值。然后将P1，P2，…，P9代入下述三个检验条件C5=(P1+P3+P5+P7+P9)mod4C7=(P4+P7+P8)mod4C9=(P6+P8+P9)mod4一一枚举，以求得准确解。由此可见，上述局部枚举的方法（枚举状态数为43个）比较全部枚举的方法（枚举状态数为49个）来说，由于大幅度削减了枚举量，减少运算次数，因此其时效显著改善，是一种优化了的算法。程序如下：programIOI94_4;constInp='input.txt';Outp='output.txt';varClock,Map:array[1..3,1..3]ofInteger;{Clock：第((I+2)mod3)*3+J个时钟从初始时间到12点的最少移动次数}{Map:最短移动序列中，数字（（I+2）mod3）*3+J的次数}procedureInit;varI,J:Integer;beginAssign(Input,Inp);Reset(Input);forI:=1to3do{读入9个时钟指针的初始位置，求出每个时钟从初始到12点的最少移动次数}forJ:=1to3dobeginRead(Clock[I,J]);Clock[I,J]:=(4-Clock[I,J])mod4;end;Close(Input);end;functionOrder(K:Integer):Integer;varc:Integer;begin c:=k; whilec<0doinc(c,4);whilec>4thendec(c,4);Order:=k;end;procedureMain; {计算和输出最短移动序列}varI,J,K:Integer;begin{枚举最短移动序列中数字1,2,3的个数可能取的43种状态}Assign(Output,Outp);Rewrite(Output);forMap[1,1]:=0to3doforMap[1,2]:=0to3doforMap[1,3]:=0to3dobeginMap[2,1]:=Order(Clock[1,1]-Map[1,1]-Map[1,2]);Map[2,3]:=Order(Clock[1,3]-Map[1,2]-Map[1,3]);Map[2,2]:=Order(Clock[1,2]-Map[1,1]-Map[1,2]-Map[1,3]);Map[3,1]:=Order(Clock[2,1]-Map[1,1]-Map[2,1]-Map[2,2]);Map[3,3]:=Order(Clock[2,3]-Map[1,3]-Map[2,2]-Map[2,3]);Map[3,2]:=Order(Clock[3,2]-Map[3,1]-Map[3,3]-Map[2,2]);{依据数字1,2,3个数的当前值，得出数字4~9的个数}if((Map[2,1]+Map[3,1]+Map[3,2])mod4=Clock[3,1])and((Map[2,3]+Map[3,2]+Map[3,3])mod4=Clock[3,3])and((Map[2,2]+Map[1,1]+Map[1,3]+Map[3,1]+Map[3,3])mod4=Clock[2,2])thenbegin{若数字4~9的个数满足检验条件，则输出方案}forI:=1to3doforJ:=1to3doforK:=1toMap[I,J]doWrite((I-1)*3+J);Exit; {找到一个解后退出}end;end;Writeln('NoAnswer!');Close(Output);end;beginInit; Main; end.在上例中，由于事先能够解除那些明显不属于解集的元素，使得算法效率特别高。而减少重复运算,力求提前计算所需数据,运用恰当的数据结构进行算法优化等方法也是优化枚举算法的常用手段。例14：最佳巡游线路（NOI94）某旅游区的街道成网格状（图2.13）。其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道，游客在旅游街上只能从西向东走，在林阴道上则既可从南向北走，也可以从北向南走。阿龙想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示全部旅游街相邻两个路口之间的街道值得巡游的程度，分值时从-100到100的整数，全部林阴道不打分。全部分值不可能全是负分。图11某旅游区街道示例图例如图11是被打过分的某旅游区的街道图：图11某旅游区街道示例图阿龙可以从任一个路口开始巡游，在任一个路口结束巡游。请你写一个程序，帮忙阿龙找一条最佳的巡游线路，使得这条线路的全部分值总和最大。输入数据：输入文件是INPUT.TXT。文件的第一行是两个整数M和N，之间用一个空格符隔开，M表示有多少条旅游街（1≦M≦100），N表示有多少条林阴道（1≦M≦20001）。接下来的M行依次给出了由北向南每条旅游街的分值信息。每行有N-1个整数，依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。输出数据：输出文件是OUTPUT.TXT。文件只有一行，是一个整数，表示你的程序找到的最佳巡游线路的总分值。输入输出示例：INPUT.TXTOUTPUT.TXT36-50–4736–30–2317–19–34–13–8-42–3–4334–4584分析：设Lij为第I条旅游街上自西向东第J段的分值（1≦I≦M，1≦J≦N–1）。例如样例中L12=17，L23=-34，L34=34。我们将网格状的旅游区街道以林荫道为界分为N–1个段，每一段由M条旅游街的对应段成，即第J段成为{L1J，L2J，……，LMJ}（1≦J≦N–1）。由于巡游方向规定横向自西向东，纵向即可沿林阴道由南向北，亦可由北向南，而横行的街段有分值，纵行无分值，因此最佳巡游路现必需具备如下三个特征：来自若干个连续的段，每一个段中取一个分值；每一个分值是所在段中最大的；起点段和终点段随意，但途经段的分值和最大。设Li为第I个段中的分值最大的段。即Li=Max{L1I，L2I，……，LMI}（1≦I≦N–1）。例如对于样例数据：L1=Max（-50，17，-42）=17；L2=Max（-47，-19，-3）=-3；L3=Max（36，-34，-43）=36；L4=Max（-30，-13，34）=34；L5=Max（-23，-8，-45）=-8；有了以上的基础，我们便可以通过图示描述解题过程，见图12。图12求解过程示例图我们把将段设为顶点，所在段的最大分值设为顶点的权，各顶点按自西向东的顺序相连，组成一条巡游路线。明显，假如确定西端为起点,东段为终点，则这条巡游路线的总分值最大。图12求解过程示例图问题是某些段的最大分值可能是负值，而最优巡游路线的起点和终点随意，在这种状况下，上述巡游路线就不肯定最佳了。因此，我们只能枚举这条巡游路线的全部可能的子路线，从中找出一条子路线II+1……J（1≦I<J≦N–1），使得经过顶点的权和LI+LI+1+……+LJ最大。设Best为最佳巡游路线的总分值，初始时为0；Sum为当前巡游路线的总分值。我们可以得到如下算法：Best:=0;Sum:=0;forI:=1toN–2doforJ:=I+1toN–1dobeginSum:=LI+……+LJ;ifSum>BestthenBest:=Sum;end明显，这个算法的时间困难度为O（N2）。而N在1~20001之间，时间困难度比较高。于是，我们必需对这个算法进行优化。仍旧从顶点1开始枚举最优路线。若当前子路线延长至顶点I时发觉总分值Sum≦0，则应放弃当前子路线。因为无论LI+1为何值，当前子路线延长至顶点I+1后的总分值不会大于LI+1。因此应当从顶点I+1开始重新考虑新的一条子路线。通过这种优化，可以使得算法的时间困难度降到了O（N）。优化后的算法描述如下:Best:=0;Sum:=0;forI:=1toN–1dobeginSum:=Sum+LI;ifSum>BestthenBest:=Sum;ifSum<0thenSum:=0;end程序描述如下：{$R-,S-,Q-}{$M65520,0,655360}programNoi94;constMaxN=20001; {林阴道数的上限}Inp='input.txt';Outp='output.txt';varM,N:Word; {旅游街数和林阴道数}Best:Longint; {最佳巡游路线的总分值}Score:array[1..MaxN]ofShortInt; {描述每个段的最大分值}procedureInit;varI,J,K:Integer;Buffer:array[1..40960]ofChar; {文件缓冲区}beginAssign(Input,Inp);Reset(Input);SetTextBuf(Input,Buffer); {开拓文件缓冲区}Readln(M,N); {读入旅游街数和林阴道数}FillChar(Score,Sizeof(Score),$80); {初始化各段的最大分值}forI:=1toMdo {计算1~N–1段的最大分值}forJ:=1toN-1dobeginRead(K);ifK>Score[J]thenScore[J]:=K;end;Close(Input); end;procedureOut;beginAssign(Output,Outp);Rewrite(Output);Writeln(Best);Close(Output);end;procedureMain;varI:Integer;Sum:Longint; {当前巡游路线的总分值}begin{最佳巡游路线的总分值和当前巡游路线的总分值初始化}Best:=0;Sum:=0;forI:=1toN-1dobegin {顺序枚举巡游路线的总分值}Inc(Sum,Score[I]); {统计当前巡游路线的总分值}ifSum>BestthenBest:=Sum; {若当前最佳，则登记}ifSum<0thenSum:=0;{若总分值<0，则考虑一条新路线}end;end;beginInit; {输入数据}Main; {主过程}Out; {输出}end.第五课递归及回溯法课题：递归及回溯目标：知识目标：递归概念及利用递归进行回溯实力目标：回溯算法的应用重点：回溯算法难点：回溯算法的理解板书示意：递归的理解利用递归回溯解决实际问题（例14,例15,例16,例17,例18）利用回溯算法解决排列问题（例19）授课过程：什么是递归？先看大家都熟识的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说……。象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之是递归。例如，我们可以这样定义N!，N!=N*(N-1)!，因此求N!转化为求(N-1)!。这就是一个递归的描述。因此，可以编写如下递归程序：programFactorial;varN:Integer;T:Longint;functionFac(N:Integer):Longint;beginifN=0thenFac:=1elseFac:=N*Fac(N-1)end;beginWrite('N=');Readln(N);T:=Fac(N);Writeln('N!=',T);end.图13图13递归调用示例图设一个未知函数f，用其自身构成的已知函数g来定义：为了定义f(n)，必需先定义f(n-1)，为了定义f(n-1)，又必需先定义f(n-2)，…，上述这种用自身的简单状况来定义自己的方式称为递归定义。递归有如下特点： ①它直接或间接的调用了自己。 ②肯定要有递归终止的条件，这个条件通常称为边界条件。及递推一样，每一个递推都有其边界条件。但不同的是，递推是由边界条件动身，通过递推式求f(n)的值，从边界到求解的全过程特别清晰；而递归则是从函数自身动身来达到边界条件，在通过边界条件的递归调用过程中，系统用堆栈把每次调用的中间结果（局部变量和返回地址）保存起来，直至求出递归边界值f(0)=a。然后返回调用函数。返回的过程中，中间结果相继出栈复原，f(1)=g(1,a)f(2)=g(2,f(1))……直至求出f(n)=g(n,f(n-1))。递归按其调用方式分直接递归——递归过程P直接自己调用自己；间接递归——即P包含另一过程D，而D又调用P；由此可见，递归算法的效率往往很低，费时和费内存空间。但是递归也有其特长，它能使一个蕴含递归关系且结构困难的程序简洁精炼，增加可读性。特殊是在难于找到从边界到解的全过程的状况下，假如把问题进一步，其结果仍维持原问题的关系，则采纳递归按其调用方式分直接递归——递归过程P直接自己调用自己；间接递归——即P包含另一过程D，而D又调用P；递归算法适用的一般场合为：①数据的定义形式按递归定义。如裴波那契数列的定义：对应的递归程序为functionfib(n:Integer):Integer;beginifn=0thenfib:=1 {递归边界}elseifn=1thenfib:=2 {递归边界}elsefib:=fib(n–2)+fib(n–1); {递归}end;这类递归问题可转化为递推算法，递归边界为递推的边界条件。例如上例转化为递推算法即为functionfib(n:Integer):Integer;beginf[0]:=1;f[1]:=2; {递推边界}forI:=2tondof[I]:=f[I–1]+f[I–2];fib:=f(n);end;②数据之间的关系（即数据结构）按递归定义。如树的遍历，图的搜寻等。③问题解法按递归算法实现。例如回溯法等。对于②和③，可以用堆栈结构将其转换为非递归算法，以提高算法的效率以及减少内存空间的奢侈。下面以经典的N皇后问题为例，看看递归法是怎样实现的，以及比较递归算法和非递归算法效率上的差别。例15：N皇后问题图14八皇后的两组解在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解全部的摆放方法。图14八皇后的两组解分析：由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行摸索和订正，这就是“回溯”的思想。在N个皇后未放置完成前，摆放第I个皇后和第I+1个皇后的摸索方法是相同的，因此完全可以采纳递归的方法来处理。下面是放置第I个皇后的的递归算法：ProcedureTry(I:integer)；{搜寻第I行皇后的位置}var j:integer;beginifI=n+1then输出方案；forj:=1tondo if皇后能放在第I行第J列的位置thenbegin放置第I个皇后；对放置皇后的位置进行标记；Try（I+1）对放置皇后的位置释放标记； End;End;N皇后问题的递归算法的程序如下：programN_Queens;constMaxN=100; {最多皇后数}varA:array[1..MaxN]ofBoolean; {竖线被限制标记}B:array[2..MaxN*2]ofBoolean; {左上到右下斜线被限制标记}C:array[1–MaxN..MaxN–1]ofBoolean;{左下到右上斜线被限制标记}X:array[1..MaxN]ofInteger; {记录皇后的解}Total:Longint; {解的总数}N:Integer; {皇后个数}procedureOut; {输出方案}varI:Integer;beginInc(Total);Write(Total:3,‘:’);forI:=1toNdoWrite(X[I]:3);Writeln;end;procedureTry(I:Integer); {搜寻第I个皇后的可行位置}varJ:Integer;beginifI=N+1thenOut;{N个皇后都放置完毕，则输出解}forJ:=1toNdoifA[J]andB[J+I]andC[J–I]thenbeginX[I]:=J;A[J]:=False;B[J+I]:=False;C[J–I]:=False;Try(I+1); {搜寻下一皇后的位置}A[J]:=True;B[J+I]:=True;C[J–I]:=True;end;end;beginWrite(‘QueensNumbers=‘);Readln(N);FillChar(A,Sizeof(A),True);FillChar(B,Sizeof(B),True);FillChar(C,Sizeof(C),True);Try(1);Writeln(‘Total=‘,Total);end.N皇后问题的非递归算法的程序：programN_Queens;constMaxN=100; {最多皇后数}varA:array[1..MaxN]ofBoolean; {竖线被限制标记}B:array[2..MaxN*2]ofBoolean; {左上到右下斜线被限制标记}C:array[1–MaxN..MaxN–1]ofBoolean;{左下到右上斜线被限制标记}X:array[1..MaxN]ofInteger; {记录皇后的解}Total:Longint; {解的总数}N:Integer; {皇后个数procedureOut; {输出方案}varI:Integer;beginInc(Total);Write(Total:3,‘:’);forI:=1toNdoWrite(X[I]:3);Writeln;end;procedureMain; varK:Integer;beginX[1]:=0;K:=1;whileK>0dobeginifX[K]<>0thenbeginA[X[K]]:=True;B[X[K]+K]:=True;C[X[K]–K]:=True;end;Inc(X[K]);while(X[K]<=N)andnot(A[X[K]]andB[X[K]+K]andC[X[K]–K])doInc(X[K]); {找寻一个可以放置的位置}ifX[K]<=NthenifK=NthenOutelsebeginA[X[K]]:=False;B[X[K]+K]:=False;C[X[K]–K]:=False;Inc(K);X[K]:=0; {接着放置下一个皇后}endelseDec(K); {回溯}end;end;beginWrite(‘QueensNumber=‘);Readln(N);FillChar(A,Sizeof(A),True);FillChar(B,Sizeof(B),True);FillChar(C,SizeofI,True);Main;Writeln(‘Total=‘,Total);end.运用递归可以使蕴含困难关系的问题，结构变得简洁精炼。看看下面的例题。例16:新汉诺（hanoi）塔问题设有n各大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘随意的迭套在三根立柱上，立柱的编号分别为A,B,C，这个状态称之为初始状态。问题要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。移动时有如下要求：一次只移动一个盘；不允许把大盘移到小盘上边；输入：输入文件第1行是状态中圆盘总数；第2~4行是分别是初始状态中A,B,C柱上的圆盘个数和从上到下每个圆盘的编号；第5~7行是分别是目标状态A,B,C柱上的圆盘个数和从上到下每个圆盘的编号。输出：每行写一步的移动方案，格式为：MoveI圆盘formP柱toQ柱。最终输出最少步数。输入样例（如图）：6312324516061234560样例所描述的状态如图15所示。图15样例图图15样例图输出样例：分析：要