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

《算法设计大作业之寻找多数元素》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、寻找最大元素一，问题描述：令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，则计数

2、器减1;如果所有的元素都已经扫描完毕并且计数器大于0，那么返回c作为多数元素的候选者。如果在c和A[j](1#includeintcandidate(intA[],intm,intn);intmajority(intA[],intn);inti=1,count,c,j;voidmain(){intc,num[100],a,n,j;j=0;n=0;printf("pleas

3、einputthenumbersanduse'00'tostop(youcaninput100numbers)");while(1){scanf_s("%d",&a);if(a!=00){num[j]=a;j=j+1;n=n+1;}elsebreak;}printf("youhaveinputed%dnumberstotally",n);printf("thenumbersyouinputareasfollows");for(j=0;j

4、if(c!=0)printf("andthemostnumberis%d",c);elseprintf("butthemostnumberisnotexsited");system("PAUSE");}intcandidate(intA[],intm,intn){c=A[m];count=1;for(j=m+1;j0;j++){if(A[j]==c)count++;elsecount--;}if(j==n)returnc;elsereturncandidate(A,j+1,n);}intmajority(i

5、ntA[],intn){inti;c=candidate(A,0,n);for(i=0;in/2)returnc;elsereturn0;}代码运行结果如下：（1），没有最大元素的情况（2）有最大元素的情况四，递归过程展示：candidate(1)j=1,c=A[1]=1,count=1j=2,A[2]!=c=1,count=0j=2!=n=10candidate(3)j=3,c=A[3]=3,count=1j=4,A[4]=2!=c=3,count=0j=4!=n=1

6、0candidate(7)j=7,c=A[7]=8,count=1j=8,A[8]=2!=c=8,countj=8!=n=10candidate(9)j=9,c=A[9]=5,count=1j=10,A[10]=2!=c=5,count=0j=10=n=10,returnc=5majority:c=candidate(1)=5count=0j=1toncount=2count=2<5returnnonecandidate(1)j=1,c=A[1]=1,countj=1!=n=11j=2,A[2]=2!=c=1,count=0j=2!=n=

7、11candidate(3)j=3,c=A[3]=5,count=1j=4,A[4]=8!=c=5,count=0j=4!=n=11candidate(5)j=5,c=A[5]=5,count=1j=6,A[6]=5=c,count=2j=7,A[7]=5=c,count=3j=8,A[8]=98!=c=5,count=2j=9,A[9]=65!=c=5,count=1j=10,A[10]=5=c,count=2j=11,A[11]=5,count=3j=11=nreturn5majorityc=candidate(1)=5count=0

8、forj=1to11count=6count=6>5returnc=5