安徽股票配资网站建设,wordpress文章加字段,网站建设一般分几年摊销,网站开发详细报价在一个2*x2‘个方格组成的棋盘中#xff0c;若怡有一个方格与其他方格不同#xff0c;则称该方格为特殊方格#xff0c;且称该棋盘为一特殊棋盘。显然#xff0c;特殊方格在棋盘上出现的位置有 4种情形因而对任何k0#xff0c;有4‘种特殊棋盘。图2-4 申的特殊棋益是12时 …在一个2*x2‘个方格组成的棋盘中若怡有一个方格与其他方格不同则称该方格为特殊方格且称该棋盘为一特殊棋盘。显然特殊方格在棋盘上出现的位置有 4种情形因而对任何k0有4‘种特殊棋盘。图2-4 申的特殊棋益是12时 16个特殊棋盘中的一个在棋盘複盖问题中要用图2-5 所示的 4种不同形态的工 型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格且任何 2 个 L 型骨牌不得重叠覆盖。易知在任何一个2*x2*的棋盘覆盖中用到的L 型骨牌个数恰为(45-1)/3。用分治策咯可以设计解棋盘復盖问题的一个简捷的算法。当心0时将2x2*棋盛分割为 4个25-x25!子棋盛如图 2-6a)所示。特殊方格必位于 4 个较小子棋盘之一中其余3个子棋盘中无特殊方格。为了将这 了个无特殊方格的子棋盘转化为特殊棋盘可以用一个山型骨牌覆盖这了个较小棋盘的会合处如图2-6所示这了个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格从而将原问题转化为 4个较小规模的棋盘覆盖问题。递归地使用这种分割直至棋盘简化为 1×1 棋盘。实现这种分治策略的算法 Chess Board 如下void ChessBoard (int tr, int tc, int dr, int dc, int size) {
if (size 1
return;
int ttilet,
ssize/2;
1/後盖左上角子棋盘
if (dr ‹trs de‹tcs)
ChessBoard (tr, tc, dr, dc, s);
else {
Board[trs-1][tcs-1]t;
ChessBoard(tr, tc, trs-1, tcs-1, s);
if (dr trs de › tcs)
ChessBoard(tr, tcs, dr, dc, s);
else {
Board[trs-11 tcs] t;
ChessBoard(tr, tcs, trs-1, tcs, s);
if (dr › trs dc tcs)
ChessBoard (trs, tc, dr, dc, s);
else {
Board[trs][tcs-1] t;
ChessBoard(trs, tc, trs, tcs-1, s);
if (dr › trs dc › tcs)
//L型骨牌号
//分割棋盘
//特殊方格在此栱盘中
//此栱盘中无特殊方格
//用七号山型骨牌覆盖右下角
//覆盖其余方格
//爱盖右上角子棋盘
//特殊方格在此棋盘中
//此棋盘中无特殊方格
//用七号L型骨牌覆盖左下角
//覆盖其余方格
//覆盖左下角子棋盘
//特殊方格在此棋盘中
//用七号山型骨牌覆盖右上角
//覆盖其余方格
//爱盖右下角子棋盘上述算法中用一个二维整型数组 Board 表示棋甜。BoarcroIrO1是棋盘的左上角方格。是算法中的一个全局性型交量用表示工 型骨牌的编号其初始值为 0。算法的输入珍数是切棋盘左上角方格的行号dc特殊方格所在的列号tc棋盘左上角方格的列号size: size2%棋盘规格为 2*x2%dr特殊方格所在的行号。设TK是算法 ChessBoard 覆盖一个2*x2*棋盘所需的时间则从算法的分治策略可知『满足如下递归方程(O(1)k 0T(k) {AT(k -1) O()解此递归方程可得 7045。由于覆盖一个242%棋盘所需的L 型骨牌个数为4-1/3故算法 ChessBoard 是一个在渐近意义下最优的算法。
