基本算法设计专题.docVIP

六 基本算法设计专题 【热点·难点·赛点】 近几年普及组的竞赛中，经常有试题考查我们基本算法的掌握程度，如果我们对于一些基本的算法在平时训练不够或一知半解，竞赛中肯定会成为自己的绊脚石。信息学竞赛中，其主要任务是设计一个好的算法，去求解所给出的问题。而求解所给出问题，其核心算法是一个基本的算法，但要把设计出这个算法来，除核心算法外，还有若干基本算法辅助而成。我们在寻求解决实际问题的算法（解决问题的方法和步骤）时，需要用到一些基本算法模型，如简单的枚举归纳、分治、递推和递归以及贪心算法等，我们应力求掌握这些基本算法的基本思想的同时，将这些算法思想应用到具体的程序设计中去，并创造性地设计解决问题的算法。 【解题方法例析】 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，2…9共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:array[1..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 (c[now mod 10]) or (now mod 10=0) then begin{判断是否1到9之间的数重复出现及是否有零出现} suc:=false; {标志量赋值为假，当前的数不符合条件} break; end; c[now mod 10]:=true;{标记出现的数} now:=now div 10; end; end; if suc then writeln(f2,i, ,i*2, ,i*3);{输出找到符合要求的这组数，} end; close(f2); End. 解析归纳：枚举就是一个一个地列举。 应用到程序中，枚举有许多表现形式，比如把所有的组合都扫描一遍，找出符合要求的组合。可以这么说，枚举是最简单，最基础