算法分析与设计实验报告七

算法分析与设计实验七2012级计算机科学与技术专业姓名牛立峰学号201215203实验题目编写拉斯维加斯整数因子分解算法和八皇后算法实验目的通过上机实验，了解并掌握概率算法思想源代码整数因子分解：//随机化算法拉斯维加斯算法因子分割问题//#include"stdafx.h"//#include"RandomNumber.h"#include<iostream>usingnamespacestd;#include"time.h"#include"math.h"//随机数类constunsignedlongmaxshort=65536L;constunsignedlongmultiplier=1194211693L;constunsignedlongadder=12345L;classRandomNumber{ private: //当前种子 unsignedlongrandSeed; public: RandomNumber(unsignedlongs=0);//构造函数，默认值0表示由系统自动产生种子 unsignedshortRandom(unsignedlongn);//产生0：n-1之间的随机整数 doublefRandom(void);//产生[0,1)之间的随机实数};RandomNumber::RandomNumber(unsignedlongs)//产生种子{ if(s==0) { randSeed=time(0);//用系统时间产生种子 } else { randSeed=s;//由用户提供种子 }}unsignedshortRandomNumber::Random(unsignedlongn)//产生0：n-1之间的随机整数{ randSeed=multiplier*randSeed+adder;//线性同余式 return(unsignedshort)((randSeed>>16)%n);}doubleRandomNumber::fRandom(void)//产生[0,1)之间的随机实数{ returnRandom(maxshort)/double(maxshort);}intSplit(intn){intm=floor(sqrt(double(n)));for(inti=2;i<=m;i++){if(n%i==0){returni;}}return1;}//求整数a和b最大公因数的欧几里得算法intgcd(inta,intb){ if(b==0) { returna; } else { returngcd(b,a%b); }}//求整数n因子分割的拉斯维加斯算法voidPollard(intn){ RandomNumberrnd; inti=1; intx=rnd.Random(n); //随机整数 inty=x; intk=2; while(true) { i++; x=(x*x-1)%n; //x[i]=(x[i-1]^2-1)modn intd=gcd(y-x,n); //求n的非平凡因子 if((d>1)&&(d<n)) { cout<<d<<endl;//因子分割问题：求n的[一]个非平凡因子的问题 return; } if(i==k) { y=x; k*=2; } }}intmain(){ intn=1024; cout<<n<<"的非平凡因子："<<endl; Pollard(n); return0;}八皇后问题：#include<stdio.h>constintnum=8;/*可以随意修改，num是多少解的就是几皇后问题*/intarr[num];intcount=0;voiddisplay()/*一个简单的数组输出函数，顺便统计解的个数*/{ for(inti=0;i<num;++i) printf("%d\t",arr[i]); printf("\n"); count++;}voidqueens(intpos=0){ /*剪枝步骤*/ /*同在斜线或者直线上*/ for(inti=0;i<pos-1;++i) { intoff=arr[i]-arr[pos-1]; if(off==0||off==pos-1-i||-off==pos-1-i) return; } /*符合条件就输出*/ if(pos==num) { display();return;} /*递归搜索解空间*/ for(intk=0;k<num;++k) { arr[pos]=k; queens(pos+1); }}voidmain(inti,intj){ queens(); printf("count:%d