奥赛经典题目讲解.doc

《奥赛经典题目讲解.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、巧用数组下标 轻松回避重复判断［作者：佚名    转贴自：网络    点击数：68    文章录入：kknd］在程序设计的某个环节中，需要统计不同数据的个数，按照常规思路的算法简单描述如下：①读入下一个数；②将该数与之前已读入的数一一比较，如果都不同，则该数是新数，累加器加1；否则，表示该数是旧数，有重复，直接退出比较的循环②。③是否读完所有数据，如果是，输出累加器值，结束；否则，转到①；下面用一个实例说明。例产生10个范围为1—20的随机整数，统计不同数的个数。按照常规思路，得如下参考程序。programtongji(input,output);vara:array[1.

2、.10]ofinteger;i,j,t:integer;beginwriteln('产生随机数:');randomize;fori:=1to10dobegina[i]:=1+random(19);write('',a[i]);end;t:=0;fori:=1to10dobeginj:=1;while(ja[j])doj:=j+1;ifj=ithent:=t+1;end;writeln;writeln('统计不同数据有',t,’个.’);end.由以上程序可知，完成数据统计需要两重循环，时间复杂度为O(n2)。如果数据是正整数，那么试着换另外一种思路

3、：将数据作为数组的下标，进行一个赋值为1的标记操作。比如，现有数：2，6，2，用数组b[]辅助存储，依次操作：b[2]:=1，b[6]:=1，接下来是2，已重复，在程序中无需特殊判断，执行相同操作：b[2]:=1，这样就可以有效回避重复判断，最后只要累计b[]数组中值为1的个数，事实上，数组中其他元素由于没有进行赋值操作，保留了默认值0，因此累加操作也可以扩展到所有数组元素的直接相加，为了更有效的累加，可以在执行赋值操作时，加入数据范围的上限、下限标识：max和min，每读入一个数后，更新数据范围，最后只要将下标为上下限范围的数组数据进行累加。参考程序如下：programt

4、ongji(input,output);vara:array[1..10]ofinteger;b:array[1..20]ofinteger;i,t,max,min:integer;beginwriteln('产生随机数:');randomize;fori:=1to10do{产生10个(1-20)随机数}begina[i]:=1+random(19);write('',a[i]);end;t:=0;max:=0;min:=10000;{设置统计时，数组范围的上下标识}fori:=1to10dobeginb[a[i]]:=1;{将数据以数组下标的形式写入，避免判断}ifa[i

5、]>maxthenmax:=a[i];{更新数组范围的上下标识}ifa[i]

6、判断非0后，再累加1完成。改变部分的代码如下：t:=0;max:=0;min:=10000;{设置统计时，数组范围的上下标识}fori:=1to10dobeginb[a[i]]:=b[a[i]]+1;ifa[i]>maxthenmax:=a[i];ifa[i]0thenbeginwrite(i,’:’,b[i],’’);t:=t+1;end;{统计不同数据个数}writeln;writeln(t);时间复杂度由原来的O(n2)降低为O(n)。编程时，不妨抛开传统解题思路，尝试着用其他方

7、法解决，一个小小的数据统计程序，或许可以给你些许启迪，愿本文起到抛砖引玉的作用。历届NOIP搜索算法全集用动态规划来解背包问题在历届NOIP竞赛中，有4道初赛题和5道复赛题均涉及到背包问题，所谓的背包问题，可以描述如下：一个小偷打劫一个保险箱，发现柜子里有N类不同大小与价值的物品，但小偷只有一个容积为M的背包来装东西，背包问题就是要找出一个小偷选择所偷物品的组合，以使偷走的物品总价值最大。如有4件物品，容积分别为：3458对应的价值分别为：45710小偷背包的载重量为：12则取编号为123的物品，得到最大价值为16