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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 分子模拟 » Monte Carlo » 【转帖】集合相等的蒙特卡罗算法
11/1返回列表
查看: 1112  |  回复: 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.55.1.O.5.4,科目齐全,可+急 +3 jCd0dEvKHShX 2026-08-29 5/250 2026-08-30 19:23 by hZiFeudZyoGR
[硕博家园] 售SCI一区T0P文章，我:8O.55.1.O.5.4,科目齐全,可+急 +3 G6APbkg8SA6w 2026-08-29 4/200 2026-08-30 18:53 by hZiFeudZyoGR
[考研] 售SCI一区T0P文章，我:8O.55.1.O.54,科目全,可伽急 +3 G6APbkg8SA6w 2026-08-29 5/250 2026-08-30 18:40 by hZiFeudZyoGR
[考博] 售SCI-T0P文章，我:8O.5.5.1.O.54,科目齐全,可+急 +4 gy1nBQXYQJqL 2026-08-29 5/250 2026-08-30 17:56 by hZiFeudZyoGR
[硕博家园] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +4 gy1nBQXYQJqL 2026-08-29 7/350 2026-08-30 17:45 by hZiFeudZyoGR
[找工作] 售SCI文章，我:8O5.5.1.O.54,科目齐全,可+急 +6 ASdOkHsho7FD 2026-08-28 10/500 2026-08-30 17:36 by hZiFeudZyoGR
[公派出国] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +7 ASdOkHsho7FD 2026-08-28 9/450 2026-08-30 17:34 by hZiFeudZyoGR
[硕博家园] 售SCI一区T0P文章，我:8.O55.1.O.54,科目全,可十急 +7 ASdOkHsho7FD 2026-08-28 14/700 2026-08-30 17:01 by hZiFeudZyoGR
[基金申请] 面上意见出来了 +9 黄鸟于飞Chao 2026-08-29 18/900 2026-08-30 16:47 by 黄鸟于飞Chao
[基金申请] 29号明天会评吗 +3 笨笨唐 2026-08-28 3/150 2026-08-30 09:29 by cww8181
[基金申请] 中青基了要发朋友圈吗？ +4 349506619 2026-08-28 4/200 2026-08-29 22:41 by alongwaytogo
[基金申请] 国社科申报系统有变化 +3 kynobel 2026-08-23 3/150 2026-08-29 21:57 by 余韵清
[基金申请] 国自然面上复盘~欢迎讨论 (金币+15) +15 晴天加油 2026-08-26 16/800 2026-08-29 18:28 by symmetry
[教师之家] 导师吐槽：我怎么摊上了这么个极品研究生！ +9 苏东坡二世 2026-08-23 9/450 2026-08-29 14:41 by hustersqt
[基金申请] 为什么资助数各大高校都创新高，自己申请怎么就这么难 +12 Kittylucky 2026-08-27 13/650 2026-08-29 00:04 by superceng
[基金申请] 基金未中，这种答复是模板吗？ +5 zhaosm1982 2026-08-27 6/300 2026-08-27 16:00 by lfy8008
[文学芳草园] 梦想 +3 myrtle 2026-08-26 3/150 2026-08-27 10:01 by angelyueyi
[基金申请] 明天应该可查了！？ +6 chengyan1220 2026-08-23 6/300 2026-08-25 19:45 by zfd97
[基金申请] 某些机构，以效率低为荣，以效率低作为存在感 +9 yuleib84 2026-08-25 10/500 2026-08-25 17:14 by alexon
[基金申请] 没有任何消息-是不是就凉了 +9 图啦图啦 2026-08-24 10/500 2026-08-25 11:59 by 南海小哥
信息提示
关闭
请填处理意见
关闭