实验报告
课程名称 算法分析与设计 实验项目名称 棋盘覆盖算法设计与实现 班级与班级代码 14251102202 实验室名称（或课室） 实验楼802 专 业 计算机科学与技术 任课教师 李绍华 学 号： 14251102202 姓 名： 陈晓俊 实验日期： 2016年10月27日
广东商学院教务处 制
姓名 实验报告成绩
评语：
等级 优 项目 算法描述的正确性 算法时间分析正确性 实验结果的正确性 附程序代码正确性 报告格式的正确性
良 中 差
指导教师（签名） 年 月 日
说明：指导教师评分后，实验报告交院（系）办公室保存。
一、实验目的
1、理解算法的概念 2、实现棋盘化以及棋盘覆盖 3、理解递归与分治策略算法 4、能够用Java语言实现该算法
二、实验设备
硬件：计算机一台
软件：Windows 7操作系统、eclipse Java编程软件
三、问题与算法描述
1、问题描述
在一个2^k×2^k （k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格，且称该棋盘为一个特殊棋盘。在棋盘覆盖问题中，要用4种不同形态的L型骨牌覆盖给定的特异盘上除特殊方格以外所有方格，且任何2个L型骨牌不得重叠覆盖。 2、算法描述
当k>0时将2^k×2^k 棋盘分割为4个2k-1×2k-1 子棋盘。 特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘可以用一个L型骨牌覆盖，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割直至棋盘简化为棋盘1×1。
3、算法时间复杂性分析
从算法的分割策略可知，此算法的时间复杂度如下递归方程所示：
o(1)k?0 T(k)?{
4T(k?1)?o(1)k?0解此递归方程可得：T(k)?o(4k)。由于覆盖2^k×2^k 棋盘所需的L型
（4k?1）/3，所以这个算法是一个渐进意义的最优算法。 骨牌个数为
四、实验结果 1、当k=0时：
2、当k>0时: 例如k=3时：
例如k=5时：
相关推荐：
loading