问题描述
给定2个集合 S 和 T ，试设计一个判定 S 和 T 是否相等的蒙特卡罗算法。
题目分析
要求用蒙特卡罗算法进行求解，那么思路就是：随机选择集合 S 中的元素与集合 T 中的元素进行比较，若随机选择很多次都能从集合T中找到与之对应的相等，则集合 S 和 T 相等。
蒙特卡罗知识可以参考这个博主的博文，链接：/Blackoutdragon/article/details/117511804
算法设计:
f1()：从集合 S 中随机选择的数组元素 x ,测试集合 T 中是否有与之相等的元素，若有，则算法返回true，否则返回 false,表明集合 S 和 T 不相等。f2()：重复调用函数f1()，调用过程中若f1()返回 true 则继续调用，否则可以判定集合 S 和 T 不相等，直接退出测试。补充：srand和time的用法
srand函数:
传入一个unsigned的参数，表示初始化随机种子，如果随机种子一样，那么输出的随机数（rand()的返回值）也一样。
time函数：
time函数是获得系统时间的。
如果想要随机数每次不重复，可以使用系统时间来初始化，即调用函数time,然后将其返回值time_t型数据转化为unsigned，再作为随机种子传给 srand 函数，即:srand((unsigned) time(&t));
还有一个用法，不需要定义time_t型 t 变量，直接传入一个空指针即可，srand((unsigned) time(NULL));，因为程序中往往并不需要经过参数获得的数据。
AC代码
#include<iostream>#include<algorithm>#include<time.h>#include<math.h>#define N 100000using namespace std;int S[N],T[N];int n;double e=0.00001;bool f1() {//单独一次 srand((unsigned)time(NULL));//用随机函数rand求0~n-1的随机数index int index=rand()%n-1;//数组索引 for(int j=0; j<n; j++) {//找寻数组 T 中是否含有S[index] if(T[j]==S[index])return true;}return false;}bool f2() {int x=(int)ceil(log(1/e));for(int i=1; i<=x; i++) {//找很多次if(!f1())//只要找到一个不相符的结果，说明Ｓ和T就是不想等的return false;}return true;}int main() {cin>>n;//集合长度 for(int i=0; i<n; i++)cin>>S[i];for(int i=0; i<n; i++)cin>>T[i];if(f2())cout<<"Yes"<<"\n";elsecout<<"No"<<endl;}
如果觉得《集合相等问题-蒙特卡罗算法》对你有帮助，请点赞、收藏，并留下你的观点哦！
