目录

一，蒙特卡洛算法

1，圆周率估算

2，弗里瓦德算法(Frievald's Algorithm)

51Nod 1140 矩阵相乘结果的判断

3，数组中出现次数超过一半的数字

力扣 剑指 Offer 39. 数组中出现次数超过一半的数字

4，其他蒙特卡洛方法

二，蒙特卡洛算法的正确性

1，带校验的随机算法

2，不校验的随机算法

三，快速排序

四，数论中的随机算法

Pollard‘s rho大数分解算法

一，蒙特卡洛算法

蒙特卡洛算法是一类随机算法的总称，这些随机算法都是基于一个已知的分布规律进行计算的。

1，圆周率估算

取一个1*1的正方形，在其中随机取一个点，点在正方形内切圆中的概率就是PI/4

取的点越多，估算越精确。

2，弗里瓦德算法(Frievald's Algorithm)

弗里瓦德算法是专门用来解决下面这个问题的。

51Nod 1140 矩阵相乘结果的判断

给出三个N*N的矩阵A, B, C，问A * B是否等于C？

Input

第1行，1个数N。(0 <= N <= 500) 第2 - N + 1行：每行N个数，对应矩阵A的元素。（0 <= Mii <= 16) 第N + 2 - 2N + 1行：每行N个数，对应矩阵B的元素。（0 <= Mii <= 16) 第2N + 2 - 3N + 1行：每行N个数，对应矩阵C的元素。

Output

如果相等输出Yes，否则输出No。

讯享网

Sample Input

2 1 0 0 1 0 1 1 0 0 1 1 0

Sample Output

讯享网Yes

#include<iostream> #include<vector> #include<algorithm> using namespace std; int p = ; template<typename T> vector<vector<T>> multi(vector<vector<T>>&v1,vector<vector<T>>&v2) { vector<vector<T>>ans(v1.size(),vector<T>(v2[0].size(),0)); for(int i=0;i<v1.size();i++)for(int j=0;j<v2[0].size();j++)for(int k=0;k<v2.size();k++)ans[i][j]+=v1[i][k]*v2[k][j],ans[i][j]%=p; return ans; } #define CIN(x) while (!(cin >> x)) { \ cin.clear(); \ cin.ignore(); \ } //输入一维vector template<typename T> void fcin(vector<T>&v,int len) { v.resize(len); for(int i=0;i<v.size();i++)CIN(v[i]); } //输入二维vector template<typename T> void fcin2(vector<vector<T>>&v,int row,int col) { v.resize(row); for(int i=0;i<v.size();i++)fcin(v[i],col); } int main() { int n; cin>>n; vector<vector<long long>>A,B,C; fcin2(A,n,n); fcin2(B,n,n); fcin2(C,n,n); vector<vector<long long>>x(n); for(int i=0;i<n;i++){ x[i].resize(1); x[i][0]=rand(); } vector<vector<long long>>ans1=multi(B,x),ans2=multi(A,ans1),ans3=multi(C,x); if(VecIsSame(ans2,ans3))cout<<"Yes"; else cout<<"No"; return 0; }

看着代码很多，但是只有main函数是需要独立写的，其他都可以从我的ACM模板中找到。

3，数组中出现次数超过一半的数字

力扣OJ 剑指 Offer（31-68）_nameofcsdn的博客-CSDN 博客

力扣 剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

限制：

1 <= 数组长度 <= 50000

思路：

不校验的随机算法

一层逻辑：随机取2个数，如果不同就继续取，直到2个数相同，此时这个数大概率就是正确答案。

二层逻辑：取2个数，如果不同就继续取，直到2个数相同，此时这个数大概率就是正确答案，但是，不是随机取，而是直接取一层逻辑得到的值。

同理，我们可以不停的这样嵌套，想要几层就有几层。

代码：

讯享网class Solution { public: int err=; int get0(vector<int>& nums){ return nums[rand()%nums.size()]; } int get1(vector<int>& nums){ int a=0,b=1; while(a!=b){ a=err,b=err; while(a==err)a=get0(nums); while(b==err)b=get0(nums); } return a; } int get2(vector<int>& nums){ int a=0,b=1; while(a!=b){ a=err,b=err; while(a==err)a=get1(nums); while(b==err)b=get1(nums); } return a; } int get3(vector<int>& nums){ int a=0,b=1; while(a!=b){ a=err,b=err; while(a==err)a=get2(nums); while(b==err)b=get2(nums); } return a; } int get4(vector<int>& nums){ int a=0,b=1; while(a!=b){ a=err,b=err; while(a==err)a=get3(nums); while(b==err)b=get3(nums); } return a; } int majorityElement(vector<int>& nums) { return get4(nums); } };

然而最坏情况下算法是错的，失败用例：

[233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,233,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333,2333]

这是501个233和499个2333

改进思路：

带校验的随机算法

不需要嵌套，只要任何时候有怀疑的值，直接确定性检测即可

讯享网class Solution { public: int err=; int get0(vector<int>& nums){ return nums[rand()%nums.size()]; } int get(vector<int>& nums){ int a=0,b=1; while(a!=b){ a=err,b=err; while(a==err)a=get0(nums); while(b==err)b=get0(nums); } return a; } int majorityElement(vector<int>& nums) { while(true){ int a=get(nums),s=0; for(int i=0;i<nums.size();i++)if(nums[i]==a)s++; if(s>nums.size()/2)return a; } } };

4，其他蒙特卡洛方法

蒙特卡洛方法_nameofcsdn的博客-CSDN博客

二，蒙特卡洛算法的正确性