算法合集之《中等硬度解题报告》.doc

《算法合集之《中等硬度解题报告》.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、中等硬度解题报告[摘要]中等硬度是IOI2000第一试的最后一道题目。这道题主要考察选手的创造性，自创算法正确高效的解决问的能力。本文主要讲述我做这到题目的过程和方法[关键字]二分法随机数[问题描述]见附件[问题分析]算法1-1：由于每次比较可以得出最大的数和最小的数（虽然不知道那个数最大的），所以可以先求出1，2，3号中的最大与最小者，再用它们与4号比较得出1~4号中的最大最小者，再用这两个数与5号比……。以此类推，可求出1~n中的最大与最小者，显然它们不是中等硬度物体，所以将它们去掉，再用上述方法求出剩下n-2中的最大与最小者，再

2、去掉，……，最后剩下的一个数就是中等硬度的物体编号。这个算法比较的复杂度为,不满足1449个物体用7777次比较出来的限制。究其原因是因为每次比较利用的信息不够。一次比较三个数，可以知道这三个数的顺序关系（虽然不知道是递增还是递减），若已知两个数的顺序关系，再与第三个数比较，则可知道第三个数在前两个数的顺序关系下的位置。算法1-1中正是没有利用这个信息，导致复杂度高。所以利用这个排序的观点，得出算法2-1。算法2-1：已知前m个物体硬度的顺序关系。将下一个物体用二分法插入到适当的位置，得出前m+1个物体硬度的顺序关系。以此类推得出n个

3、物体的顺序关系，从而知道中等硬度者。参看实例：Label12345Strength25431插入物体编号已知顺序比较返回结果得出顺序1233132413213441（）32514324354（1）432514321451（）143251432注：（）表示改物体可能插入的区域。第二行得出结论4在1和3中间。第三行得出结论5的位置在4的左侧，所以还要比较一次以确定5与1的位置关系。这个算法采用二分插入法。二分插入法复杂度为。要插入n-3个数。所以总的复杂度比要小一些。实践证明，当n=1449时，平均用11000多次比较。（）究其原因是因为

4、这个算法将所有物体的硬度都排了序，其中有些是一定不只中等硬度的，对于它们的排序浪费了比较次数。所以在算法2-1的基础上加上剪枝，得出算法2-2。算法2-2：设2m+1=n。则可知对于一个已全部排好顺序的序列，中等硬度物体左边有n个物体，右边也有n个物体。也就是说若已知一个物体所在序列中位置的左边(右边)有n个以上物体时，则它一定不是所求。所以不用排出它的具体位置，将其插在最右边（左边）即可。利用这一原理，用先将前m+1个物体排序，因为这m+1个物体都有可能是所求。当第m+2号物体插入后，最两端的物体肯定不是所求。同理当现在已经有m+3

5、个物体排好序，则这个序列两端的两个物体一定不是所求。也就是说第k个物体只有插在位置（k-m-1）到位置（m+1）这个子序列中，才有可能成为中等硬度者。所以在二分法插入中，若当前插入区域已不在上述区域中，则它的具体位置对结果没有影响，所以直接插入到最左端或最右端。举个简单的实例，当前已将n-1个物体排好序，在这n-1个物体中只有最中间的两个物体才有可能为中等硬度。我们称其为A,B（A在B左侧）。按照上述方法，第n个物体C只需与A、B比较一次。若A在中间，则C的插入区域在A的左边，已不再可能区域中，于是将C插入到最左端，最终结果是A。若B

6、在中间，同理将C插入到最右端，结果为C。若C在中间，则插入到AB之间，结果为C。而不需要象算法2-1那样，比较若干次，将C插入到正确的位置。第二个剪枝在第一个剪枝的基础上，通过实践发现有相当一部分物体是通过上述剪枝，插入到两端。而当判断出它不属于可能区域时，已经做了2~5次判断。所以直接先用1~2次比较，判断出插入物体是否在可能区域。若是，则在用二分法插入；若否，则直接插入到两端。这样可以提高一些效率。这个改进可使1449个物体的比较次数平均为8200，只距7777的上限一步之遥。但改进幅度很小，原因是这种排序的方法对前725个物体的

7、排序无法剪枝，要用去5000次左右的比较。所以要在规定次数内解出此题，只能改变算法，进入3-X算法系列。算法3-1：虽然前两系列算法没有成功，但我总结了一下，有以下2点经验值得借鉴。1.要有位置概念。虽然不知大小，但要有顺序。2.要有区域概念。先判断出可能区域，再逐步细化。（算法2-2就是细化得太早）所以算法是：用a[1]和a[2]（a[i]表示可能区域中第i个物体的号码是a[i]。不妨设a[1]在a[2]左边）依次与a[3]~a[n]比较，将所有物体分为三类：一类在a[1]左边（比a[1]小或大），一类在a[1]和a[2]之间（硬度

8、介于两者之间），一类在a[2]右边（比a[2]大或小）。统计个数可知中等硬度物体是a[1]或a[2]或三类之一。若是三类之一，再对这一类物体采用相似的方法分解，直到求出结果。之所以称相似的方法，是因为有两点不同：1.不能