应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 分子模拟 » Monte Carlo » 【转帖】集合相等的蒙特卡罗算法
11/1返回列表
查看: 1123  |  回复: 0
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

zyj8119

木虫 (著名写手)

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

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< //=========================================
*/

}

[ Last edited by zyj8119 on 2010-10-17 at 01:27 ]
回复此楼

» 猜你喜欢
好好学习，天天向上。
1楼 2010-10-17 01:25:03
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

智能机器人

Robot (super robot)

我们都爱小木虫

找到一些相关的精华帖子，希望有用哦~

科研从小木虫开始，人人为我，我为人人
相关版块跳转 我要订阅楼主 zyj8119 的主题更新
11/1返回列表
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[基金申请] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +3 uKOSCocCb6Fm 2026-11-13 3/150 2026-11-15 04:16 by xSrQNSSjcgoX
[考博] 售SCI文章，我:8O5.5.1.O.54,科目齐全,可+急 +3 uKOSCocCb6Fm 2026-11-12 7/350 2026-11-15 03:32 by xSrQNSSjcgoX
[硕博家园] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +7 0TEMgxdT1eIw 2026-11-09 10/500 2026-11-15 00:39 by Equinoxhua
[基金申请] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +6 FChKX8meu1ds 2026-11-09 8/400 2026-11-15 00:35 by Equinoxhua
[考研] 售SCI一区T0P文章，我:8.O.55.1.O54,科目全,可伽急 +6 FChKX8meu1ds 2026-11-09 9/450 2026-11-14 22:39 by Equinoxhua
[基金申请] 售SCI-T0P文章，我:8O.5.5.1.O.54,科目齐全,可+急 +3 XJXMuRjD7cK7 2026-11-13 3/150 2026-11-13 23:37 by 6PrO1XyZ5URF
[考博] 考博求助 10+3 社会实践对别 2026-11-08 3/150 2026-11-13 14:04 by 沐小虫252
[考研] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +8 zSbvVX9JFl9J 2026-11-09 9/450 2026-11-13 11:11 by Equinoxhua
[基金申请] 售SCI一区T0P文章，我:8O.55.1.O.54,科目全,可伽急 +6 C6CRn66RYYXS 2026-11-10 7/350 2026-11-13 10:55 by Equinoxhua
[教师之家] 售SCI-T0P文章，我:8O.5.5.1.O.54,科目齐全,可+急 +6 C6CRn66RYYXS 2026-11-10 6/300 2026-11-13 04:21 by Equinoxhua
[基金申请] 售SCI一区T0P文章，我:8.O55.1.O.54,科目全,可十急 +4 Z7qfCsdIiD1T 2026-11-11 5/250 2026-11-12 11:44 by HajghKOMynmz
[考博] 售SCI一区T0P文章，我:8.O55.1.O.54,科目全,可十急 +3 Z7qfCsdIiD1T 2026-11-10 5/250 2026-11-12 11:25 by HajghKOMynmz
[教师之家] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +4 Z7qfCsdIiD1T 2026-11-10 9/450 2026-11-12 11:22 by HajghKOMynmz
[硕博家园] 售SCI一区T0P文章，我:8O.55.1.O.5.4,科目齐全,可+急 +4 Z7qfCsdIiD1T 2026-11-10 6/300 2026-11-12 11:22 by HajghKOMynmz
[教师之家] 售SCI一区T0P文章，我:8.O.55.1.O54,科目全,可伽急 +5 czAiolzR0IJC 2026-11-10 7/350 2026-11-12 11:09 by HajghKOMynmz
[基金申请] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +4 czAiolzR0IJC 2026-11-10 8/400 2026-11-12 11:00 by HajghKOMynmz
[考博] 售SCI一区T0P文章，我:8O.55.1.O.5.4,科目齐全,可+急 +6 YHiw1gou1Eda 2026-11-10 6/300 2026-11-12 10:08 by HajghKOMynmz
[教师之家] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +3 TgvkbZZl9tqB 2026-11-11 3/150 2026-11-12 08:26 by HajghKOMynmz
[教师之家] 售SCI文章，我:8O5.5.1.O.54,科目齐全,可+急 +4 C6CRn66RYYXS 2026-11-10 4/200 2026-11-12 06:03 by 9fOTqj074tIg
[考博] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +6 zSbvVX9JFl9J 2026-11-09 9/450 2026-11-12 04:57 by 9fOTqj074tIg
信息提示
关闭
请填处理意见
关闭