2014算法大全

1算法详解及练习题目录第一讲穷举法------------------------------1第二讲字符与字符串处理--------------------16第三讲不同进制转换------------------------25第四讲高精度计算--------------------------26第五讲数据排序----------------------------30第六讲约瑟夫问题（纸牌问题）---------------34第七讲矩阵（递推问题）---------------------40第八讲排列组合----------------------------43第九讲贪心算法----------------------------47第十讲递归算法----------------------------56第一讲穷举法一、穷举法的基本概念穷举方法是基于计算机特点而进行解题的思维方法。一般是在一时找不出解决问题的更好途径（即从数学上找不到求解的公式或规则）时，可以根据问题中的的部分条件（约束条件）将所有可能解的情况列举出来，然后通过一一验证是否符合整个问题的求解要求，而得到问题的解。这样解决问题的方法我们称之为穷举算法。穷举算法特点是算法简单，但运行时所花费的时间量大。有些问题所列举出来的情况数目会大得惊人，就是用高速的电子计算机运行，其等待运行结果的时间也将使人无法忍受。因此，我们在用穷举方法解决问题时，应尽可能将明显的不符合条件的情况排除在外，以尽快取得问题的解。二、算法模式问题解的可能搜索的范围：用循环或循环嵌套结构实现，写出符合问题解的条件。能使程序优化的语句，以便缩小搜索范围，减少程序运行时间。三、使用穷举法设计算法例1：百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，大鸡三块钱一只，小鸡一块钱三只，不大不小的鸡两块钱一只。现在，请你编一程序，帮他计划一下，怎么样买法，才能刚好用一百块钱买一百只鸡？算法分析：此题很显然是用枚举法，我们以三种鸡的个数为枚举对象（分别设为x,y,z）,以三种鸡的总数（x+y+z）和买鸡用去的钱的总数(x*3+y*2+z)为判定条件，穷举各种鸡的个数。下面是解这个百鸡问题的程序varx,y,z:integer;2beginforx:=0to100dofory:=0to100doforz:=0to100do{枚举所有可能的解}if(x+y+z=100)and(x*3+y*2+zdiv3=100)and(zmod3=0)thenwriteln('x=',x,'y=',y,'z=',z);{验证可能的解，并输出符合题目要求的解}end.上面的条件还有优化的空间，三种鸡的和是固定的，我们只要枚举二种鸡（x,y），第三种鸡就可以根据约束条件求得（z=100-x-y），这样就缩小了枚举范围，请看下面的程序：varx,y,z:integer;beginforx:=0to100dofory:=0to100-xdobeginz:=100-x-y;if(x*3+y*2+zdiv3=100)and(zmod3=0)thenwriteln('x=',x,'y=',y,'z=',z);end;end.未经优化的程序循环了1013次，时间复杂度为O(n3)；优化后的程序只循环了（102*101/2）次，时间复杂度为O(n2)。从上面的对比可以看出，对于枚举算法，加强约束条件，缩小枚举的范围，是程序优化的主要考虑方向。在枚举算法中，枚举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的枚举对象可以获得更高的效率。如下例：例2、将1,2...9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,试求出所有满足条件的三个三位数.例如:三个三位数192,384,576满足以上条件.(NOIP1998pj)算法分析：这是1998年全国分区联赛普及组试题（简称NOIP1998pj，以下同）。此题数据规模不大，可以进行枚举，如果我们不加思地以每一个数位为枚举对象，一位一位地去枚举：fora:=1to9doforb:=1to9do………fori:=1to9do这样下去，枚举次数就有99次，如果我们分别设三个数为x,2x,3x，以x为枚举对象，穷举的范围就减少为93，在细节上再进一步优化，枚举范围就更少了。程序如下：var3t,x:integer;s,st:string;c:char;beginforx:=123to329do{枚举所有可能的解}begint:=0;str(x,st);{把整数x转化为字符串，存放在st中}str(x*2,s);st:=st+s;str(x*3,s);st:=st+s;forc:='1'to'9'do{枚举9个字符，判断是否都在st中}ifpos(c,st)0theninc(t)elsebreak;{如果不在st中，则退出循环}ift=9thenwriteln(x,'',x*2,'',x*3);end;end.在枚举法解题中，判定条件的确定也是很重要的，如果约束条件不对或者不全面，就穷举不出正确的结果，我们再看看下面的例子。例3：古希腊人认为因子的和等于它本身的数是一个完全数（自身因子除外），例如28的因子是1、2、4、7、14，且1+2+4+7+14=28，则28是一个完全数，编写一个程序求2～1000内的所有完全数。分析：本题是一个搜索问题，搜索范围2～1000，找出该范围内的完全数；完全数必须满足的条件：因子的和等于该数据的本身。问题关键在于将该数的因子一一寻找出来，并求出因子的和。程序如下：Programp3_1;Vara,b,s:integer;BeginFora:=2to1000doBegins:=0;Forb:=1toa-1doIfamodb=0thens:=s+b;{分解因子并求和}Ifa=sthenbeginWrite(a,‘=’,1,);｛打印a=1｝Forb:=2toa-1doIfamodb=0thenwrite(’+’,b);｛打印加法式子｝Writeln;End;End;End.4当程序运行后，输出结果：6=1+2+328=1+2+4+7+14496=1+2+4+8+16+31+62+124+248例4：（第七届全国青少年信息学(计算机)奥林匹克分区联赛初赛试题）在A，B两个城市之间设有N个路站(如下图中的S1，且N100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数≤20，且每条路段上的距离均为一个整数)。A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，…最后到达B。通路上路段距离之和称为通路距离(最大距离≤1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。例如：上图所示是当N=1时的情况：从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。算法说明：本题采用穷举算法。数据结构：（1）N：记录A，B间路站的个数；（2）数组D(I，0)记录第I-1到第I路站间路段的个数；（3）D(I，1)，D(I，2)，…记录每个路段距离；（4）数组G记录可取到的距离。PROGRAMCHU7_6；VARI，J，N，S：INTEGER；B：ARRAY[0..100]OFINTEGER；D：ARRAY[0..100，0..20]OFINTEGER；G：ARRAY[0..1000]OF0..1；BEGINREADLN(N)；FORI:=1TON+1DOBEGINREADLN(D[I，0])；FORJ:=1TOD[I，0]DOREADLN(D[I，J])；END；D[0，0]:=1；FORI:=1TON+1DOB[I]:=1；B[0]:=0；FORI:=0TO1000DOG[I]:=0；WHILE①DOBEGIN5S:=0；FORI:=1TON+1DOS:=②G[S]:=1；J:=N+1；WHILE③DOJ:=J-1；B[J]:=B[J]+1；FORI:=J+1TON+1DOB[I]:=1；END；S:=0；FORI:=1TO1000DO④；WRITELN(S)；READLN；END.答案：①B[0]=0②S+D[I,B[I]];③B[J]=D[J,0]④S:=S+G[I]例5（第八届全国青少年信息学奥林匹克联赛(NOIP2002)试题）将n个整数分成k组(k≤n,要求每组不能为空),显然这k个部分均可得到一个各自的和s1,s2,……sk,定义整数P为:P=(S1-S2)2+(S1一S3)2+……+(S1-Sk)2+(s2-s3)2+……+(Sk-1-Sk)2问题求解:求出一种分法,使P为最小(若有多种方案仅记一种)程序说明:数组:a[1],a[2],...A[N]存放原数s[1],s[2],...,s[K]存放每个部分的和b[1],b[2],...,b[N]穷举用临时空间d[1],d[2],...,d[N]存放最佳方案程序:programexp4;Vari,j,n,k:integer;a:array[1..100]ofinteger;b,d:array[0..100]ofinteger;s:array[1..30]ofinteger;beginreadln(n,k);forI:=1tondoread(a[I]);forI:=0tondob[I]:=1;cmin:=1000000;while(b[0]=1)dobeginforI:=1tokdo①6forI:=1tondo②sum:=0;forI:=1tok-1doforj:=③sum:=sum+(s[I]-s[j])*(s[I]-s[j]);if④thenbegincmin:=sum;forI:=1tondod[I]:=b[I];end;j:=n;while⑤doj:=j-1;b[j]:=b[j]+1;forI:=j+1tondo⑥end;writeln(cmin);forI:=1tondowrite(d[I]:40);writeln;end.四、穷举算法的深入应用实例一：一根29厘米长的尺子,只允许在上面刻七个刻度,要能用它量出1～29厘米的各种长度。试问这根尺的刻度应该怎样选择?分析：(1)从1～29厘米中选择七个刻度的所有可能情况数是:C(7,29)=29·28·27·26·25·24·23/1·2·3·4·5·6·7=29·9·26·5·2·23=29·26·23·90=1560780(2)对于每一组刻度的选择都需要判断是否能将1～29厘米的各种刻度量出来,例如选择的刻度为:a1,a2,a3,a4,a5a,6,a7那么能量出的刻度为：a1,29-a1;2a2,a2-a1,29-a2;3a3,a3-a1,a3-a2,29-a3;4a4,a4-a1,a4-a2,a4-a3,29-a4;5a5,a5-a1,a5-a2,a5-a3,a5-a4,29-a5;6a6,a6-a1,a6-a2,a6-a3,a6-a4,a6-a5,29-a6;7a7-a1,a7-a2,a7-a2,a7-a3,a7-a4,a7-a5,a7-a6,29-a7;8共可量出2+3+4+5+6+7+8种刻度,即35种刻度,事实上其中有许多刻度是重复的,不可能复盖1～29。例如：取a1,a2,a3,a4,a5,a6,a7为1,3,6,10,15,21,28能量出的刻度为：1,2873,2,266,5,3,2310,9,7,4,1915,14,12,9,5,1421,20,18,15,11,6,828,27,25,22,18,13,7,1缺16,17,24(29即尺子长度)如果找出了刻度a1,a2,a3,a4,a5,a6,a7那么我们可以利用其对称性29-a1,29-a2,29-a3,29-a4,29-a5,29-a6,29-a7,也是一组解,所以求解过程中可仅考虑a1a2a3a4a5a6a7的情况。很显然要使1,28两种刻度能量出来,则在七个刻度就必须有1或28;这样