(原创精品)n后问题(用拉斯维加斯算法)

1、题目：n后问题（用拉斯维加斯算法）程序清单：Randomnumber.h#include <iostream>#include "time.h"using namespace std;/随机数类const unsigned long maxshort=65536L;const unsigned long multiplier=1194211693L;const unsigned long adder=12345L;class RandomNumberprivate:/当前种子unsigned long randSeed;public:/构造函数，默认值0表示由系

2、统自动产生种子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

3、n)randSeed=multiplier*randSeed+adder;return (unsigned short) (randSeed>>16)%n);/产生0,1)之间的随机实数double RandomNumber:fRandom(void)return Random(maxshort)/double(maxshort);Nqueen LasVegas.cpp#include<iostream>#include "math.h"#include "randomnumber.h"using namespace std;cl

4、ass Queenfriend void nQueen(int); private:bool Place(int k); /测试皇后k置于第xk列的合法性bool QueensLV(void); /随机放置n个皇后拉斯维加斯算法int n, /皇后个数 *x,y1000; /解向量;bool Queen:Place(int k) /Place(k)用于测试将皇后k置于第xk列的合法性for(int j=1;j<k;j+)if(abs(k-j)=abs(xj-xk)|(xj=xk)return false;return true;bool Queen:QueensLV(void) /Que

5、ensLV(void)实现在棋盘上随机放置n个皇后拉斯维加斯算法RandomNumber rnd; /随机数产生器int k=1; /下一个放置的皇后编号int count=1;while(k<=n)&&(count>0)count=0;for(int i=1;i<=n;i+)xk=i;if(Place(k)ycount+=i;if(count>0) xk+=yrnd.Random(count);/随机位置return (count>0); /count>0表示放置成功void nQueen(int n) /解n后问题的拉斯维加斯算法Quee

6、n X; /初始化X.n=n;int * p=new intn+1;for(int i=0;i<=n;i+)pi=0;X.x=p;/反复调用随机放置n个皇后拉斯维加斯算法，直至放置成功while(X.QueensLV()cout<<"结果是："<<endl;for(int i=1;i<=n;i+)for(int j=1;j<=n;j+)if(j=pi)cout<<"Q"<<" "if(j!=pi)cout<<"*"<<" "cout<<endl;break;delete p;void main()int n;c