10122157项镇敏实验1棋盘覆盖

《算法设计与分析实验》

实验报告

实验指导教师 沈云付

学生姓名 项镇敏 学号 10122157 序号 1 实验时间 周三7-9

上海大学计算机工程与科学学院

2016年10月15日

实验一、棋盘覆盖问题

问题描述与实验目的：

设n=2k（k≥0）。在一个n×n个方格组成的棋盘中，恰有1个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有4k种，因而有n2种不同的棋盘，下图所示是k=2，n=4时16种棋盘中的一个。 棋盘覆盖问题要求用下图所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 易知，在任何一个n×n的棋盘中，用到的 L 型骨牌个数恰为 (n2-1)/3 。 你的任务是给定k>1，n=2k设计一个算法实现棋盘的一种覆盖。 实验分析：

使用分治策略，解决期盼覆盖问题。当k>0时，将2k×2k棋盘分割成4个2k-1×2k-1

子棋盘。特殊方格必位于4个较小子棋盘之一，其余3个子棋盘中无特殊方格。使用一个L型骨牌覆盖这3个较小棋盘的会和处，将3个无特殊方格的子棋盘转化为特殊棋盘，那么这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归的使用这种分割，直至棋盘简化为1×1棋盘。

递归方程：

设T(k)是算法ChessBoard覆盖一个2k×2k棋盘所需的时间，则从算法的分治

策略可知，T(k)满足下面的递归方程：

O(1) k=0 T(k)= 4T(k-1)+O(1) k>0 解得T(k)=O(4k)

源代码及运行结果：

//ChessBoard.cpp #include #include using namespace std;

int tile;

int Board[129][129];

void ChessBoard(int tr,int tc,int dr,int dc,int size) { if(size==1) return; int t=tile++,s=size/2; if(dr=tc+s) ChessBoard(tr,tc+s,dr,dc,s); else { Board[tr+s-1][tc+s]=t; ChessBoard(tr,tc+s,tr+s-1,tc+s,s); } if(dr>=tr+s && dc=tr+s && dc>=tc+s) ChessBoard(tr+s,tc+s,dr,dc,s); else {

Board[tr+s][tc+s]=t; ChessBoard(tr+s,tc+s,tr+s,tc+s,s); } }

int main() {

int ssize,x,y,size,k=1; while(cin>>ssize>>x>>y) {

size = pow(2,ssize); for (int i = 0; i < size; ++i) for (int j = 0; j < size; ++j) Board[i][j] = -1; tile=1; ChessBoard(0,0,x-1,y-1,size); cout<<\"Case \"<输入：3 2 6

体会：

通过这次实验的练习，加深了我对分治策略的理解。将一个大问题分解为n个规模较小的子问题，子问题相互独立且与原问题相同，通过递归方式解决问题，最终将各子问题的解合并即为原问题的解。这是一种完备的思考方式和解题方式，可以解决很多看上去繁琐却又有规律可循的问题