10122157项镇敏实验1棋盘覆盖

《10122157项镇敏实验1棋盘覆盖》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法设计与分析实验》实验报告实验指导教师学生姓名项镇敏学号10122157序号1实验时间上海大学计算机工程与科学学院2016年10月15B实验一、棋盘覆盖问题问题描述与实验目的:设n二，(k^O)o在一个nXn个方格组成的棋盘中，恰有1个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有坐种，因而有r?种不同的棋盘，下图所示是k=2,n=4时16种棋盘中的一个。棋盘覆盖问题要求用下图所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠

2、覆盖。易知，在任何一个nXn的棋盘中，用到的L型骨牌个数恰为(『-1)/3。你的任务是给定k>l,n=2k设计一个算法实现棋盘的一•种覆盖。实验分析：使用分治策略，解决期盼覆盖问题。当k>OU寸,将以労棋盘分割成4个2k-,x2k-1子棋盘。特殊方格必位于4个较小子棋盘Z-,其余3个子棋盘中无特殊方格。使用一个L型骨牌覆盖这3个较小棋盘的会和处，将3个无特殊方格的子棋盘转化为特殊棋盘，那么这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归的使用这

3、种分割，直至棋盘简化为1x1棋盘。递归方程：设T(k)是算法ChessBoard覆盖一个才Q棋盘所需的时间，则从算法的分治策略可知，T(k)满足下面的递归方程：「0(1)k=0T(k)=<-4T(k・l)+0(1)k>0解得T(k)=O(4k)源代码及运行结果：//ChessBoard.cpp#includeviostream>#includeusingnamespacestd;inttile;intBoard[129][129];voidChessBoard(inttr’inttc,in

4、tdr’intdc,intsize){if(size==l)return;intt=tile++,s=size/2;if(dr=tc+s)ChessBoard(tr,tc+s,dr,dc,s);else{Board[tr+s-l][tc+s]=t;ChessBoard(

5、tr,tc+s,tr+s-l,tc+s,s);}if(dr>=tr+s&&dc=tr+s&&dc>=tc+s)ChessBoard(tr+s/tc+s,dr,dc,s);elseBoard[tr+s][tc+s]=t;ChessBoard(tr+s,tc+s,tr+s,tc+s,s);}}intmain()

6、{intssize,x,y,size,k二1;while(cin»ssize»x»y){size=pow(2,ssize);for(inti=0;i

7、]«,,t";cout«endl;}}return0;}输入：326匕26ICase1：n»3B3448899B2248-179E266107711656110101111131411181919tt312141418181719Ll512121620171721Ll515161620202121体会:通过这次实验的练习，加深了我对分治策略的理解。将一个大问题分解为n个规模较小的子问题，子问题相互独立且与原问题相同，通过递归方式解决问题，最终将各了问题的解合并即为原问题的解。这是一种完备的思考方式和解题

8、方式,可以解决很多看上去繁琐却又有规律可循的问题