算法设计大作业之寻找多数元素.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](1jn)比较时计数器为0，那么对于A[j+1…n]上的元素递归调用candidate过程。 算法如下： 三，程序代码： # include stdio.h # include stdlib.h 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;jn;j++) printf(%5d,num[j]); c=majority (num,n); if (c!=0) printf(\nand the most number is %d \n,c); else printf(\nbut the most number is not exsited); system(PAUSE); } int candidate(int A[],int m,int n) { c=A[m]; count=1; for(j=m+1;jncount0;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;i++) if (A[i]==c) count++; if (countn/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=25 return none candidate(1) j=1,c=A[1]=1,count j=1!=n=11 j=2,A[2]=2!=c=1,count=0 j=2!=n