算法实验报告算法分析与设计实验报告实验名称： 棋盘覆盖 实验日期： 2011/03/06 学生姓名： 学生学号： 算法实验报告一、实验目的在一个 2k*2k 的方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一个特殊方格。用分治法将整个棋盘除特殊方格以外的方格覆盖。二、实验环境Windows7 + Visual Studio 2010三、实验内容1. 设计思路当 k0 时，将 2k * 2k 的棋盘分割为 4 个 2（k-1 ） *2（k-1） 子棋盘。特殊方格必位于 4 个较小棋盘之一中，其余 3 个子棋盘中无特殊方格。为了将这 3 个无特殊方格的子棋盘化为特殊棋盘，我们用一个 L 型骨牌覆盖这 3 个较小的棋盘的回合处，这 3 个子棋盘被 L 型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题化为 4 个小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘化简为 1*1棋盘。2. 相关模块#include #include using namespace std;void ChessBoard(int,int,int,int,int);int *board;/棋盘int tile = 1;/L型骨牌编号void main()int size = 0;int row, column;cout size;cout row column;算法实验报告board = new int*size;for(int i=0; i=tc+s)ChessBoard(tr,tc+s,dr,dc,s);elseboardtr+s-1tc+s=t;ChessBoard(tr,tc+s,tr+s-1,tc+s-1,s);/左下角if(dr=tr+s & dc=tr+s & dc=tc+s)ChessBoard(tr+s,tc+s,dr,dc,s);elseboardtr+stc+s=t;ChessBoard(tr+s,tc+s,tr+s,tc+s,s);四、实验结果分析及结论算法实验报告由于覆盖一个 2k * 2k 棋盘所需的 L 型骨牌个数为（4 k-1）/3，故此算法是一个在渐近意义下最优的算法。