棋盘覆盖实验报告

实验报告

课程名称 算法分析与设计 实验项目名称 棋盘覆盖算法设计与实现 班级与班级代码 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时：