资源预览内容
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
亲,该文档总共5页全部预览完了,如果喜欢就下载吧!
资源描述
算法实验报告算法分析与设计实验报告实验名称: 棋盘覆盖 实验日期: 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,故此算法是一个在渐近意义下最优的算法。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号