资源描述:
《寻找多数元素(递归分析)》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、寻找多数元素算法设计技巧与分析----------寻找多数元素姓名:张俊飞学号:021050581寻找多数元素寻找多数元素一、问题描述令A[1…n]是一个整数序列,A中的整数a如果在A中出现的此书多于n/2,那么a称为多数元素。例如,在序列1,3,2,3,3,4,3中,3是多数元素,因为7个元素中它出现4次。有多种方法可以解决此问题。蛮力的方法是把每个元素和其他元素比较,并且对每个元素计数,若某个元素的计数大于n/2,就可以断言它为多数元素;否则在序列中就没有多数元素。但是这样的比较次数是nn(1)/22=()n,这种方法的代价太大。所以
2、我们希望找一个更好的解法,我们用归纳法导出如下这个算法。二、算法描述首先提出一个观察结论,观察结论:在原序列中去除两个不同的元素后,那么在原序列中的多数元素在新序列中还是多数元素。这个观察结论支持下述寻找多数元素候选者的过程:算法Majority输入:n个元素的数组A[1…n]。输出:若存在多数元素,则输出;否则输出none。1.c←candidate(1)2.count←03.forj←1ton4.ifA[j]=cthencount←count+15.endfor6.ifcount>n/2thenreturnc7.elsereturnnon
3、e过程:candidate(m)1.j←m;c←A[m];count←12.whilej03.j←j+14.ifA[j]=cthencount←count+15.elsecount←count+16.endwhile7.ifj=nthenreturnc2寻找多数元素8.elsereturncandidate(j+1)三、代码及运行结果1、代码#include#includeintMajority(intn);intcandidate(int*A,intm,intn);voidmain
4、(){intd;intn;printf("pleaseinputthetotalofthenumberyouwanttoinput:");scanf("%d",&n);d=Majority(n);if(d!=-1){printf("thereisamajorityelement:");printf("%d",d);}elseprintf("thereisnoexistmajorityelement");}intMajority(intn){int*A;intc,i,j;intcount=0;A=(int*)malloc(sizeo
5、f(int)*n);for(i=0;in/2)returnc;elsereturn-1;}3寻找多数元素intcandidate(int*A,intm,intn){intj=m;intc=A[m];
6、intcount=1;while((j0)){j=j+1;if(A[j]==c)count=count+1;elsecount=count-1;}if(j==n-1)returnc;elsereturncandidate(A,j+1,n);}2、运行结果在MicrosoftvisualC++6.0中运行结果如下:图1成功找到多数元素示例图2没有多数元素的数组示例四、递归过程分析以A[0…8]={1,3,2,3,4,4,3,3,3}为例.j=0c=A[0]=1,count=1j=1,A[j]=3!=c,count=0
7、j!=8,candidate(2)j=2c=A[2]=2,count=1j=3,A[j]=3!=c,count=04寻找多数元素j!=8,candidate(4)j=4c=A[4]=4,count=1j=5,A[5]=4=c,count=2j=6,A[6]=3!=c,count=1j=7A[7]=3!=c,count=0j!=8,candidate(8)j=8c=A[8]=3,count=1j=8,returnc=3综上所述,本例程四次递归。且总终的多数元素候选者位3,再经程序后半段判断,认为3的确是多数元素。5