算法设计与分析课程设计报告(共10页).doc

精选优质文档-倾情为你奉上算法与分析课程设计报告题 目： 算法设计和分析 专 业： 网络工程 班 级： 学 号： 11 姓 名： 赫前进 太原工业学院计算机工程系 2012年 11月 24 日第二章 主元素问题一、 算法问题描述主元素问题:设T0.n-1是n个元素的数组。对任一元素x，设S(x)=i|Ti=x。当|S(x)|n/2时，称x为T的主元素。如果T中元素存在序关系，按分治策略设计并实现一个线性时间算法，确定T0.n-1是否有一个主元素。二、 算法问题形式化表示若T 中存在主元素，则将T 分为两部分后，T 的主元素也必为两部分中至少一部分的主元素，因此可用分治法。将元素划分为两部分，递归地检查两部分有无主元素。算法如下：若T 只含一个元素，则此元素就是主元素，返回此数。将T 分为两部分T1 和T2（二者元素个数相等或只差一