信 息 工 程 学 院
算法分析 实习报告
学院:信息工程学院 班级:软件工程083 姓名: 学号: 成绩:
一、实习题目 : 棋盘覆盖
二、实习过程 :
1、了解分治法的思想：
将一个难以解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。由分治法产生的子问题是原问题的较小模式，从而可以使用递归的方法求解，反复使用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易求出其解。
2、用分治法求解棋盘覆盖问题的思想：
当k>0时，将2k*2k 棋盘分割为4个2k-1*2k-1子棋盘如图(1)所示：
特殊方格位于4个较小子棋盘之一中，其余三个子棋盘中无特殊方格。为了将剩余三个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L 型骨牌覆盖这三个较小棋盘的回合处，如图(2)所示，这三个子棋盘被L 型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归的使用这种方格，直至棋盘简化为1*1方格。
(1) (2)
3、用分治的一般递归算法：
Divide-and-conquer(P)
{
If(|P|For(i=1;i<=k;i++)
Yi=divide-and-conquer(Pi);
Return merge(y1,…,yk);
}
4、棋盘覆盖：
如果觉得《java棋盘覆盖分治法 棋盘覆盖-分治法》对你有帮助，请点赞、收藏，并留下你的观点哦！
