《中山纪念中学信息学奥林匹克算法设计题选》由会员分享，可在线阅读，更多相关《中山纪念中学信息学奥林匹克算法设计题选（34页珍藏版）》请在金锄头文库上搜索。
1、中 算念法言息设奥林计克题设选选（一）、算法设计：一、筛选法1 ：求 1 100 间的所有素数。分析：用筛选法，先把2100 的数存到一个数组中，然后先把2 的所有倍数删除掉（即让此数变为0）再删3的倍数，继续往上就是5的倍数，7的倍数，最后，剩下的数（即数组中不为0的数）就是素数。Var n:array2.100 of integer;I,j,k:i nt eger;BeginFor I:=2 to 100 do nI:=I;I:=2;RepeatJ:=1;RepeatJ:=j+1;K:=I*j;辻 nk0 then Nk:=0;Until (j+1)*i100;Repeati:=i+1;u
2、ntil (ni0) or (i50);Until i50;for i:=2 to 100 do if ni0 then write(ni:4); end.另外，该题也可利用集合来做，同样用筛选法：var ss:set of 2.100;集合SS用来存放数i, j,k:i nt eger;beginss: = 2.100;for i:=2 to 50 do begin把SS中2至50的倍数全部删除j:=1;repeatj:=j+l； k:=i*j; if k in ss then ss:=ss-k;until k+i100;end;for i:=2 to 100 do if i in ss t
3、hen write（i:3）;end.2：不相同的余数问题，即“秦王暗点兵”或“韩信点兵”： 有一楼房的楼梯级数很奇特，一步跨二级多一级，一步跨三级多二级，如果分用四、五、六、七去除级数分 别余三、三、五、五。问这楼房共有多少级阶梯？（已知不超过400级）。分析：已知级数不超过400级，我们可仿照求素数的方法，把1400存进一个数组中，然后这些数用2、3、 4、5、6、7分别去除，如果余数分别不为1、2、3、3、5、5就删除它，最后，最小的一个没有被删除的数就是 解。Var n:array1.400 of integer;I,j,k:i nt eger;Cons t a:array1.6 of
4、 int eger=(2,3,4,5,6,7);除数b:array1.6 of int eger=(1,2,3,3,5,5);余数BeginFor I:=1 to 400 do nI:=I;for i:=1 to 6 do beginfor k:=1 to 400 do begin if nk0 then beginif k mod aibi then begin nk:=0;end;end;end;end;i:=0;repeati:=i+1;until ni0;writ e(ni:4);end.找最小的一个没有被删除的数分析：用上述方法由于要删除的数非常多，因此速度较慢，我们可以反过来想，把
5、满足余数条件的数加上记 号，最后，最小的一个加上了六个记号的数就是答案。Var n:array1.400 of integer;I,j,k:i nt eger;cons t a:array1.6 of int eger=(2,3,4,5,6,7); b:array1.6 of int eger=(l,2,3,3,5,5);BeginFor I:=1 to 400 do nI:=0;for k:=1 to 400 do beginfor i:=1 to 6 do beginif k mod ai=bi then nk:=nk+1; end;end;i:=0;repeati:=i+1;until
6、ni=6;writ e(i:4);end.这样，速度要快很多。大家思考一下下题：孙子算法有题：今有物，不知其数。三、三数之，剩二；五、 五数之，剩三；七、七数之，剩二。问物几何？（最小正数解）。3：狼追兔子，兔子躲进了 10个环形分布的洞的某一个中。狼在第1个洞中没有找到兔子，就间隔1 个洞， 到第 3个洞中去找，也没找到兔子，就间隔2个洞，到第 6个洞中去找。以后狼每次多隔1个洞去找兔子，。 这样狼一直找不到兔子。请问兔子可能躲在哪个洞中？分析：该题看似简单，只要每次把狼找过的洞删除就行了，但是，这种删除操作的结束状态（条件）是什么 呢？而且，狼的搜索过程中，如果要间隔11 个洞时，我们是否
7、可以认为就是间隔1 个洞？实际上，第一个问题应该是当狼回到第1 个洞，并且又上间隔1 个洞去找兔子时，就应该结束删除操作，因 为此后的搜索是重复以前的搜索了，此时，那些没有被删除过的洞就是答案。这里，大家一定不能想当然地认为： 结束条件就是只剩下一个洞的时候！题目中并没有说明只有一个答案，事实上是有四个洞的！第二个问题也是可行的。因为只有10个洞，间隔11个洞和间隔1个洞的作用是相同的。var d:array1.10 of integer; i,j,k,l: integer;beginfor i:=1 to 10 do di:=1;i:=1;j:=1;repeatdi:=0;j:=j+l；if
8、 j10 then j:=j-10; i:=i+j;if i10 then i:=i-10;until (i=l) and (j=1);for i:=1 to 10 do if di0 then write(i); end.习题1、作 8001000 的素数表。答案：809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 9972、一位数学家和一些游客共81人不幸落入强盗手中，强盗把俘虏排成一队，宣布每天处理所有第2的N次方个
9、俘虏(N=0)，而只放走剩下的最后一个。由于数学家身怀重任，不得不选择了一个恰当的位置而最终被放 走。请问他归初排在第几个位置。 答案：803、有一堆礼物，工作人员无论是分成二个一份，还是三个、四个、五个、六个一份，总是多一个。请问这堆礼 物至少多少个？ 答案：614、一付扑克中拿出所有的黑桃AK按顺序排好。第一次翻出第一张牌一A,放在一边，再拿出第二张放到 牌的最下面。以后每次都翻出一张牌，再把一张牌放到最后，问第八次翻出的牌是哪一张？ 答案：4二、排序方法本小节讨论几种排序方法。何为排序呢？就是把一些数字按递增或递减的顺序排列。例如：4， 3， 5， 1， 2 这五个数，按从小到大的顺序排
10、列是：1， 2， 3， 4， 5；按从大到小的顺序排列是：5， 4， 3， 2， 1。1、双数组排序法：用一个数组存放未经排序的数，然后按顺序找出未经排序数中的最大数，按顺序存放到另一个数组中，要考 虑的问题是：怎样把未经排序数组中已经找出的数删除。程序如下：uses crt;var n,m:array1.10 of integer;i,j,max,k:integer;beginclrscr;for i:=l to 10 do read(ni);读入 10 个数for i:=1 to 10 do beginmax:=0;for j:=1 to 10 do begin 从数组N找到最大的数if
11、njmax then beginmax:=nj;k:=j;记住该位置end;end;mi:=max;存入数组M中nk:=-30000;删除该数，把值变为-30000end;for i:=1 to 10 do wri te(mi:3);打印已排好序的数end.2、插入法排序： 插入法排序是把存放在数组中的未经排序的数逐个插入到另外一个数组中。如何找到每个数的正确位置呢？ 我们应该用动态查找的方法，从已排序的数组中从最左边开始查找，直到找到一个数大于等于待插入的数时，该 数之前就是我们要找的位置。此方法可用数组来完成，也可用链表来完成。程序如下：把数先存放在一个数组中，再逐个插入到另一个数组中：u
12、ses crt;var n,m:array1.10 of integer;i,j,k,l:integer;beginclrscr;for i:=1 to 10 do read(ni); 读入 10 个数存放到数组 N 中 ml:=nl; 在数组M中存放第一个数for i:=2 to 10 do begin 把数组N中第2到第10个数逐个插入到数组M中j:=0;repeatj:=j+1;until (j=i) or (mj二ni);找到待插入的数在M中的位置if j=i then mj:=ni else beginfor l:=i-1 down to j do ml+l:=ml; 把该位置后的数
13、后移 mj:=ni; 把待插入的数放在正确位置end;end;for i:=1 to 10 do write(mi:3);打印end.3、冒泡法排序冒泡法：这是最常用的一种排序方法，其实质是：先把数据存放在数组中，然后从第一个开始，分别与其后 所有数据进行比较，如果第一个比其后某个数据小，则交换它们的值，一直到第一个与其后所有数据比较完，这 时第一个数据就是最大的一个；然后再把第二个数据再与其后数据进行比较，比较完后，第二个数据则为第二大 的，这样直到倒数第二个数据比较完后，整个数组就已经按从大到小的顺序排列了。其作用示意如下：假设我们已经把6个数据分别存放在N1至N6中，其值分别为：3,1,
14、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再重复进行第三个值与其后值的比较，直到第五个值与第六个值比较完后， 这时数组的值已经变为：9， 6， 5， 3， 2， 1至此，数组已经按从大到小的顺序排好了。程序如下 ： 例 6、1Var n:array1.1O of integer;说明一个数组型变量I,j,t:int eger;BeginFor I:=1 to 10 do Readln(nI);For I:=1 to 9 do begin
