////////////////////////////////---------課程設計
//題目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?		for（int?j?=?0;?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?			if（j-1?>=?0??&&??i+2?			if（j+2?=?0）{?Record[i-1][j+2]++;?}??????????????????
			if（j+1?=?0）{?Record[i-2][j+1]++;?}
			if（j+2?			if（j+1?		}
	}
}

//主體算法------------------------------------
void?ChessBoard::ReCaculateChance（ChessBoard?Cb）{
	int?Max?=?Record[0][0];
	int?Max_i?=?0Max_j?=?0;
	for（int?i?=?0;?i?		for（int?j?=?0;?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