八皇后问题回溯,概率算法及回溯+概率可执行代码.doc

#include#include math.h#include randomnumber.husing namespace std;class Queenfriend void nQueenlv(int);friend void nQueenrc(int);friend void nQueen_lv_rc(int,int);friend int nQueen_sum(int,int);private:bool Place(int k); /测试皇后k 置于第xk列的合法性bool QueensLV(void); /随机放置n 个皇后拉斯维加斯算法void Backtrack(int);/回溯函数int n,stopVegas; /皇后个数int*x,y1000; /解向量int step;/统计步数;bool Queen:Place(int k) /Place(k)用于测试将皇后k 置于第xk列的合法性for(int j=1;jk;j+)if(abs(k-j)=abs(xj-xk)|(xj=xk)/合法性测试表达式return false;return true;bool Queen:QueensLV(void) /QueensLV(void)实现在棋盘上随机放置n 个皇后拉斯维加斯算法RandomNumber rnd; /随机数产生器int k=1; /下一个放置的皇后编号int count=1;while(k0)count=0;for(int i=1;i0) xk+=yrnd.Random(count);/随机位置step+;return (count0); /count0 表示放置成功void Queen:Backtrack(int t)if(t=n)for(int i=1;i=n&x0!=1;i+)xt=i;if(Place(t)+step;if(t=n)x0=1;/printf(%d/%d ,t,xt);Backtrack(t+1);void nQueenlv(int n) /解n 后问题的拉斯维加斯算法Queen X; /初始化X.n=n;X.step=1;X.stopVegas=n;int * p=new intn+1;for(int i=0;i=n;i+)pi=0;X.x=p;/反复调用随机放置n 个皇后拉斯维加斯算法，直至放置成功while(!X.QueensLV();cout经过X.step步得结果nendl;for(i=1;i=n;i+)for(int j=1;j=n;j+)if(j=pi)coutQ ;else cout* ;coutendl;delete p;void nQueenrc(int n)Queen Y; /初始化Y.n=n;Y.step=1;int * p=new intn+1;for(int i=0;i=n;i+)pi=0;Y.x=p;Y.Backtrack(1);for(i=1;i=n;i+)for(int j=1;j=n;j+)if(j=pi)coutQ ;else cout* ;coutendl;cout经过Y.step步出结果nendl;delete p;void nQueen_lv_rc(int n,int m)Queen Z; /初始化Z.n=n;Z.step=1;Z.stopVegas=m;int * p=new intn+1;for(int i=0;i=n;i+)pi=0;Z.x=p;while(p0!=1)while(!Z.QueensLV();Z.Backtrack(Z.stopVegas+1);for(i=1;i=n;i+)for(int j=1;j=n;j+)if(j=pi)coutQ ;else cout* ;coutendl;cout经过Z.step步得结果nendl;delete p;int nQueen_sum(int n,int m)Queen S; /初始化S.n=n;S.step=1;S.stopVegas=m;int * p=new intn+1;for(int i=0;i=n;i+)pi=0;S.x=p;while(p0!=1)while(!S.QueensLV();S.Backtrack(S.stopVegas+1);delete p;return S.step;int main()int n,min,flag;float sum65;cout输入皇后个数:n;cout回溯法的结果是：endl;nQueenrc(n);cout拉斯维加斯算法的结果是：endl;nQueenlv(n);for(int i=1;i=n-1;i+)coutk为i的拉斯维加斯+回溯算法的结果是：endl;nQueen_lv_rc(n,i);for(i=1;i=n-1;i+)sumi=0;for(int j=1;j=20;j+)sumi+=nQueen_sum(n,i);min=sum1;flag=1;coutk=i时运行20次的平均步数是sum1/20endl;for(i=2;i=n-1;i+)if(sumimin)min=sumi;flag=i;sumi=sumi/20;coutk=i时运行20次的平均步数是sumiendl;cout最优k为flagendl;return 0;Randomnumber.h#include #include time.husing namespace std;/随机数类const unsigned long maxshort=65536L;const unsigned long multiplier=1194211693L;const unsigned long adder=12345L;class RandomNumberprivate:/当前种子unsigned long randSeed;public:/构造函数，默认值0 表示由系统自动产生种子RandomNumber(unsigned long s=0);/产生0:n-1 之间的随机整数unsigned short Random(unsigned long n);/产生0,1)之间的随机实数double fRandom(void);/产生种子RandomNumber:RandomNumber(unsigned long s)if(s=0) randSeed=time(0); /用系统时间产生种子else randSeed=s; /由用户提供种子/产生0:n-1 之间的随机整数unsigned short RandomNumber:Random(unsigned long n)randSeed=multipli