文档介绍：算法设计-----寻找多数元素学号:020105020姓名:林桥洲(1)问题提出:令A[1,2,…n]是一个整数序列,A中的整数a如果在A中出现的次数多余,那么a称为多数元素。例如在序列1,3,2,3,3,4,3中,3是多数元素,因为在7个元素中它出现了四次。有几个方法可以解决这个问题。蛮力方法是把每个元素和其他各个元素比较,并且对每个元素计数,如果某个元素的计数大于,就可以断定它是多数元素,否则在序列中就没有多数元素。但这样比较的次数是n(n-1)/2=Θ(n2),这种方法的代价太昂贵了。比较有效的算法是对这些元素进行排序,并且计算每个元素在序列中出现了多少次。这在最坏情况下的代价是Θ(nlogn).因为在最坏情况下,排序这一步需要Ω(nlogn)。另外一种方法是寻找中间元素,就是第元素,因为多数元素在排序的序列中一定是中间元素。可以扫描这个序列来测试中间元素是否是多数元素。由于中间元素可以在Θ(n)时间内找到,这个方法要花费Θ(n)时间。个人收集整理勿做商业用途有一个漂亮的求解方法,它比较的次数要少得多,我们用归纳法导出这个算法,这个算法的实质是基于下面的观察结论。个人收集整理勿做商业用途观察结论:在原序列中去除两个不同的元素后,原序列的多数元素在新序列中还是多数元素。这个结论支持下述寻找多数元素候选者的过程。将计数器置1,并令c=A[1]。从A[2]开始逐个扫描元素,如果被扫描的元素和c相等。则计数器加1,,那么返回c作为多数元素的候选者。如果在c和A[j](1<j<n)比较式计数器为0,那么对A[j+1,…n]上的过程调用candidate过程。算法的伪代码描述如下。个人收集整理勿做商业用途(2)算法Input:AnarrayA[1…n]ofnelements;Output:Themajorityelementifitexists;otherwisenone;¬candidate(1);¬0;¬[j]=cthencount¬count+1;;>ën/2ûthenreturnc;;candidate(m)¬m;c¬A[m];count¬1;<nandcount>¬j+1;[j]=cthencount¬count+1;¬count-1;;=nthenreturnc;(j+1);(3)代码#include<>#include<>intmajority(int*A,intn);intcandidate(intm,intn);int*A;voidmain(){ inti,d,n;printf("pleaseinputnumbern\n"); scanf("%d",&n); A=(int*)malloc(sizeof(int)*n); for(i=0;i<n;i++) scanf("%d",&A[i]); d=majority(A,n); if(d!=-999) printf("themajorit