基于蒙特卡洛算法的皇后控制问题

算法分析的课后题，很实用。基于蒙特卡洛的算法的皇后控制问题

#include 
#include 
#include 
#include 
#include 


ifstream infile（“input.txt“）;
ofstream outfile（“output.txt“）;


const unsigned long maxshort=65536L;
const unsigned long multiplier=1194211693L;
const unsigned long adder=12345L;

//随机数类
class RandomNumber
{
public:
	//构造函数，缺省值0表示由系统自动产生种子
	RandomNumber（unsigned long s=0）;
	//产生0:n-1之间的随机整数
	unsigned short Random（unsigned long n）;
	//产生[01）之间的随机实数
	double fRandom（void）;
private:
	//当前种子
	unsigned long randSeed;
};

//产生种子
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=multiplier*randSeed+adder;
	return （unsigned short）（（randSeed>>16）%n）;
}

//产生[01）之间的随机实数
double RandomNumber::fRandom（void）
{
	return Random（maxshort）/double（maxshort）;
}

//2维数组类
template 
void Make2DArray（T** &x int rows int cols）
{
        //创建行指针
        x = new T* [rows];
        //为每行分配空间
        for（int j = 0; j < rows; j++）
        {
                x[j] = new T[cols];
        }
}


template 
void Delete2DArray（T** &x int rows）
{
        //释放为每行所分配的空间
        for（int j = 0; j < rows; j++）
        {
                delete[] x[j];
        }
        //删除行指针
        delete[] x;
        x = NULL;
}

class Queen
{
	friend bool nQueen（int）;
	private:
		bool Place（int k）;//测试皇后k置于第x[k]列的合法性
		bool Backtrack（int t）;//解n后问题的回溯法
		bool ddBacktrack（int t）;//迭代法
		int Placenum（int k）;//暂时不用计算已放置皇后个数
		int QueensLV（int stopVegas）;//随机放置n个皇后的拉斯维加斯算法
		bool ctrl（int m）;//测试皇后是否已控制棋盘
		int n//皇后个数
			*x*y*a**z;//x[k]表示：第k行皇后置于第x[k]列
                         //y是用来记录每行皇后可行位置
                         //a是用来记录最优解皇后位置
                         //z是用来记录皇后控制的方格
		int cminc;//cmin记录最优皇后个数，c为当前个数
		RandomNumber rnd;//随机数产生器定义在类里随机效果更好
};

bool Queen::Place（int k）
{//测试皇后k置于第x[k]列的合法性x[k]和x[j]都大于0时候比较
	if（x[k]>0）
		for（int j=1;j			if（（x[j]>0）&&（（abs（k-j）==abs（x[j]-x[k]））||x[j]==x[k]））
				return false;
	return true;
}

bool Queen::ctrl（int m）
{//测试皇后是否已控制棋盘m*m
	int ijuvcount=0;
	for（i=1;i<=m;i++）
		for（j=1;j<=m;j++） z[i][j]=0;//初始置0
	for（i=1;i<=m;i++）
	{
		if（x[i]>0） //i行有皇后时
		{
			for（j=1;j<=m;j++） {z[i][j]=1;z[j][x[i]]=1;}//i行x[i]列所有元素都控制
			for（u=iv=x[i];u>=1&&v>=1;u--v--） z[u][v]=1;//（ix[i]）左上对角线所有元素都控制
			for（u=iv=x[i];u<=m&&v>=1;u++v--） z[u][v]=1;//（ix[i]）左下对角线所有元素都控制
			for（u=iv=x[i];u>=1&&v<=m;u--v++） z[u][v]=1;//（ix[i]）右上对角线所有元素都控制
			for（u=iv=x[i];u<=m&&v<=m;u++v++） z[u][v]=1;//（ix[i]）右下对角线所有元素都控制
		}
	}
	for（i=1;i<=m;i++）
		for（j=1;j<=m;j++） count+=z[i][j];
	return（count==m*m）;
}

bool Queen::Backtrack（int t）
{//解n后问题的回溯法有解输出true
	if（t>n）
		{//输出一个解
//		for（int i=1;i<=n;i++）
//			a[i]=x[i];
//		return true;
		if（ctrl（n）&&（c<=cmin））
		{
			a

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      68414  2007-08-11 11:12  皇后控制问题\queen.pdf

     文件       6028  2007-08-11 11:11  皇后控制问题\queen1.cpp

     文件     140288  2007-08-11 11:11  皇后控制问题\queen1.ppt

     文件       4617  2010-12-21 14:20  皇后控制问题\queen2.cpp

     文件     224768  2007-08-11 11:11  皇后控制问题\queen2.ppt

     文件       3176  2010-12-21 14:25  皇后控制问题\queen3.cpp

     文件     185344  2007-08-11 11:12  皇后控制问题\queen3.ppt

     文件          3  2010-12-21 14:15  皇后控制问题\input.txt

     文件         19  2010-12-21 14:28  皇后控制问题\output.txt

     文件     597976  2010-12-21 14:20  皇后控制问题\queen2.exe

     文件     594415  2010-12-21 14:25  皇后控制问题\queen3.exe

     目录          0  2007-08-11 11:12  皇后控制问题

----------- ---------  ---------- -----  ----

              1825048                    12