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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 分子模拟 » Monte Carlo » 【转帖】集合相等的蒙特卡罗算法
11/1返回列表
查看: 1059  |  回复: 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返回列表
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 一志愿西南交大，求调剂 +4 材化逐梦人 2026-03-18 4/200 2026-03-18 14:22 by 007_lilei
[考研] 0703化学调剂 +4 pupcoco 2026-03-17 7/350 2026-03-18 12:14 by djl2006
[考研] 303求调剂 +4 睿08 2026-03-17 6/300 2026-03-18 11:01 by Iveryant
[考研] 301求调剂 +9 yy要上岸呀 2026-03-17 9/450 2026-03-18 08:58 by 无际的草原
[基金申请] 被我言中：新模板不强调格式了，假专家开始管格式了 +4 beefly 2026-03-14 4/200 2026-03-17 22:04 by 黄鸟于飞Chao
[考研] 326求调剂 +5 上岸的小葡 2026-03-15 6/300 2026-03-17 17:26 by ruiyingmiao
[考研] 考研化学学硕调剂，一志愿985 +4 张vvvv 2026-03-15 6/300 2026-03-17 17:15 by ruiyingmiao
[考研] 一志愿苏州大学材料工程（085601）专硕有科研经历三项国奖两个实用型专利一项省级立项 +6 大火山小火山 2026-03-16 8/400 2026-03-17 15:05 by 无懈可击111
[考研] 一志愿南京大学，080500材料科学与工程，调剂 +4 Jy? 2026-03-16 4/200 2026-03-17 11:02 by gaoqiong
[考研] 283求调剂 +3 听风就是雨； 2026-03-16 3/150 2026-03-17 07:41 by 热情沙漠
[考研] 070300化学学硕求调剂 +6 太想进步了0608 2026-03-16 6/300 2026-03-16 16:13 by kykm678
[考研] 0856求调剂 +3 刘梦微 2026-03-15 3/150 2026-03-16 10:00 by houyaoxu
[考研] 294求调剂 +3 Zys010410@ 2026-03-13 4/200 2026-03-15 10:59 by zhq0425
[考研] 中科大材料专硕319求调剂 +3 孟鑫材料 2026-03-13 3/150 2026-03-14 18:10 by houyaoxu
[考研] 招收0805（材料）调剂 +3 18595523086 2026-03-13 3/150 2026-03-14 00:33 by 123%、
[考研] 工科材料085601 279求调剂 +8 困于星晨 2026-03-12 10/500 2026-03-13 15:42 by ms629
[考研] 290求调剂 +7 ADT 2026-03-12 7/350 2026-03-13 15:17 by JourneyLucky
[考研] 274求调剂 +3 S.H1 2026-03-12 3/150 2026-03-13 15:15 by JourneyLucky
[考研] 328化工专硕求调剂 +4 。，。，。，。i 2026-03-12 4/200 2026-03-13 14:44 by JourneyLucky
[考研] 070303一志愿西北大学学硕310找调剂 +3 d如愿上岸 2026-03-13 3/150 2026-03-13 10:43 by houyaoxu
信息提示
关闭
请填处理意见
关闭