wizen-coder
10/5/2018 - 1:55 AM

设T[1:n]是一个含有n个元素的数组。当|{i|T[i]=x}|>n/2时，称元素x是数组T的主元素。 例如：数组T[]={5,5,5,5,5,5,1,3,4,6}中，元素T[0:5]为数组T[]的主元素。

设T[1:n]是一个含有n个元素的数组。当|{i|T[i]=x}|>n/2时，称元素x是数组T的主元素。 例如：数组T[]={5,5,5,5,5,5,1,3,4,6}中，元素T[0:5]为数组T[]的主元素。

MajorityMC.cpp
content_copyfile_download
//随机化算法 蒙特卡罗算法 主元素问题
#include "stdafx.h"
#include "RandomNumber.h"
#include <cmath>
#include <iostream>
using namespace std;
 
//判定主元素的蒙特卡罗算法
template<class Type>
bool Majority(Type *T,int n)
{
	RandomNumber rnd;
	int i = rnd.Random(n);
 
	Type x = T[i];	//随机选择数组元素
	int k = 0;
 
	for(int j=0; j<n; j++)
	{
		if(T[j] == x)
		{
			k++;
		}
	}
 
	return (k>n/2);	//k>n/2时，T含有主元素
}
 
//重复k次调用算法Majority
template<class Type>
bool MajorityMC(Type *T,int n,double e)
{
	int k = ceil(log(1/e)/log((float)2));
	for(int i=1; i<=k; i++)
	{
		if(Majority(T,n))
		{
			return true;
		}
	}
	return false;
}
 
int main()
{
	int n = 10;
	float e = 0.001;
	int a[] = {5,5,5,5,5,5,1,3,4,6};
	cout<<"数组a的元素如下："<<endl;
	for(int i=0; i<10; i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
	cout<<"调用MajorityMC判断数组是否含有主元素结果是："<<MajorityMC(a,n,e)<<endl;
}