蒙特卡罗算法--主元素问题

用蒙特卡罗算法求解数组主元素问题

蒙特卡罗算法：关键在于概率的分析计算，其理论基础是概率论

下面是实现数组主元素问题的方法

// MonteCarlo.cpp : 定义控制台应用程序的入口点。
#include "stdafx.h"
#include "targetver.h"
#include <stdio.h>
#include <tchar.h>
#include "stdafx.h"
#include"iostream"
#include<math.h>
#include<time.h>
#include<iomanip>
using namespace std;
const unsigned long maxshort=65535L;
const unsigned long multiplier=1194211693L;
const unsigned long adder=12345L;
class RandomNumber{
private:
 //当前种子
 unsigned long randSeed;
public:
 //构造函数
 RandomNumber(unsigned long s=0);
 unsigned short Random(unsigned long n);
 double fRandom();
};

RandomNumber::RandomNumber(unsigned long s)
{
 if(s==0)
  randSeed=time(0);
 else
  randSeed=s;
}

double RandomNumber::fRandom()
{
 return Random(maxshort)/double(maxshort);
}

unsigned short RandomNumber::Random(unsigned long n)
{
 randSeed=multiplier*randSeed+adder;
 return (unsigned short)((randSeed>>16)%n);
}

RandomNumber rnd;

bool Majority(int *T,int n)
{
 //判定主元素的蒙特卡罗算法
 int i=rnd.Random(n);
 int x=T[i];
 int k=0;
 for(int j=0;j<n;j++)
  if(T[j]==x)
   k++;
 if(k>n/2)
 {
  cout<<"主元素是："<<x<<endl;
  return true;
 }
 else
  return false;

}

bool MajorityMC(int *T,int n,double e)
{
 //重复调用算法Majority
 int k=ceil(log(1.0/e)/log(2.0));//依概率产生的最大重复计算次数
 for(int i=1;i<=k;i++)
  if(Majority(T,n))
   return true;
 return false;
}

int _tmain(int argc, _TCHAR* argv[])
{
 int arr[10]={7,7,2,4,7,4,7,7,7,8};
    MajorityMC(arr,10,0.1);
 int a;
 cin>>a;
 return 0;
}