搜索
中山纪念中学信息学奥林匹克算法设计题选第1页共38页算法设计题选（一）、算法设计：一、筛选法1：求1—100间的所有素数。分析：用筛选法，先把2—100的数存到一个数组中，然后先把2的所有倍数删除掉（即让此数变为0），再删3的倍数，继续往上就是5的倍数，7的倍数……，最后，剩下的数(即数组中不为0的数)就是素数。Varn:array[2..100]ofinteger;I,j,k:integer;BeginForI:=2to100don[I]:=I;I:=2;RepeatJ:=1;RepeatJ:=j+1;K:=I*j;ifn[k]0thenN[k]:=0;Until(j+1)*i100;Repeati:=i+1;until(n[i]0)or(i50);Untili50;fori:=2to100doifn[i]0thenwrite(n[i]:4);end.另外，该题也可利用集合来做，同样用筛选法：varss:setof2..100;i,j,k:integer;beginss:=[2..100];fori:=2to50dobeginj:=1;repeatj:=j+1;k:=i*j;ifkinssthenss:=ss-[k];untilk+i100;end;fori:=2to100doifiinssthen集合SS用来存放数把SS中2至50的倍数全部删除中山纪念中学信息学奥林匹克算法设计题选第2页共38页write(i:3);end.2：不相同的余数问题，即“秦王暗点兵”或“韩信点兵”：有一楼房的楼梯级数很奇特，一步跨二级多一级，一步跨三级多二级，如果分用四、五、六、七去除级数分别余三、三、五、五。问这楼房共有多少级阶梯？（已知不超过400级）。分析：已知级数不超过400级，我们可仿照求素数的方法，把1—400存进一个数组中，然后这些数用2、3、4、5、6、7分别去除，如果余数分别不为1、2、3、3、5、5就删除它，最后，最小的一个没有被删除的数就是解。Varn:array[1..400]ofinteger;I,j,k:integer;Consta:array[1..6]ofinteger=(2,3,4,5,6,7);b:array[1..6]ofinteger=(1,2,3,3,5,5);BeginForI:=1to400don[I]:=I;fori:=1to6dobeginfork:=1to400dobeginifn[k]0thenbeginifkmoda[i]b[i]thenbeginn[k]:=0;end;end;end;end;i:=0;repeati:=i+1;untiln[i]0;write(n[i]:4);end.除数余数找最小的一个没有被删除的数分析：用上述方法由于要删除的数非常多，因此速度较慢，我们可以反过来想，把满足余数条件的数加上记号，最后，最小的一个加上了六个记号的数就是答案。Varn:array[1..400]ofinteger;I,j,k:integer;consta:array[1..6]ofinteger=(2,3,4,5,6,7);b:array[1..6]ofinteger=(1,2,3,3,5,5);BeginForI:=1to400don[I]:=0;fork:=1to400dobegin中山纪念中学信息学奥林匹克算法设计题选第3页共38页fori:=1to6dobeginifkmoda[i]=b[i]thenn[k]:=n[k]+1;end;end;i:=0;repeati:=i+1;untiln[i]=6;write(i:4);end.这样，速度要快很多。大家思考一下下题：《孙子算法》有题：今有物，不知其数。三、三数之，剩二；五、五数之，剩三；七、七数之，剩二。问物几何？（最小正数解）。3：狼追兔子，兔子躲进了10个环形分布的洞的某一个中。狼在第1个洞中没有找到兔子，就间隔1个洞，到第3个洞中去找，也没找到兔子，就间隔2个洞，到第6个洞中去找。以后狼每次多隔1个洞去找兔子，……。这样狼一直找不到兔子。请问兔子可能躲在哪个洞中？分析：该题看似简单，只要每次把狼找过的洞删除就行了，但是，这种删除操作的结束状态（条件）是什么呢？而且，狼的搜索过程中，如果要间隔11个洞时，我们是否可以认为就是间隔1个洞？实际上，第一个问题应该是当狼回到第1个洞，并且又上间隔1个洞去找兔子时，就应该结束删除操作，因为此后的搜索是重复以前的搜索了，此时，那些没有被删除过的洞就是答案。这里，大家一定不能想当然地认为：结束条件就是只剩下一个洞的时候！题目中并没有说明只有一个答案，事实上是有四个洞的！第二个问题也是可行的。因为只有10个洞，间隔11个洞和间隔1个洞的作用是相同的。vard:array[1..10]ofinteger;i,j,k,l:integer;beginfori:=1to10dod[i]:=1;i:=1;j:=1;repeatd[i]:=0;j:=j+1;ifj10thenj:=j-10;i:=i+j;ifi10theni:=i-10;until(i=1)and(j=1);fori:=1to10doifd[i]0thenwrite(i);end.习题1、作800—1000的素数表。答案：8098118218238278298398538578598638778818838879079119199299379419479539679719779839919972、一位数学家和一些游客共81人不幸落入强盗手中，强盗把俘虏排成一队，宣布每天处理所有中山纪念中学信息学奥林匹克算法设计题选第4页共38页第2的N次方个俘虏（N=0），而只放走剩下的最后一个。由于数学家身怀重任，不得不选择了一个恰当的位置而最终被放走。请问他归初排在第几个位置。答案：803、有一堆礼物，工作人员无论是分成二个一份，还是三个、四个、五个、六个一份，总是多一个。请问这堆礼物至少多少个？答案：614、一付扑克中拿出所有的黑桃A……K按顺序排好。第一次翻出第一张牌——A，放在一边，再拿出第二张放到牌的最下面。以后每次都翻出一张牌，再把一张牌放到最后，问第八次翻出的牌是哪一张？答案：4二、排序方法本小节讨论几种排序方法。何为排序呢？就是把一些数字按递增或递减的顺序排列。例如：4，3，5，1，2这五个数，按从小到大的顺序排列是：1，2，3，4，5；按从大到小的顺序排列是：5，4，3，2，1。1、双数组排序法：用一个数组存放未经排序的数，然后按顺序找出未经排序数中的最大数，按顺序存放到另一个数组中，要考虑的问题是：怎样把未经排序数组中已经找出的数删除。程序如下：usescrt;varn,m:array[1..10]ofinteger;i,j,max,k:integer;beginclrscr;fori:=1to10doread(n[i]);{读入10个数}fori:=1to10dobeginmax:=0;forj:=1to10dobegin{从数组N找到最大的数}ifn[j]maxthenbeginmax:=n[j];k:=j;{记住该位置}end;end;m[i]:=max;{存入数组M中}n[k]:=-30000;{删除该数，把值变为-30000}end;fori:=1to10dowrite(m[i]:3);{打印已排好序的数}end.2、插入法排序：插入法排序是把存放在数组中的未经排序的数逐个插入到另外一个数组中。如何找到每个数的正确位置呢？我们应该用动态查找的方法，从已排序的数组中从最左边开始查找，直到找到一个数大于等于待插入的数时，该数之前就是我们要找的位置。此方法可用数组来完成，也可用链表来完成。程序如下：把数先存放在一个数组中，再逐个插入到另一个数组中：usescrt;中山纪念中学信息学奥林匹克算法设计题选第5页共38页varn,m:array[1..10]ofinteger;i,j,k,l:integer;beginclrscr;fori:=1to10doread(n[i]);{读入10个数存放到数组N中}m[1]:=n[1];{在数组M中存放第一个数}fori:=2to10dobegin{把数组N中第2到第10个数逐个插入到数组M中}j:=0;repeatj:=j+1;until(j=i)or(m[j]=n[i]);{找到待插入的数在M中的位置}ifj=ithenm[j]:=n[i]elsebeginforl:=i-1downtojdom[l+1]:=m[l];{把该位置后的数后移}m[j]:=n[i];{把待插入的数放在正确位置}end;end;fori:=1to10dowrite(m[i]:3);{打印}end.3、冒泡法排序冒泡法：这是最常用的一种排序方法，其实质是：先把数据存放在数组中，然后从第一个开始，分别与其后所有数据进行比较，如果第一个比其后某个数据小，则交换它们的值，一直到第一个与其后所有数据比较完，这时第一个数据就是最大的一个；然后再把第二个数据再与其后数据进行比较，比较完后，第二个数据则为第二大的，这样直到倒数第二个数据比较完后，整个数组就已经按从大到小的顺序排列了。其作用示意如下：假设我们已经把6个数据分别存放在N[1]至N[6]中，其值分别为：3,1,5,9,2,6。交换前的值为：3，1，5，9，2，6第一步，把第一个值与其后第一个进行比较，这时31，所以值不变：3，1，5，9，2，6第二步：把第一个值与其后第二个进行比较，这时35，所以值交换：5，1，3，9，2，6第三步：把第一个值与其后第三个进行比较，这时59，所以值交换：9，1，3，5，2，6…………当第一个值与其后所有值比较完后，第一个值已经是最大的，数组值为：9，1，3，5，2，6这时，重复上述第一步的操作，只是把第一个值换成第二个值，第一个值即第二个值与其后第一个值进行比较，这时13，所以交换其值：9，3，1，5，2，6第二个值与其后所有值比较完后，数组值为：9，6，1，3，2，5中山纪念中学信息学奥林匹克算法设计题选第6页共38页再重复进行第三个值与其后值的比较，直到第五个值与第六个值比较完后，这时数组的值已经变为：9，6，5，3，2，1至此，数组已经按从大到小的顺序排好了。程序如下：[例6、1]Varn:array[1..10]ofinteger;I,j,t:integer;BeginForI:=1to10doReadln(n[I]);ForI:=1to9dobeginForj:=I+1to10dobeginIfn[I]n[j]thenbeginT:=n[I];N[I]:=n[j];N[j]:=t;End;End;End;ForI:=1to10dobeginWrite(n[I]:5);End;End.说明一个数组型变量从键盘读入10个数据存放在数组N中参加比较的第一个数据为第1至第9个。第二个数据为第一个数据之后所有的数据如果n[I]n[j]则用以下三句来交换其位置打印排序后的结果四、选择排序：设数组中有N个数，取I=1，2，3，……N-1，每次找出后N-I+1个数字中最小的与第I个数字交换位置。程序如下：usescrt;varn:array[1..10]ofinteger;i,j,k,t,min:integer;beginclrscr;fori:=1to10doread(n[i]);fori:=1to9dobeginmin:=30000;forj:=ito10dobegin{在第I到第10个数中找到最小的一个}ifn[j]minthenbeginmin:=n[j];k:=j;{记录该位置}end;end;t:=n[i];n[i]:=n[k];n[k]:=t;end;中山纪念中学信息学奥林匹克算法设计题选第7页共38页fori:=1to10dowrite(n[i]:4);end.5、快速排序：（1）把N个数存放在数组S中，当前集合为S中所有数。（2）把当前集合第一个数定为标