(原創(chuàng)精品)n后問題(用拉斯維加斯算法)

1、題目：n后問題（用拉斯維加斯算法）程序清單：Randomnumber.h#include <iostream>#include "time.h"using namespace std;/隨機(jī)數(shù)類const unsigned long maxshort=65536L;const unsigned long multiplier=1194211693L;const unsigned long adder=12345L;class RandomNumberprivate:/當(dāng)前種子unsigned long randSeed;public:/構(gòu)造函數(shù)，默認(rèn)值0表示由系

2、統(tǒng)自動產(chǎn)生種子RandomNumber(unsigned long s=0);/產(chǎn)生0:n-1之間的隨機(jī)整數(shù)unsigned short Random(unsigned long n);/產(chǎn)生0,1)之間的隨機(jī)實(shí)數(shù)double fRandom(void);/產(chǎn)生種子RandomNumber:RandomNumber(unsigned long s)if(s=0) randSeed=time(0); /用系統(tǒng)時(shí)間產(chǎn)生種子else randSeed=s; /由用戶提供種子/產(chǎn)生0:n-1之間的隨機(jī)整數(shù)unsigned short RandomNumber:Random(unsigned long

3、n)randSeed=multiplier*randSeed+adder;return (unsigned short) (randSeed>>16)%n);/產(chǎn)生0,1)之間的隨機(jī)實(shí)數(shù)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); /隨機(jī)放置n個皇后拉斯維加斯算法int n, /皇后個數(shù) *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)實(shí)現(xiàn)在棋盤上隨機(jī)放置n個皇后拉斯維加斯算法RandomNumber rnd; /隨機(jī)數(shù)產(chǎn)生器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);/隨機(jī)位置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;/反復(fù)調(diào)用隨機(jī)放置n個皇后拉斯維加斯算法，直至放置成功while(X.QueensLV()cout<<"結(jié)果是："<<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