课程设计:马的极小覆盖

//题目21：在8*8的国际象棋上，如果在放置若干马后，使得整个棋盘的任意空位置上所放置的棋子均能被这些马吃掉， //则称这组放置为棋盘的一个满覆盖。若去掉满覆盖中的任意一个棋子都会使这组放置不再是满覆盖，则称这 //一满覆盖为极小满覆盖。设计程序完成如下要求： // (1)求解一个极小满覆盖。 // (2)最好能画出棋盘的图形形式，并在其上动态的演示试探过程。 // (3)程序能方便的移植到其它规格的棋盘上。

////////////////////////////////---------课程设计
//题目21：在8*8的国际象棋上，如果在放置若干马后，使得整个棋盘的任意空位置上所放置的棋子均能被这些马吃掉，
//则称这组放置为棋盘的一个满覆盖。若去掉满覆盖中的任意一个棋子都会使这组放置不再是满覆盖，则称这
//一满覆盖为极小满覆盖。设计程序完成如下要求：
//            （1）求解一个极小满覆盖。
//            （2）最好能画出棋盘的图形形式，并在其上动态的演示试探过程。
//            （3）程序能方便的移植到其它规格的棋盘上。


#include
#include
using namespace std;

const int ChessBoardScale = 3 ;                            //棋盘规模；
int Record[ChessBoardScale][ChessBoardScale];              //记录被吃几率；
char Cover[ChessBoardScale][ChessBoardScale];              //记录可以放马的位置；

class ChessBoard{
public:
	void GetChance（ ）;                    //计算每一个位置被其它位置的马吃掉的几率；
	void ReCaculateChance（/**/ChessBoard Cb）;            //主题算法：计算极小覆盖；
	void GetMinCover（ChessBoard Cb）;                    //输出最终结果；
	void Condition（int aint b ）;               //被吃几率的再次计算；
};

void ChessBoard::GetChance（）{
	for（int i = 0; i < ChessBoardScale;i++）{
		for（int j = 0; j < ChessBoardScale; j++）{
			int k=0;
			if（j-2 >= 0  &&  i-1 >= 0）{ Record[i-1][j-2]++; }
			if（j-1 >= 0  &&  i-2 >= 0）{ Record[i-2][j-1]++; }
			if（j-2 >= 0  &&  i+1 < ChessBoardScale）{ Record[i+1][j-2]++; }
			if（j-1 >= 0  &&  i+2 < ChessBoardScale）{ Record[i+2][j-1]++; }
			if（j+2 < ChessBoardScale  &&  i-1 >= 0）{ Record[i-1][j+2]++; }                  
			if（j+1 < ChessBoardScale  &&  i-2 >= 0）{ Record[i-2][j+1]++; }
			if（j+2 < ChessBoardScale  &&  i+1 < ChessBoardScale）{ Record[i+1][j+2]++; }
			if（j+1 < ChessBoardScale  &&  i+2 < ChessBoardScale）{ Record[i+2][j+1]++; }
		}
	}
}

//主体算法------------------------------------
void ChessBoard::ReCaculateChance（ChessBoard Cb）{
	int Max = Record[0][0];
	int Max_i = 0Max_j = 0;
	for（int i = 0; i < ChessBoardScale; i++）{
		for（int j = 0; j < ChessBoardScale; j++）{//////计算棋盘中被吃几率最大的位置；
			if（Record[i][j] > Max）{
				Max = Record[i][j];
				Max_i = i;
				Max_j = j;
			}
		}
	}

	if（Record[Max_i][Max_j] >= 0 ）{  ///////在棋盘中被吃几率最大的位置放马；
		Cover[Max_i][Max_j] = ‘@‘;
		Record[Max_i][Max_j] = -1;
		cout<		cout<<“此步计算马应该在的位置：“<<（ChessBoardScale*Max_i+Max_j）<		cout<	}                                    ////////////棋盘的输出；////////////******************

//------------------------------------------------------------------------------------极小覆盖的算法；

	if（Max_j-2 >= 0  &&  Max_i-1 >= 0）{
		Record[Max_i-1][Max_j-2] = -1;
		int i = Max_i-1;
		int j = Max_j-2;
		Cb.Condition（ij）;
	}

	if（Max_j-1 >= 0 && Max_i-2 >= 0）{
		Record[Max_i-2][Max_j-1] = -1;
		int i=Max_i-2;
		int j=Max_j-1;
		Cb.Condition（ij）;
	}

	if（Max_j-2 >= 0 && Max_i+1		Record[Max_i+1][Max_j-2] = -1;
		int i=Max_i+1;
		int j=Max_j-2;
		Cb.Condition（ij）;
	}

	if（Max_j-1 >= 0 && Max_i+2		Record[Max_i+2][Max_j-1] = -1;
		int i = Max_i+2;
		int j = Max_j-1;
		Cb.Condition（ij）;
	}

	if（Max_j+2= 0）{
		Record[Max_i-1][Max_j+2] = -1;
		i

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

     文件      59392  2009-06-29 20:39  马的极小覆盖.doc

     文件       7326  2009-06-29 19:07  Lcover.cpp

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

                66718                    2