算法合集之《浅析信息学中的“分”与“合”》

《算法合集之《浅析信息学中的“分”与“合”》》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅析信息学中的“分”与“合”福建省福州第三屮学杨沐目录【摘要】3【关键字】3【正文】3一、引言3二、例题分析3［例一］牛奶模版4［例二］树的重建6［例三］最优序列9三、总结12【感谢】13【参考文献】13【附录】13【摘要】本文就“分”与“合”的思想在信息学中的应用进行讨论与研究。“分”与“合”思想的精髓在于通过在“分”与“合”之间的转化屮找到问题的本质从而解决问题，该思想的应用并非仅限于传统意义上的“分治法”。本文通过分析例题《牛奶模版》、《树的重建》与《最优序列》來介绍“分”与“合”思想在解题屮的具体应用。【关键字】“分”与“合”、转化、辨证关

2、系【正文】一、引言——“话说天下大势，合久必分，分久必合”，这富有辨证意味的第一句话可以说是《三国演义》的精髓。浩浩中华儿T年的历史，充分说明了“合久必分，分久必合”这一观点的正确性。“合久必分，分久必合”是从低级到高级，螺旋式发展的过程，纵观天下事，无不是在“分”与“合”之间互相转化下发展的。“分”与“合”的规律不仅在社会发展上得到应验，在信息学中的许多题冃的解题过程小也有着充分的体现。“分”的思想是将一个难以直接解决的大问题，分成一些规模较小或限制某些条件的了问题來思考，以求将问题解决。“合”的思想与“分”相对，是将“分”出的一•些零碎的小问题

3、合并成一个大问题，从而理清关系，得出解法。在当今信息学竞赛小，我们常常会碰到齐种问题，由于规模过大而难以思考,无从入手，乂或情况过于纷繁复杂导致思考难度骤增，这时不妨尝试使用“分”与“合”的思考方式來帮助分析问题。二、例题分析下面，作者通过介绍三个例题《牛奶模版》、《树的重建》和《最优序列》，结合各题自身特性利用“分”与“合”的思想解题，希望能起到抛砖引土的作用。［例一］牛奶模版I问题简述由于奶牛们的产奶品质波动不定，FJ决定找出奶牛产奶品质波动的规律。FJ用一个由0到1000000的整数组成的长度为N(1

4、记录了各天奶牛们的产奶品质，FJ希望从中找出最长的一段模版串，使得该模版串在序列中出现至少£次，请输出最长模版串的长度。(例如，12323231中2323出现了2次,最长的模版长度为4。)问题分析木题是一道与串匹配有关的问题，我们很自然的想到使用解决字符串问题的利器——后缀树，事实上，使用后缀树确实可以在线性时间内解决本题，但后缀树的高编程复杂度使我们很难在限定时间内完成解题任务。那么，是否存在简单而又行Z冇效的算法呢？普通枚举法解决此题最简单的方法莫过于枚举法了，我们可以枚举岀原串的所有子串，互相比对并统计出它们各自岀现的次数，从中选出出现次数不

5、少于£次的最长子串。由于原串的子串数达到屮的级别，而字符串比较的时间复杂度为O(N)因此该枚举法的吋间复杂度高达O(7V5),完全无法在限定吋间内出解。上述枚举法之所以低效，很重要的一个原因是重复比较过多。这时我们又想到了高效的串匹配算法——KMP算法。在枚举原串的了串后，我们可以使用KMP算法在0(2)的时间内算出该串在原串中的出现次数，因而将总算法复杂度降为O(7V3)o但是，当我们试图使用串匹配算法继续优化算法时间复朵度的时候遇到了重重困难，在多次尝试无果后，不得不回到问题的起点，换一角度思考问题。枚举法改进观察普通的枚举法，我们发现其实枚举

6、所有了串的做法存在许多冗余，因为对于任意两个子串，相等的先决条件是它们的长度必须相同，这提示我们可以枚举子串的长度。而题口中存在着一个很明显的单调性，即在原串小若存在一个长度为/幼的了串出现了至少R次，则对于任意长度lenlen'

7、有N—ls+l个，可以使用hash表来存储各串，并用以判等。根据题目特点,我们设计如下hash函数:对于子串皿瓦…％“1fk=(akxpllen~[+ak+lxplen~2+ak+2xplle,,~3...ak+len_x)modhashsizelposik=(akxp2len~[+你+]xp2le"~2+ak+2xp2len~3...ak+len_})modhashsizelpl,p2可以取任意素数,hashsize,hashsize2为大素数，posik表示皿仇在hash表屮的位置，使用齐代替皿“•的内容(使得冲突时的比较时间复杂度降为0(

8、1))。若二子串的•与/值分别相同，则认为这两个子串相同(由于设置了两个加必函数，误判的概率大约仅为，可以忽略)。hash