资源描述：
《基本算法设计专题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、六基本算法设计专题【热点·难点·赛点】近几年普及组的竞赛中，经常有试题考查我们基本算法的掌握程度，如果我们对于一些基本的算法在平时训练不够或一知半解，竞赛中肯定会成为自己的绊脚石。信息学竞赛中，其主要任务是设计一个好的算法，去求解所给出的问题。而求解所给出问题，其核心算法是一个基本的算法，但要把设计出这个算法来，除核心算法外，还有若干基本算法辅助而成。我们在寻求解决实际问题的算法（解决问题的方法和步骤）时，需要用到一些基本算法模型，如简单的枚举归纳、分治、递推和递归以及贪心算法等，我们应力求掌握这些基本算法的基本思想的同时，将这些算法思想应用到具体
2、的程序设计中去，并创造性地设计解决问题的算法。【解题方法例析】1、一位农民到市场上去买鸡，但他只带了100元钱，可他想买100只鸡。他问卖鸡的人：“鸡多少钱一只？”卖鸡的人说：“一只公鸡值５元，一只母鸡值３元，３只小鸡值１元”。可这位农民书读的少，想了很长时间也没有想出一种用100元钱买100只鸡的方法，由是他请你帮他想出一种买鸡的方案，用一百元要买一百只鸡。问有多少方案，并全部输出来？解析：本题是要求用100元买100只鸡，对于这个问题，只能用枚举法。我们可以用三重循环，来枚举每一种可能的方案，这样，我们要运算1030301次。仔细分析，我们知道
3、公鸡最多可以买20只，母鸡最多可以买33只，小鸡的只数，可以根据总数减去公鸡与母鸡的只数得到，这样，我们只要两重循环，最多714次循环，就可以得出方案。完整的参考程序如下：Constfno='OUTPUT.TXT';Vari,j,k:integer;{I代表公鸡的只数；j代表母鸡的只数；k代表小鸡的只数}f2:text;Beginassign(f2,fno);rewrite(f2);fori:=0to20do{公鸡的只数}forj:=0to(100-5*i)div3dobegin{母鸡的只数}k:=(100-5*i-3*j)*3;{小鸡的只数}if
4、i+j+k=100then{判断是否用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中是否出现过，程序中用一个一维布尔型
5、数组C。完整的参考程序如下：Constfno='OUTPUT.TXT';Vari,j,k,now:integer;suc:boolean;f2:text;c:array[1..9]ofboolean;{记录1到9这9个数是否出现过}Beginassign(f2,fno);rewrite(f2);fori:=123to329dobeginfillchar(c,sizeof(c),0);{给数组C赋初值为假}suc:=true;{判断1到9是否全部出现的标志量，开始赋初值为真}forj:=1to3dobeginnow:=i*j;fork:=1to3do
6、beginif(c[nowmod10])or(nowmod10=0)thenbegin{判断是否1到9之间的数重复出现及是否有零出现}suc:=false;{标志量赋值为假，当前的数不符合条件}break;end;c[nowmod10]:=true;{标记出现的数}now:=nowdiv10;end;end;ifsucthenwriteln(f2,i,'',i*2,'',i*3);{输出找到符合要求的这组数，}end;close(f2);End.解析归纳：枚举就是一个一个地列举。应用到程序中，枚举有许多表现形式，比如把所有的组合都扫描一遍，找出符合
7、要求的组合。可以这么说，枚举是最简单，最基础，也是最没效率的算法。但是，枚举拥有很多优点，以致于他能够活到现在而不被淘汰。首先，枚举有超级无敌准确性，只要时间足够，正确的枚举得出的结论是绝对正确的。其次，枚举拥有天下第一全面性，因为它是对所有方案的全面搜索，所以，它能够得出所有的解。可是由于他的运算量相对较大，我们应该注意尽可能地限制一些无谓运算的出现。3、排序是计算机科学中一个常见任务。有一种特殊的排序，最多只有3个关键字。例如，试图对信息学竞赛的奖牌榜排序时，就只有3个关键字，所有的金牌获得者在最前面，随后是银牌获得者，最后是铜牌获得者。本题中
8、用1，2，3分别表示3个关键字，需将它们按升序排列。排序是通过一系列对换操作实现的。一次操作可以交换两个数的位置。子任务A
