24小时热门版块排行榜

返回列表

zyj8119

木虫 (著名写手)

模拟EPI: 10
应助: 65 (初中生)
贵宾: 0.003
金币: 915.1
散金: 1440
红花: 35
帖子: 2936
在线: 1329.4小时
虫号: 664177
注册: 2008-11-29
性别: GG
专业: 理论和计算化学

[交流] 【转帖】集合相等的蒙特卡罗算法

CODE:

#include

#include

#include

#include

//============随机数类=================

const unsigned long maxshort=65536L;

const unsigned long multiplier=1194211693L;

const unsigned long adder=12345L;

class RandomNumber

{

 private:

  unsigned long randSeed;  //当前种子

 public:

  RandomNumber(unsigned long s=0);  //构造函数，缺省值0表示有系统自动产生种子

  unsigned short Random(unsigned long n); //产生0:n-1之间的随机整数

  double fRandom(void);   //产生[0，1)之间的随机实数

};

RandomNumber::RandomNumber(unsigned long s)

{//产生种子

 if(s==0)

  randSeed=time(0);  //用系统时间产生种子

 else

  randSeed=s;        //由用户提供种子

}

unsigned short RandomNumber::Random(unsigned long n)

{//产生0:n-1之间的随机整数

    randSeed = multiplier * randSeed + adder;

 return(unsigned short)((randSeed>>16) % n);

}

double RandomNumber::fRandom(void)

{//产生(0，1)之间的随机实数

 return Random(maxshort)/double(maxshort);

}

//===================================================

//=============合并排序算法====================

template 

void Merge(T *c,T *d,int l,int m,int r)

{

 int i=l,

  j=m+1,

  k=l;

 while((i<=m)&&(j<=r))

  if (c <=c[j]) d[k++]=c[i++];

  else d[k++]=c[j++];

 if(i>m) for (int q=j;q<=r;q++)

    d[k++]=c[q];

 else for(int q=i;q<=m;q++)

  d[k++]=c[q];

}

template 

void MergePass(T *x,T *y,int s,int n)

{

 int i=0;

 while(i<=n-2*s)

 {

  Merge(x,y,i,i+s-1,i+2*s-1);

  i=i+2*s;

 }

 if (i+s
 else for(int j=i;j<=n-1;j++)

   y[j]=x[j];

}

template 

void MergeSort(T *a,int n)

{

 T * b = new T[n];

 int s=1;

 while (s
 {

  MergePass(a,b,s,n);

  s+=s;

  MergePass(b,a,s,n);

  s+=s;

 }

}

//==============二分查找算法==================

template 

int BinarySearch(T *a, const T & x,int n)

{//在a[0]<=a[1]<= ... <=a[n-1]中搜索x,找到返回其位置，否则返回-1

 int left=0;int right=n-1;

 while(left <=right)

 {

  int middle=(left+right)/2;

  if(x == a[middle]) return middle;

  if(x > a[middle]) 

   left=middle+1;

  else

   right=middle-1;

 }

 return -1;//未找到x

}

//=========判断两个集合相等的蒙特卡罗算法==============

bool Equal(int *S,int *T,int n)

{//判断两个集合相等的蒙特卡罗算法

 static RandomNumber rnd;

 int i= rnd.Random(n);    //从集合T中随机选择一个元素，判断它是否在集合S中，

// cout << T <
    if (BinarySearch(S,T,n)==-1) return false;  //不在,返回false,即集合不相等

 return true;   //在,返回true，即集合相等

}

bool EqualMC(int *S,int *T,int n,double e)

{//重复多次调用算法Equal,确保错误率小于e

    int k= int(ceil(log(e)/log(double(n-1)/double(n))));

// cout <<"k="<< k<
 for(int i=1;i<=k;i++)

 {

//  cout <  ";

  if (!Equal(S,T,n)) 

  {

//   cout <
   return false;

  }

 }

 return true;

}

int main()

{

 int n;  //集合的元素的个数

 int * S,*T; //待比较的两个集合

 int i;

 ifstream InFile("input.txt",ios::nocreate); //读取input.txt

 if(InFile.fail()) //读取文件失败

 {

  cout<<"the input.txt is not exist!"<
  return(1);

 }

 InFile >> n ;  //集合的元素的个数

 S=new int [n];

    for( i=0; i> S;  //集合S的各元素

 T=new int [n];

    for( i=0; i> T;  //集合T的各元素

 InFile.close();

 //将集合S的元素进行排序预处理

 MergeSort(S,n);

 //cout <<"OK Sort"<
// for (i=0;i
// cout <

///*    

 ofstream OutFile("output.txt");

 double e=0.001;  //错误的概率

 if (EqualMC(S,T,n,e))

  OutFile <<"YES";

 else

  OutFile <<"NO";

 delete []S;

 delete []T;

 return 0;

//*/

/*

//=========测试用，连续判断m次，看得到的结果正确的次数和错误的次数

 int a=0,b=0,m=1;

 double e=0.01;

 for(i=1;i<=m;i++)

 {

  if (EqualMC(S,T,n,e))

   a++;

  else

   b++;

 }

 cout <<"Yes " <
    cout <<"NO  " <
//============================================================== 

*/

/*

//==========产生测试用数据===================

 ofstream OutFile("input.txt");

 n=10000;

 OutFile<< n<
    for( i= 0 ;i
 OutFile<
    for( i= 0 ;i
 OutFile<
//=========================================

*/

}

le e=0.01;

 for(i=1;i<=m;i++)

 {

  if (EqualMC(S,T,n,e))

   a++;

  else

   b++;

 }

 cout <<"Yes " <
    cout <<"NO  " <
//============================================================== 

*/

/*

//==========产生测试用数据===================

 ofstream OutFile("input.txt");

 n=10000;

 OutFile<< n<
    for( i= 0 ;i
 OutFile<
    for( i= 0 ;i
 OutFile<
//=========================================

*/

}