西电算法设计大作业.docVIP

算法设计----- 寻找多数元素 学号:020105020 姓名:林桥洲 (1)问题提出： 令A[1,2,…n]是一个整数序列，A中的整数a如果在A中出现的次数多余，那么a称为多数元素。例如在序列1,3,2,3,3,4,3中，3是多数元素，因为在7个元素中它出现了四次。有几个方法可以解决这个问题。蛮力方法是把每个元素和其他各个元素比较，并且对每个元素计数，如果某个元素的计数大于，就可以断定它是多数元素，否则在序列中就没有多数元素。但这样比较的次数是n(n-1)/2=Θ(),这种方法的代价太昂贵了。比较有效的算法是对这些元素进行排序，并且计算每个元素在序列中出现了多少次。这在最坏情况下的代价是Θ(n ).因为在最坏情况下，排序这一步需要Ω(n ) 。另外一种方法是寻找中间元素，就是第元素，因为多数元素在排序的序列中一定是中间元素。可以扫描这个序列来测试中间元素是否是多数元素。由于中间元素可以在Θ（n）时间内找到，这个方法要花费Θ（n）时间。 有一个漂亮的求解方法，它比较的次数要少得多，我们用归纳法导出这个算法，这个算法的实质是基于下面的观察结论。 观察结论：在原序列中去除两个不同的元素后，原序列的多数元素在新序列中还是多数元素。 这个结论支持下述寻找多数元素候选者的过程。将计数器置1，并令c=A[1]。从A[2]开始逐个扫描元素，如果被扫描的元素和c相等。则计数器加1，否则计数器减1.如果所有的元素都扫描完并且计数器的值大于0，那么返回c作为多数元素的候选者。如果在c和A[j](1jn)比较式计数器为0，那么对A[j+1,…n]上的过程调用candidate过程。算法的伪代码描述如下。 (2)算法 Input: An array A[1…n] of n elements; Output: The majority element if it exists; otherwise none; 1. c(candidate(1); 2. count(0; 3. for j(1 to n 4. if A[j]=c then count(count+1; 5. end for; 6. if count(n/2( then return c; 7. else return none; candidate(m) 1. j(m; c(A[m]; count(1; 2. while jn and count0 3. j (j+1; 4. if A[j]=c then count (count+1; 5. else count (count-1; 6. end while; 7. if j=n then return c; 8. else return candidate(j+1); （3）代码 #includestdio.h #includemalloc.h int majority(int*A,int n); int candidate(int m,int n); int*A; void main() { int i,d,n; printf(please input number n \n); scanf(%d,n); A=(int*)malloc(sizeof(int)*n); for(i=0;in;i++) scanf(%d,A[i]); d=majority(A,n); if(d!=-999) printf(the majority element is %d\n,d); else printf(the majority element do not exist\n); } int majority(int*A,int n) { int c,count,j; c=candidate(0,n); count=0; for(j=0;jn;j++) if(A[j]==c) count++; if(countn/2) return c; else return -999; } int candidate(int m,int n) { int j=m; int c=A[m]; int count=1; while(jncount0) { j=j+1; if(A[j]==c) count++; else count--; } if(j==n) return c; else return candidate(j+1,n); } （4）结果： 该程序的测试结果如下图,该程序能很高效且正确的找出多数元素 （5）设计实例 例如，首先输入数据的个数N