寻找多数元素(递归分析)

寻找多数元素(递归分析)

ID:43845588

大小:362.90 KB

页数:5页

时间:2019-10-15

寻找多数元素(递归分析)_第1页
寻找多数元素(递归分析)_第2页
寻找多数元素(递归分析)_第3页
寻找多数元素(递归分析)_第4页
寻找多数元素(递归分析)_第5页
资源描述:

《寻找多数元素(递归分析)》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

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)/22=()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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。