西电算法大作业,寻找多数元素

寻找多数元素的算法试验报告

一． 问题描述

令A[1...n]是一个整数序列，A中的整数a如果在A中出现的次数多于 n/2 ，那么a称为多数元素。例如，在序列1,3,2,3,3,4,3中，3是多数元素，因为7个元素中它出现4次。现在我们就要讨论如何利用计算机来找出一个序列中的多数元素，当然这个多数元素要么不存在，要么就只有一个。

二． 算法描述

有几种方法可以解决这个问题，蛮力方法就是把序列中的每个元素和其他每个元素比较，并且对每个元素计数，如果某个元素的计数大于 n/2 ，就可以断言它是多数元素；否则，在序列中就没有多数元素。但是这样的比较次数是n(n 1)/2 (n2)，这种方法的代价太昂贵。 另一种比较有效的算法是先对这些元素排序，并且计算每个元素在序列中出现多少次。这在最坏情况下的代价是 (nlogn)。因为在最坏情况下，排序这一步需要 (nlogn)次比较（选择合并排序或者快速排序）。 还有一种方法就是先对序列排序，再寻找中间元素，就是第 n/2 元素。因为多数元素，在排序的序列中一定是中间元素，可以扫描这个序列来测试中间元素是否确实是多数元素。由于多数元素可以在 (n)的时间内找到，这个方法要花费 (n)的时间，但是对于大数据量的序列，中项寻找算法的时间花费非常大，并且算法很复杂。

上述的几种方法都存在各种弊端，这里我们讨论一种非常漂亮的算法，它用的比较次数要少得多。在介绍这种由归纳法导出的递归算法之前，我们首先需要了解一个观察结论：

在原序列中去除两个不同的元素后，那么在原序列中的多数元素在新序列中还是多数元素。

这个观察结论支持下述寻找多数元素候选者的过程。将计数器置1，并令c A[1]，从c A[逐个地扫描元素，如果被扫描的元素和c相2]开始，

等，则计数器加1；如果元素不等于c，则计数器减1；如果所有的元素都已经扫描完毕并且计数器大于0，那么返回c作为多数元素的候选者（注

意：这里得到的仅仅是候选者，是否是真正的多数元素还有待验证）。如果在c和A[j](1 j n)比较时计数器为0，那么返回对于A[j 1...n]上的元素递归调用上述candidate过程。这里减少计数器就是观察结论中所述去除两个不同元素的思想的实现。

得到候选者以后，我们需要验证其正确性。这时候计数器置0，我们把得到的候选者c与原序列中的元素一个个一次比较，相等则计数器加1，比较结束后，如果计数器的值大于 n/2 ，则候选者是真正的多数元素，否则不是。

算法MAJORITY描述如下：

输入：n个元素的数组A[1...n]。

输出：若存在多数元素，则输出；否则输出none。

1.c candidate(1)

2.count 0

3.forj 1ton

4.ifA[j] cthencount count 1

5.endfor

6.ifcount n/2 thenreturnc

7.elsereturnnone

过程candidate(m)

1.j m;c A[m];count 1

2.whilej nandcount 0

3.

4.

5.j j 1ifA[j] cthencount count 1elsecount count 1

6.endwhile

7.ifj nthenreturnc

8.elsereturncandidate(j 1)

三． 源代码

解决这个问题的源代码如下：

#include<stdio.h>

#include<stdlib.h>

int candidate(int *A, int n, int m) //寻找A[m...n]中多数元素候选者

{

int j=m;

int c=A[m];//让c的值为判断区域的起点

int count=1;//计数器置1

while((j<n)&&(count>0))//执行循环的条件

{

j++;

if(A[j]==c)

count++;//如果后面的数据和起点值相等，计数器自增

else count--;//如果不相等则计数器自减，计数器为0时退出循环 }

if(j==n)

return c;//如果循环到判断区域终点则返回最后一次递归的起点值，这即是候选者

else return candidate(A,n,j+1);//对A[j+1...n]寻找多数元素候选者，即却掉了前面两个不等的值，继续在后面的区间内寻找候选者

}

int Majority(int *A,int n)//检查候选者是否真的是多数元素

{

int count=0;

int c=candidate(A,n,0);//首先调用寻找候选者的函数，得到候选者

for(inti=0;i<n;i++)

if(A[i]==c)

count++;//A[i]在寻找候选元素函数中被赋值，即如果数组中与候选元素相等的元素过半数即是主元素

if(count>n/2)return c;//并返回其值

else return ' '; //如果不存在多数元素，则返回空格

}

void main()

{

int *A,i,m,n,k;

printf("请输入数组大小:");

scanf("%d",&n);

A=(int *)malloc(sizeof (int)*n);//分配存储数组A的动态空间

printf("\n请输入%d个数据:\n",n);

for(i=0;i<n;i++)

scanf("%d",&A[i]);//给数组A赋值

if(Majority(A,n)==' ')//如果函数Majority返回值为空格

printf("\n该数组中不存在多数元素！\n");

else

printf("\n该数组中的多数元素为：%d\n",Majority(A,n));

free(A);

}

四． 运行过程

示例结果

1.

2.

以例1来说明程序运行过程：

第一趟：j m 0,c A[0] 1,count 1，满足循环条件，j 0 1 1，因为A[1] 3 c，所以count 1 1 0，不满足循环条件且j n，返回candidate(2)。

第二趟：j m 2,c A[2] 2,count 1，满足循环条件，j 2 1 3，因为A[3] 3 c，所以count 1 1 0，不满足循环条件且j n，返回candidate(4)。

第三趟：j m 4,c A[4] 3,count 1，满足循环条件，j 4 1 5，因为A[5] 4 c，所以count 1 1 0，不满足循环条件且j n，返回candidate(6)。

第四趟：j m 6,c A[6] 3,count 1，满足循环条件，j 6 1 7 n，循环结束，返回候选者c的值3。

递归结束，执行检验程序Majority，发现count 4 n/2 3，所以得到原序列的多数元素3，输出结果，程序结束。