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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 分子模拟 » Monte Carlo » 【转帖】集合相等的蒙特卡罗算法
11/1返回列表
查看: 1111  |  回复: 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返回列表
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[基金申请] 投票:  有多少人是今天查系统知道结果的？ +17 爱看书的可乐 2026-08-26 19/950 2026-08-30 16:34 by xiangy672
[基金申请] 国社科又开始会评了，不知道这次命运如何 +3 雨打竹帘 2026-08-30 4/200 2026-08-30 12:35 by 白大多亮
[公派出国] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +6 ASdOkHsho7FD 2026-08-28 8/400 2026-08-30 11:32 by l0VvVHGBGRLv
[考研] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +6 ASdOkHsho7FD 2026-08-28 9/450 2026-08-30 11:30 by l0VvVHGBGRLv
[基金申请] 29号明天会评吗 +3 笨笨唐 2026-08-28 3/150 2026-08-30 09:29 by cww8181
[基金申请] 麻烦专家们看看评委们的意见（F口面上） +6 gdd2018 2026-08-28 11/550 2026-08-30 08:58 by 超级无敌华子
[考博] 售SCI文章，我:8O5.5.1.O.54,科目齐全,可+急 +3 G6APbkg8SA6w 2026-08-29 4/200 2026-08-30 07:28 by ZPa0EcMwuECS
[硕博家园] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +3 gy1nBQXYQJqL 2026-08-29 6/300 2026-08-30 06:22 by ZPa0EcMwuECS
[考博] 售SCI一区T0P文章，我:8.O.55.1.O54,科目全,可伽急 +6 ASdOkHsho7FD 2026-08-28 10/500 2026-08-30 06:11 by ZPa0EcMwuECS
[论文投稿] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +4 gy1nBQXYQJqL 2026-08-29 4/200 2026-08-30 02:09 by ZPa0EcMwuECS
[基金申请] 中青基了要发朋友圈吗？ +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
[基金申请] 为什么到现在没收到通知？ +4 tannykie 2026-08-29 4/200 2026-08-29 17:14 by lmz0216
[基金申请] 申请删除本帖 +6 lyz123lyz 2026-08-27 7/350 2026-08-27 17:31 by 宁静致远sy
[基金申请] 基金未中，这种答复是模板吗？ +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
[基金申请] 为什么 国际(地区)合作与交流项目 没有放榜？ 10+3 majunge000 2026-08-26 11/550 2026-08-27 08:42 by 北京莱茵编辑
[基金申请] 国合可查了 +3 paperzjh 2026-08-26 3/150 2026-08-26 10:41 by LemmonTr
[基金申请] 某些机构，以效率低为荣，以效率低作为存在感 +9 yuleib84 2026-08-25 10/500 2026-08-25 17:14 by alexon
信息提示
关闭
请填处理意见
关闭