算法设计大作业之寻找多数元素.doc

寻找最大元素一，问题描述： 令A[1…n]是一个整数序列，A中的整数a如果在A中出现的次数多于，那么a称为多数元素例如，在序列1,3,2,3,3,4,3中，3是多数元素，因为7个元素中它出现的次数为4，大于3设计一个性能比较优异的算法求解这个问题二，算法描述：本算法得益于这样一个观察结论：在原序列中去除两个不同的元素以后，原序列中的多数元素在新的序列中还是多数元素此结论的数学证明省略本算法的语言描述如下：将计数器置1，并令c=A[1]，从A[2]开始，逐个的扫描元素，如果被扫描的元素和c相等，则计数器加1；若果元素不等于c，则计数器减1;如果所有的元素都已经扫描完毕并且计数器大于0，那么返回c作为多数元素的候选者如果在c和A[j](1# include int candidate(int A[],int m,int n);int majority (int A[],int n);int i=1,count,c,j;void main(){ int c,num[100],a,n,j; j=0;n=0; printf("please input the numbers and use '00' to stop (you can input 100 numbers) \n"); while(1) { scanf_s("%d",&a); if (a!=00) { num[j]=a; j=j+1; n=n+1; } else break; } printf("you have inputed %d numbers totally",n); printf("\nthe numbers you input are as follows\n"); for(j=0;j0;j++) { if(A[j]==c) count++; else count--; } if (j==n) return c; else return candidate(A,j+1,n);}int majority (int A[],int n){ int i; c=candidate(A,0,n); for (i=0;in/2) return c; else return 0;}代码运行结果如下：（1），没有最大元素的情况（2）有最大元素的情况四，递归过程展示： candidate(1) j=1,c=A[1]=1,count=1 j=2,A[2]!=c=1,count=0 j=2!=n=10 candidate(3) j=3,c=A[3]=3,count=1 j=4,A[4]=2!=c=3,count=0 j=4!=n=10 candidate(7) j=7,c=A[7]=8,count=1 j=8,A[8]=2!=c=8,count j=8!=n=10 candidate(9) j=9,c=A[9]=5,count=1 j=10,A[10]=2!=c=5,count=0 j=10=n=10,return c=5 majority: c=candidate(1)=5 count=0 j=1 to n count=2 count=2<5 return nonecandidate(1) j=1,c=A[1]=1,count j=1!=n=11 j=2,A[2]=2!=c=1,count=0 j=2!=n=11 candidate(3) j=3,c=A[3]=5,count=1 j=4,A[4]=8!=c=5,count=0 j=4!=n=11 candidate(5) j=5,c=A[5]=5,count=1 j=6,A[6]=5=c,count=2 j=7,A[7]=5=c,count=3 j=8,A[8]=98!=c=5,count=2 j=9,A[9]=65!=c=5,count=1 j=10,A[10]=5=c,count=2 j=11,A[11]=5,count=3 j=11=n return 5majority c=candidate(1)=5 count=0 for j=1 to 11 count=6count=6>5return c=5。