课程名称:算法设计与分析 班级:
姓名:
实验序号:一
学号:
实验日期:
指导教师:
实验成绩:
一、实验名称
分治算法实验 - 棋盘覆盖问题
二、实验目的及要求
1、熟悉递归算法编写;
2、理解分治算法的特点;
3、掌握分治算法的基本结构。
三、实验环境
Visual C++
四、实验内容
根据教材上分析的棋盘覆盖问题的求解思路,进行验证性实验;
要求完成棋盘覆盖问题的输入、分治求解、输出。有余力的同学
尝试消去递归求解。
五、算法描述及实验步骤
分治算法原理:
分治算法将大的分解成形状结构相同的子问题,并且不断递归地分解,直到
子问题规模小到可以直接求解。
棋盘覆盖问题描述:
在一个 2k x 2k 个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方
格,想要求利用四种 L 型骨牌(每个骨牌可覆盖三个方格)不相互重叠覆盖的
将除了特殊方格外的其他方格覆盖。
实验步骤:
1、定 义用 于输 入和 输出 的数 据结 构;