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

24小时热门版块排行榜    

Znn3bq.jpeg
小木虫论坛-学术科研互动平台 » 计算模拟区 » 分子模拟 » Monte Carlo » 【转帖】集合相等的蒙特卡罗算法
北京石油化工学院2026年研究生招生接收调剂公告
11/1返回列表
查看: 1066  |  回复: 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返回列表
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 285求调剂 +5 恶法大二的气味� 2026-04-05 8/400 2026-04-07 23:37 by shanqishi
[考研] 求调剂 +11 wwwwabcde 2026-04-07 11/550 2026-04-07 23:16 by JourneyLucky
[考研] 土木水利专硕276分求调剂 +4 我想上学！！6 2026-04-05 7/350 2026-04-07 22:10 by Delta2012
[考研] 270分求调剂 +6 maxjxbsk 2026-04-01 6/300 2026-04-07 12:53 by flydream1314
[考研] 材料334求调剂 +19 Eecho# 2026-04-03 19/950 2026-04-06 08:37 by 小小树2024
[考研] 085500机械专硕初试288求调剂 +3 GZJguo666- 2026-04-05 3/150 2026-04-05 18:06 by jkddd
[考研] 083200 333求调剂 +3 十二！！ 2026-04-04 3/150 2026-04-05 08:28 by barlinike
[考研] 材料专硕322分 +11 哈哈哈吼吼吼哈 2026-04-02 11/550 2026-04-04 23:37 by 永字号
[考研] 296材料专硕求调剂 +21 202451007219 2026-04-02 22/1100 2026-04-04 21:48 by hemengdong
[考研] 277求调剂 +4 12A3 2026-04-02 5/250 2026-04-04 20:28 by 蓝云思雨
[考研] 一志愿上海大学生物学346 +3 上海大学346调剂 2026-04-03 3/150 2026-04-04 20:20 by dongzh2009
[考研] 302求调剂一志愿华中师范大学 +8 小江小江江江 2026-04-02 8/400 2026-04-04 19:50 by 蓝云思雨
[考研] 368求调剂 +5 今华习 2026-04-03 7/350 2026-04-04 18:47 by imissbao
[考研] 求调剂 +3 农业工程与信息� 2026-04-04 3/150 2026-04-04 12:19 by 舍而后得
[考研] 297求调剂 +11 ljy20040718！ 2026-04-03 13/650 2026-04-04 09:23 by 来看流星雨10
[考研] 一志愿山东大学化学与化工学院材料与化工专硕，360分求调剂 +4 不愿透露姓名的� 2026-04-02 4/200 2026-04-03 09:29 by 遗忘消失的灆
[考研] 一志愿大工学硕，求调剂 +4 yub0811 2026-04-02 4/200 2026-04-02 21:36 by 百灵童888
[考研] 一志愿北交大材料工程，总分358 +4 cs0106 2026-04-01 4/200 2026-04-02 07:42 by 尚水阁主
[考研] 285求调剂 +11 AZMK 2026-04-01 11/550 2026-04-01 22:40 by peike
[考研] 一志愿北交材料工程总分358 +5 cs0106 2026-04-01 7/350 2026-04-01 11:45 by wangjy2002
信息提示
关闭
请填处理意见
关闭