国家集训队2005论文集 胡伟栋

《国家集训队2005论文集 胡伟栋》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、非完美算法长郡中学胡伟栋在信息学竞赛中的应用浅析计算机科学中非完美的例子图片、音频、视频的压缩很多压缩率比较高的压缩方法都是有损压缩密码验证很多都是多对一，通过验证的不一定是正确的搜索引擎不一定能搜索到所有匹配的内容较小的磁盘空间安全、实用方便、快捷非完美算法在信息学乃至整个计算机科学领域，不一定绝对正确的算法就是最好的算法，有可能一个在绝大多数情况下正确的算法(非完美算法)比一个完全正确的算法更有前途。时间使用较少空间使用较少实现较容易容易被接受非完美算法的一些常见方法随机贪心抽样测试部分忽略……——周咏基《论随机化算法的原理与设计》(*)(*)抽样测试法抽样：

2、从统计总体中，任意抽出一部分单位作为样本，并以其结果推算总体的相应指标。抽样测试法s满足条件A具有性质P√抽样测试法10000个元素100个满足条件只要少量抽样就能取得较高的正确率抽样测试法在抽样测试时，有时总体中存在一些特殊的元素，这些元素满足条件的概率往往与其他元素满足条件的概率相差较大。如果特别的在这些元素中抽取一些进行测试，则可以加快出解的速度或增大解的正确率。——特殊抽样抽样测试法——特殊抽样α={‘A’,’B’,’C’,……,’Z’}总体：α的所有子集条件：含{‘A’,’B’,’C’,……,’G’}的集合取特殊元素α即满足条件！质数判定朴素的质数判定方

3、法：用2~试除。O(n0.5)抽样测试法：在2~中抽取k个试除。×StrongPseudoprime对于奇数n和正整数a，设n-1=d·2s(d为奇数)，若：ad≡1(modn)或存在0≤r

4、干个质数。只用2测试：最小的强伪质数为2047，在小于2.5×1010中有4842个强伪质数。只用2,3测试：最小强伪质数大于1.3×106。只用2,3,5测试：最小强伪质数大于2.5×107。只用2,3,5,7测试：最小强伪质数大于3.2×109。质数测试——抽样测试一般情况下，只要用2,3,5,7进行测试就能正确的判断一个数是否为质数。时间复杂度：O(log2n)抽样测试法明显降低时间复杂度！抽样测试法部分忽略法在信息学中，可能会遇到这样情况：一个题的分类非常多，同时某些情况的处理非常复杂，但这些情况往往不是主要情况(即出现的概率很小或不处理这些情况对答案不会

5、造成很大的影响)。有时，忽略这些复杂却对结果影响不大的情况仍然可以达到令人满意的结果。部分忽略法ProblemABD30%40%√√√正确率：99%C29%1%少多少非常多情况出现率处理用时判断点是否在多边形内给出一个点和一个简单多边形(设点不在多边形的边上)，判断点是否在多边形内。方法：判断点是否在多边形内特殊情况：…忽略特殊情况！？√×√×ABCD判断点是否在多边形内射线经过多边形的顶点是一种非常特殊的情况。而我们取的是一条非常特殊的射线——与x轴平行的射线。经验表明，特殊的射线经过多边形的顶点的几率会大于一般的射线！解决方法：取一条一般的射线！判断点是否在多

6、边形内ABCD√判断点是否在多边形内多取几条！将出现次数最多的结果作为正确结果设取一条射线，其经过多边形顶点的概率为x，取n条，所得结果的正确率不小于1-x[n/2]部分忽略部分忽略法能减轻我们的思维负担和编程复杂性。部分忽略法通常要加入一些小小的技巧。使被忽略的情况对结果影响尽量小！非完美算法共同点：不完全性优点时空消耗低编程复杂度低思维复杂度低能减少编程错误缺点不完全正确总结在信息学竞赛以及实际应用中，并不是完全正确的算法就一定比非完美的算法表现得好，因为非完美算法的不完全性，反而使非完美算法在一些方面比正确算法表现得更好。因此，合理的使用非完美算法能取得非常

7、令人满意的结果。忠告在能用完全正确的算法时要尽量使用完全正确的算法，只有当确实难想到很好的方法或时间比较紧时才使用非完美算法。结束语想了解更多，欢迎阅读我的论文。里面还有一些更好玩的例子，如：NOIP2003的《传染病控制》、ACM的《直觉主义逻辑》以及IOI2004的《Polygon》。谢谢RP类问题对于一个判定类问题，如果存在一个随机算法，当此算法判定结果为否时，原问题的结果必为否，同时，当此算法的判定结果为是时，原问题的结果为是的概率大于50%，那么这个问题属于RP类问题。该算法称为Monte-Carlo算法。如果一个问题是RP类问题，可以通过多次运行它的一

8、个Mont