随机化算法(2)拉斯维加斯算法和蒙特卡罗算法
2022/2/11 22:13:27
本文主要是介绍随机化算法(2)拉斯维加斯算法和蒙特卡罗算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
实验要求
1、根据实验内容构思设计算法;
2、对所设计的算法采用大O符号进行时间复杂性分析;
3、上机实现算法;
4、实验报告内容应包括问题描述、问题分析、算法设计、算法实现、运行结果及算法复杂度分析等内容。
实验内容
1、使用拉斯维加斯( Las Vegas )算法求解1000-9999之间的任意随机整数n的因子划分问题,对于不同的测试用例给出具体的执行时间。
#include <cstdio> #include <cstdlib> #include <ctime> #include <cstring> #include <iostream> #include<algorithm> const int S=20; using namespace std; typedef long long LL; #define maxn 10000 LL factor[maxn]; int tot; LL muti_mod(LL a,LL b,LL c){ //返回(a*b) mod c,a,b,c<2^63 a%=c; b%=c; LL ret=0; while (b){ if (b&1){ ret+=a; if (ret>=c) ret-=c; } a<<=1; if (a>=c) a-=c; b>>=1; }return ret; } LL pow_mod(LL x,LL n,LL mod){ //返回x^n mod c LL ret=1; while(n) { if(n&1) ret=muti_mod(ret,x,mod); x=muti_mod(x,x,mod); n=n>>1; }return ret; } bool check(LL a,LL n,LL x,LL t){ //以a为基,n-1=x*2^t,检验n是不是合数 LL ret=pow_mod(a,x,n),last=ret; for (int i=1;i<=t;i++){ ret=muti_mod(ret,ret,n); if (ret==1 && last!=1 && last!=n-1) return 1;//n是合数 last=ret; } if (ret!=1) return 1; return 0; } bool Miller_Rabin(LL n){ LL x=n-1,t=0; while ((x&1)==0) x>>=1,t++; bool flag=0;//flag是0表示合数,1表示素数 if (t>=1 && (x&1)==1){//当n为偶数时,它一定不是素数(2除外) for (int k=0;k<S;k++){ LL a=rand()%(n-2)+1; if (check(a,n,x,t)) {flag=0;break;} flag=1; } } if (flag || n==2) return 1; return 0; } LL gcd(LL a,LL b){ if (a==0) return 1; if (a<0) return gcd(-a,b); while (b){ LL t=a%b; a=b; b=t; } return a; } LL Pollard_rho(LL x,LL c){ LL i=1,x0=rand()%x,y=x0,k=2; while (1){ i++; x0=(muti_mod(x0,x0,x)+c)%x; LL d=gcd(y-x0,x); if (d!=1 && d!=x){ return d; } if (y==x0) return x; if (i==k){ y=x0; k+=k; } } } void findfac(LL n){ //递归进行质因数分解N if (Miller_Rabin(n)){ factor[tot++] = n; return; } LL p=n; while (p>=n) p=Pollard_rho(p,rand() % (n-1) +1); findfac(p); findfac(n/p); } int main(){ srand(time(NULL)); int t; scanf("%d",&t); while (t--){ LL n; scanf("%lld",&n); if (Miller_Rabin(n)) { //printf("Prime\n"); cout<<n<<endl; } else{ tot = 0; findfac(n); sort(factor,factor+tot); for (int i = 0; i < tot; i++) printf("%lld ",factor[i]); printf("\n"); } }return 0; }
2、分别从键盘输入20个、30个整数,使用蒙特卡罗算法求解主元素,对于不同的测试用例给出算法的执行时间。
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <time.h> #include <math.h> using namespace std; #define N 30 bool Majority(int *T, int len, int &num) { int n = rand()%10; num = T[n]; int cnt = 0; for(int i=0; i<len; i++) { if(T[i] == num) cnt++; } return (cnt>len/2); } bool MajorityMC(int *T, int len, double e, int &num) { int k = ceil(log(1/e)/log((float)2)); for(int i=0; i<k; i++) { if(Majority(T, len, num)) return true; } return false; } int main() { int num=INT_MAX; float e = 0.001; int T[N]={3,3,1,3,4,2,3,5,3,5,3,3,3,3,3,2,3,3,4,2,2,3,2,3,3,1,3,2,0,2}; cout<<"元素如下:"<<endl; for(int i=0; i<N; i++) { cout<<T[i]<<" "; } cout<<endl; if(MajorityMC(T,N,e,num)) cout << "该数组的主元素为:" << num << endl; else cout << "该数组没有主元素" << endl; return 0; }
这篇关于随机化算法(2)拉斯维加斯算法和蒙特卡罗算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南