基本算法设计专题.doc

六 基本算法设计专题【热点难点赛点】近几年普及组的竞赛中，经常有试题考查我们基本算法的掌握程度，如果我们对于一些基本的算法在平时训练不够或一知半解，竞赛中肯定会成为自己的绊脚石。信息学竞赛中，其主要任务是设计一个好的算法，去求解所给出的问题。而求解所给出问题，其核心算法是一个基本的算法，但要把设计出这个算法来，除核心算法外，还有若干基本算法辅助而成。我们在寻求解决实际问题的算法（解决问题的方法和步骤）时，需要用到一些基本算法模型，如简单的枚举归纳、分治、递推和递归以及贪心算法等，我们应力求掌握这些基本算法的基本思想的同时，将这些算法思想应用到具体的程序设计中去，并创造性地设计解决问题的算法。【解题方法例析】1、一位农民到市场上去买鸡，但他只带了100元钱，可他想买100只鸡。他问卖鸡的人：“鸡多少钱一只？”卖鸡的人说：“一只公鸡值元，一只母鸡值元，只小鸡值元”。可这位农民书读的少，想了很长时间也没有想出一种用100元钱买100只鸡的方法，由是他请你帮他想出一种买鸡的方案，用一百元要买一百只鸡。问有多少方案，并全部输出来？解析：本题是要求用100元买100只鸡，对于这个问题，只能用枚举法。我们可以用三重循环，来枚举每一种可能的方案，这样，我们要运算1030301次。仔细分析，我们知道公鸡最多可以买20只，母鸡最多可以买33只，小鸡的只数，可以根据总数减去公鸡与母鸡的只数得到，这样，我们只要两重循环，最多714次循环，就可以得出方案。完整的参考程序如下：Const fno=OUTPUT.TXT; Var i,j,k:integer;I代表公鸡的只数；j代表母鸡的只数；k代表小鸡的只数 f2:text; Begin assign(f2,fno); rewrite(f2); for i:=0 to 20 do公鸡的只数 for j:=0 to (100-5*i) div 3 do begin母鸡的只数 k:=(100-5*i-3*j)*3;小鸡的只数 if i+j+k=100 then判断是否用100元正好买了100只鸡 writeln(f2,i, ,j, ,k);输出方案 end; close(f2); End.2、将1，29共9个数分成三组,分别组成三个三位数，且使这三个三位数构成1:2:3的比例，试求出所有满足条件的三个三位数。例如:三个三位数192，384，576满足以上条件。解析：本题只要穷举123到329之间的所有三位数I，如果I、I*2、I*3这三个数中包含的9个数字刚好是1到9则输出I、I*2、I*3。为了记录1到9这9个数字在I、I*2、I*3中是否出现过，程序中用一个一维布尔型数组C。完整的参考程序如下： Const fno=OUTPUT.TXT; Var i,j,k,now:integer; suc:boolean; f2:text; c:array1.9 of boolean;记录1到9这9个数是否出现过 Begin assign(f2,fno); rewrite(f2); for i:=123 to 329 do begin fillchar(c,sizeof(c),0);给数组C赋初值为假 suc:=true;判断1到9是否全部出现的标志量，开始赋初值为真 for j:=1 to 3 do begin now:=i*j; for k:=1 to 3 do begin if (cnow mod 10) or (now mod 10=0) then begin判断是否1到9之间的数重复出现及是否有零出现 suc:=false; 标志量赋值为假，当前的数不符合条件break; end; cnow mod 10:=true;标记出现的数 now:=now div 10; end; end; if suc then writeln(f2,i, ,i*2, ,i*3);输出找到符合要求的这组数， end; close(f2); End.解析归纳：枚举就是一个一个地列举。 应用到程序中，枚举有许多表现形式，比如把所有的组合都扫描一遍，找出符合要求的组合。可以这么说，枚举是最简单，最基础，也是最没效率的算法。但是，枚举拥有很多优点，以致于他能够活到现在而不被淘汰。首先，枚举有超级无敌准确性，只要时间足够，正确的枚举得出的结论是绝对正确的。其次，枚举拥有天下第一全面性，因为它是对所有方案的全面搜索，所以，它能够得出所有的解。可是由于他的运算量相对较大，我们应该注意尽可能地限制一些无谓运算的出现。3、排序是计算机科学中一个常见任务。有一种特殊的排序，最多只有3个关键字。例如，试图对信息学竞赛的奖牌榜排序时，就只有3个关键字，所有的金牌获得者在最前面，随后是银牌获得者，最后是铜牌获得者。 本题中用1，2，3分别表示3个关键字，需将它们按升序排列。排序是通过一系列对换操作实现的。一次操作可以交换两个数的位置。子任务A：请写一个程序，对于一个给定的只含有关键字的序列，计算最少需要几次对换操作就可以将其按升序排列。子任务B：输出一种最少次数的对换方案。输入数据：文件名INPUT.TXT，第一行是序列的长度N（），随后N行，每一行有一个关键字。输出数据：文件名OUTPUT.TXT，第一行是你的程序计算出的所需最少次数L（子任务A）。随后L行是具体的操作方案（子任务B），每一行有两个数P和Q（以一个空格分隔），表示此次操作将第P个数和第Q个数交换。输入输出样例：Input.txtOutput.txt61 1 2 3 2 314 5解析：这道题是排序，却无法用我们所学的简单排序方法来完成，因为它要求交换次数最少。同时，因为序列长度有1000，也不能用枚举搜索的方法去完成。注意到本题中的排序要求，排序元素只有1、2、3三种数字，似乎很简单。1在最前，那么如果序列中有N1个1，那么1要交换到前N1位；同理，如有N2个2，那么2就应该在第N1+1N1+N2位之间。因此，如果1在前N1位那么则不需要交换，否则肯定要交换1次，将不在前N1位的数与在前N1位的不是1的数交换，这样每交换一次就能将一个数换到它应在的位置。但是，还有可能是两个数的位置正好可以互换后使得两数都回到原位，那么在交换时就应该优先将满足两两互换原则的数先进行交换，剩下的再进行单个到位的交换，这样就能保证所用次数最少了。我们通过对一些小数据的模拟，按我们上述归纳出来的办法进行交换确实是正确的，因此只要按原则进行交换就可以了。但由于题设需要输出具体的交换方案，因此，我们需要利用一个10002的整型数组来记录每一次的交换方案，题目的实现就不再困难。完整的参考程序如下： Const fni=Input.txt; fno=Output.txt; Var n,tot:integer; a:array1.1000 of byte; t:array1.3 of integer; w:array1.1000,1.2 of integer;用于记录交换方案 Procedure Init;初始化数据 var f1:text; i:integer; begin assign(f1,fni); reset(f1); readln(f1,n); fillchar(t,sizeof(t),0); for i:=1 to n do begin read(f1,ai); inc(tai); end; close(f1); inc(t2,t1); inc(t3,t2); end; Procedure Exchange1(v1,s1,t1,v2,s2,t2:integer);交换过程 var x:byte; begin while (s1=t1) and (s2=t2) do if as1v2 then inc(s1) else if as2v1 then inc(s2) else begin inc(tot); wtot,1:=s1; wtot,2:=s2; x:=as1; as1:=as2; as2:=x; end; end; Procedure Exchange2(v,s1,t1:integer); var s2,i,x:integer; begin s2:=t1+1; for i:=s1 to t1 do if aiv then begin while (s2=n) and (as2v) do inc(s2); inc(tot); wtot,1:=i; wtot,2:=s2; x:=ai; ai:=as2; as2:=x; end; end; Procedure Main;主过程 var i:integer; f2:text; begin tot:=0; Exchange1(1,1,t1,2,t1+1,t2); Exchange1(1,1,t1,3,t2+1,t3); Exchange1(2,t1+1,t2,3,t2+1,t3); Exchange2(1,1,t1); Exchange2(2,t1+1,t2); assign(f2,fno); rewrite(f2); writeln(f2,tot); for i:=1 to tot do writeln(f2,wi,1, ,wi,2); close(f2); end; Begin主程序 Init; Main; End.程序结束4、有一栋楼，共有N级楼梯，某人每步可以走1级楼梯，也可以走2级楼梯，问他从底层开始走完全部楼梯，总共有多少种不同的走法？输入输出样例：Input.txtOutput.txt58解析：这道题是非常典型的组合数学的题目，也是著名的菲布拉契数列（0，1，1，2，3，5，8，）的一种延伸的表现形式。旨在考查学生的递推能力和面对问题求解的思维能力。我们具体地来分析N比较小的情况。当N=1时，只有1种走法，即一次走1级；当N=2时，有2种走法，一种是一次走1级，另一种是一次走2级；当N=3时，有3种走法，一种是每一步都只走1级，第二种是先走1级，然后再走2级，第三种是先走2级，然后再走1级，以次类推，可得N=4时，有5种走法，N=5时，有8种走法，。由此可得到一个推导公式：F(n)=F(n-1)+F(n-2)。完整的递推参考程序如下：Const fni=INPUT.TXT; fno=OUTPUT.TXT; Var n,i:integer; a1,a2,a3:longint; f1,f2:text; Begin assign(f1,fni); reset(f1); readln(f1,n);读入楼梯的级数 close(f1); a1:=0; a2:=1;给分界数据赋初值 for i:=1 to n do begin a3:=a1+a2;计算N级楼梯的走法 a1:=a2; a2:=a3;记录当前N及N-1级楼梯的走法 end; assign(f2,fno); rewrite(f2); writeln(f2,a3); close(f2); End.此题也还可以用递归的思想来做。完整的递归参考程序如下：Const fni=INPUT.TXT; fno=OUTPUT.TXT; Var n,i:integer; f1,f2:text; Function Solve(m:integer):longint;递归过程 begin if m=P）条直线的基础上，再加上一条直线，最多可以与K条直线相交，而每次相交都会增加一个区域。与最后一条直线相交后，由于直线可以无限延伸，还会再增加一个区域。所以Fm=Fm-1+m(mp)，边界条件在前面已经计算过了，是Fp=2P。完整的参考程序如下： Const fni=INPUT.TXT; fno=OUTPUT.TXT; Var n,p,total,i:longint; f1,f2:text; Begin assign(f1,fni); reset(f1); readln(f1,n,p); close(f1); total:=P*2;边界数据 for I:=P+1 to N do inc(total,I);计算区域个数 assign(f2,fno); rewrite(f2); writeln(f2,total); close(f2); End.6、N个有区别的球放到M个相同的盒子中，要求无一空盒，其不同的方案数总共有多少种？输入：文件只有一行，且只有两个数，第一个数是N，第二个数是M。输出：文件只有一行，即方案的总数。输入输出样例：Input.txtOutput.txt4 27解析：这是第二类Stirling数，是五类典型的递推关系中的一种。根据题义，我们设这N个不同的球，分别用a1，a2，an表示。从中取出一个球an，an的放法有以下两种：an独自占一个盒子，那么剩下的球只能放在M-1个盒子中，方案数为S（N-1，M-1）。an与别的球共占一个盒子，那么可以事先将a1，a2，an-1这N-1个球放入M个盒子中，然后再将球an放入其中一个盒子中，方案数为MS（N-1，M）。综合以上两种情况，可以得出第二类Stirling数公式：S（N，M）= S（N-1，M-1）+ MS（N-1，M） （N1，M=1）边界条件：S（N，0）=0； S（N，1）=1； S（N，N）=1；S（N，M）=0 （MN）。根据以上分析，我们用两个数组来存储计算的结果，a1保存的是N-1个球放到1，2，M-1，M个盒子的方案总数，a2保存的通过递推公式a2j:=a1j-1+a1j*j计算后N个球放到1，2，M-1，M个盒子的方案总数。完整的参考程序如下：Const fni=INPUT.TXT; fno=OUTPUT.TXT; Var a1,a2:array0.100 of longint;记录方案数数组 n,m,i,j:integer; f1,f2:text; Function Min(x,y:integer):integer;比较大小 begin if xy then min:=x else min:=y; end; Begin assign(f1,fni); reset(f1); readln(f1,n,m); close(f1); fillchar(a2,sizeof(a2),0);给a2数组赋初值为0 a21:=1; for i:=2 to n do begin a1:=a2;把a2的值赋给a1 fillchar(a2,sizeof(a2),0); for j:=1 to min(m,i) do a2j:=a1j-1+a1j*j;递推公式 end; assign(f2,fno); rewrite(f2); writeln(f2,a2m); close(f2); End.解析归纳：递推关系共有五种类型，在这里讲到了菲布拉契数列、平面分割问题和第二类Stirling数，还有Hanoi塔问题及Catalan数没有讲到。递推是迭代算法中一种用若干步可重复的简单运算来描述复杂问题的方法，以便于计算机进行处理。它由边界条件开始往后逐个推算，在一般情况下，效率较高，编程也非常的方法。但是，我们一般只需要求递推关系的第N项，而边界条件与条N项前面之间的若干项的信息是我们不需要的。 7、对于给定的整数N（N0时，N！=N（N-1）！。假设用函数JC(N)表示N的阶乘，当N=4时，JC（4）的求解解方法可表示为：JC（4）=4*JC（3）=4*3*JC（2）=4*3*2*JC（1）=4*3*2*1*JC（0）=4*3*2*1*1=24根据上述定义方式和求解方法，完整的参考程序如下：Const fni=INPUT.TXT; fno=OUTPUT.TXT; Var n:integer; f1,f2:text; s:longint; Function JC(n:integer):longint;递归过程 begin if n=0 then jc:=1 else jc:=n*jc(n-1); end; Begin assign(f1,fni); reset(f1); readln(f1,n); close(f1); s:=jc(n);递归调用 assign(f2,fno); rewrite(f2); writeln(f2,s); close(f2); End.解析归纳：递归的过程实际上是借助于一个递归工作栈来实现的，它是由递推和回归两个过程组成。尽管随着N的增大，递归工作栈的变化情况将变得更复杂，而事补，我们并不需要人工考虑递归工作栈的具体工作情况。一般来讲，采用递归方法编写的问题解决程序具有结构清晰、可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些。所以当问题本身是递归定义的，或者问题所涉及的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。递归方法必须满足下列三个条件：可以把问题转化为一个新问题，而这个新问题的解决方法仍与原问题的解法相同；只是所处理的对象不同，但它们只是存在有规律的递增或递减。可以通过转化过程问题得到解决。必定要有一个明确的结束递归的条件，否则递归将会无止境地进行下去，也就是讲必须要有某个终止递归的条件。8、已知一个容量大小为M重量的背包和N种物品，每种物品的重量为Wi。若将物品放入背包将得到Pi的价值，求怎样选取物品（物品可分割）将得到收益最大？输入：文件只有三行，第一行有两个数，第一个数是M，即容量大小，第二个数是N，即物品的种数；第二行有N个数，即每一种物品的重量；第三行有N个数，即每一种物品放入背包将得到的价值。输出：文件只有一行，即收益的最大值（保留两位小数）。输入输出样例：Input.txtOutput.txt10 82 2 2 2 2 2 2 21 2 3 4 5 6 7 830.00解析：因为每一个物品都可以分割成单位块，单位块的价值越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。方法如下：我们用一个记录数组来记录物品的重量、价值、物品编号及每单位的价值，然后将单位块收益按从大到小进行排序，再用循环从单位块收益最大的取起，真到背包装满为止便得到了最优解。完整的参考程序如下：Const fni=input.txt; fno=output.txt; Type Tnode=record w,p,a:integer;w表示物品的重量，p表示物品的价值，a表示物品的编号 d:real;d表示物品单位块的价值 end; Var a:array1.1000 of Tnode;记录数级，存储物品的总数 m,n:integer; Procedure Init;初始化数据 var f1:text; i:integer; begin assign(f1,fni); reset(f1); readln(f1,m,n); for i:=1 to n do read(f1,ai.w); readln(f1); for i:=1 to n do read(f1,ai.p); close(f1); for i:=1 to n do with ai do begin a:=i; d:=p/w;计算单位块的收益 end; end; Procedure Main;主过程 var i,j:integer; ans:real;背包的总收益 x:Tnode; f2:text; begin for i:=1 to n-1 do从大到小排序过程 for j:=i+1 to n do if ai.daj.d then begin x:=ai; ai:=aj; aj:=x; end;排序结束 ans:=0; assign(f2,fno); rewrite(f2); for i:=1 to n do if ai.w0 then begin inc(tot,a5); 直接把a5的个数加入总数 t:=a1-11*a5;箱子剩余空间 if t0 then begin inc(tot,a4); 直接把a4的个数加入总数 t:=a2-a4*5; 剩余22的盒子数 if t=t then a1:=a1-t else a1:=0; end else a2:=t; end; if a30 then begin case a3 mod 4 of一个箱子最多装4个33的盒子，所以分4种情况 0:inc(tot,a3 div 4); 1:begin inc(tot,a3 div 4+1); t:=a2-5;剩余22的盒子数 if t=t then a1:=a1-t else a1:=0; end else begin a2:=t; if a1=7 then a1:=a1-7 else a1:=0; end; end; 2:begin inc(tot,a3 div 4+1); t:=a2-3; 剩余22的盒子数 if t=t then a1:=a1-t else a1:=0; end else begin a2:=t; t:=a1-6; if t=0 then a1:=t else a1:=0; end; end; 3:begin inc(tot,a3 div 4+1); t:=a2-1; 剩余22的盒子数 if t=0 then a1:=t else a1:=0; end else begin a2:=t; if a1=5 then a1:=a1-5 else a1:=0; end; end; end; end; if a20 then begin if a2 mod 9=0 then inc(tot,a2 div 9)一个箱子最多可以装9个22的盒子 else begin inc(tot,a2 div 9+1); t:=36-(a2 mod 9)*4;剩余空间数 if a1=t then a1:=a1-t else a1:=0; end; end; if a10 then inc(tot,(a1-1) div 36+1);一个箱子最多可以装36个11的盒子 writeln(tot); end; begin主程序 init; main; end.程序结束解法归纳：贪心法(greedy method)就是.只顾眼前利益，每次都选最好的。贪心算法并不从整体最优上加以考虑它所作出的选择只是在某种意义上的局部最优选择。当然，我们希望贪心算法得到的最终结果也是整体最优的。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。对于贪心法解题，一般应注意以下五个方面：解向量，把可行解写成一个N元组的形式，就是解向量；贪心标准，就是眼前“最好”的标准。例如背包问题，标准可以是价值，重量或“性价比”；贪心算法，对于解向量的每一维，用贪心标准在所有可能值中选择一个加入到解向量中；什么样的问题可以考虑用贪心？贪心选择性质：选择具有无后效性，即不依赖与以后将要作出的选择。最优子结构：全局最优包含局部最优；正确性证明的常见方法，反证法是最常见的。通常把一次贪心选择换成另一个值，再把两个可行解加以比较。10、用尽可能少的比较次数，求出任意N个数中的最大数和最小数。输入：文件有两行，第一行只有一个数，即N的值；第二行有N个数。输出：文件有两行，第一行只有一个数，即最小的比较次数，第二行有两个数，第一个数为N个数中最小的数，第二个数为N个数中最大的数。输入输出样例：Input.txtOutput.txt812 6 67 34 27 89 3 53103 89解析：从题义可知，要在N个数中找出其中最大数与最小数，且比较的次数要最少，用排序算法来解，因排序算法最少的比较次数都是O（N2），这对于本题来讲，如果用排序算法来解，肯定不是最优的解。我们知道，题目要我们找出最大数与最小数，我们把这N个数一分为二，在左边的数列中找出最大数与最小数，再与在右边数据中找出的最大数与最小数来比较，就可以得到结果，可问题还是没有解决，我们又把左边的数列一分为二，右边的数列也一分为二，进行同样的比较，最后使每个数列都只有两个数或一个数，这样，问题就变成了两个数比较大小，然后把每二组相互比较大小，以此倒推，就变成了N个数中用最少的比较次数，找N个数的最大数与最小数。这就是分治算法。根据此思想，我们用一个一组数组来存储这N个数，用一个递归过程来模拟分治的情况，用两个变量（S和T）来表示数列的起点与终点，用两个变量（MAX和MIN）来表示最大数与最小数，用一个变量（SUM）来表示比较的次数，因每两个数才进行一次比较，所以最后要把多余的比较次数（即N DIV 2次）减去。完整的参考程序如下：$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+$M 65520,0,655360 Const fni=Input.txt; fno=Output.txt; Var a:array1.30000 of integer;记录数组 sum,n,max,min:integer; f2:text; Procedure Init;初始化数据 var f1:text; i:integer; begin assign(f1,fni); reset(f1); readln(f1,n); for i:=1 to n do read(f1,ai); close(f1); end; Procedure Calc(s,t:integer; var m1,m2:integer);递归分治过程 var p1,p2,m:integer; begin if s=t then begin起点与终点是否相等 m1:=as; m2:=as; exit;退出过程 end; m:=(s+t) div 2;计算N个数的中间点，也就是一分为二的点 Calc(s,m,m1,m2);递归分解原问题的左边部分子问题 Calc(m+1,t,p1,p2); 递归分解原问题的右边部分子问题 if p1m1 then begin m1:=p1; inc(sum) end else inc(sum); if p2m2 then begin m2:=p2; inc(sum) end else inc(sum); end; Begin主程序 sum:=0; Init; Calc(1,n,max,min);递归调用 assign(f2,fno); rewrite(f2); sum:=sum-(n div 2);减去多余的比较次数 writeln(f2,sum);输出最少的比较次数 writeln(f2,min, ,max);输出最小的数与最大的数 close(f2); End.程序结束11、设有(n=6)个球队进行单循环比赛，计划在-1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在-1天内每个队都与不同的对手比赛.例如n=2时的比赛安排为： 队 1 2 3 4 比赛 1-2 3-4 第一天 1-3 2-4 第二天 1-4 2-3 第三天输入输出样例：Input.txtOutput.txt21-2 3-41-3 2-41-4 2-3解析：由于有个运动员要进行单循环比较，且在-1天内结束全部比赛，我们可以将运动员分成两组：1，2，和+1，+2，。给第一组运动员安排一个比赛日程，得到一个阶的一个方阵A1；同时给第二组的运动员安排一个比赛日程，同样会得到一个阶的一个方阵A2。考虑到比赛的性质，设定第I个运动员在某一天的比赛对手为第K个运动员，则第K个运动员在同一天的比赛对手必然是第I个运动员，即若有AI，J=K，则AI，K=I。因此原问题的解（一个N阶方阵）可以由分解后的两个子问题的解，同时，每一个子问题又可以按照上述的二分法分解下去，直至每个组中仅有2个运动员为止。完整的参考程序如下： Const fni=input.txt; fno=output.txt; Var a:array1.64,1.64 of byte; mark:array1.64 of boolean; n,m:integer; Procedure Init;初始化数据 var f1:text; i:integer; begin assign(f1,fni); reset(f1); readln(f1,n); close(f1); m:=1; for i:=1 to n do m:=m*2; end; Procedure Make(s,t:integer);从S号运动员起的共T员运动员单循环日程表的过程 var i,j,t0:integer; begin if t=2 then begin处理只有2名运动员的情况，递归终止条件 a1,s:=s; a1,s+1:=s+1; a2,s:=s+1; a2,s+1:=s; exit; end; t0:=t div 2; Make(s,t0); 递归分解原问题与求解子问题Make(s+t0,t0); 递归分解原问题与求解子问题 for i:=0 to t0-1 do合并子问题的解，构造原问题的解AI，J for j:=0 to t0-1 do begin ai+1+t0,j+s:=ai+1,j+s+t0; ai+1+t0,j+s+t0:=ai+1,j+s; end; end; Procedure Show;输出数据 var f2:text; i,j:integer; begin assign(f2,fno); rewrite(f2); for i:=2 to m do begin fillchar(mark,sizeof(mark),0); for j:=1 to m do if (not markj) and (not markai,j) then begin write(f2,j,-,ai,j, ); markj:=true; markai,j:=true; end; writeln(f2);