在一个2^k * 2^k个方格组成的棋盘中,有一个方格与其它的不同,若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格,如何覆盖。
四各L型骨牌如下图1
图1
棋盘中的特殊方格如图2
图2
实现的基本原理是将2^k * 2^k的棋盘分成四块2^(k - 1) * 2^(k - 1)的子棋盘,特殊方格一定在其中的一个子棋盘中,如果特殊方格在某一个子棋盘中,继续递归处理这个子棋盘,直到这个子棋盘中只有一个方格为止如果特殊方格不在某一个子棋盘中,将这个子棋盘中的相应的位置设为骨牌号,将这个无特殊方格的了棋盘转换为有特殊方格的子棋盘,然后再递归处理这个子棋盘。以上原理如图3所示。
图3
将棋盘保存在一个二维数组中。骨牌号从1开始,特殊方格为0,如果是一个4 * 4的棋盘,特殊方格为(2,2),那么程序的输出为
2 2 3 3
2 1 1 3
4 1 0 5
4 4 5 5
相同数字的为同一骨牌。
=============================================================================
package 递归与分治;
public class ChessboardCoverage {
private int tile = 1; //L型骨牌的值
private int Board[][] = new int[16][16]; //表示棋盘
/*
* tr:棋盘左上角方格的行号 tc:棋盘左上角方格的列号 dr:特殊方格所在的行号 dc:特殊方格所在的列号 size:方形棋盘的边长
*/
private void coverageChessBoard(int tr, int tc, int dr, int dc, int size) {
if (size == 1)
return;
int t = tile++, s = size / 2;
// 覆盖左上角子棋盘
if (dr < tr + s && dc < tc + s)
// 特殊方格在此棋盘中
coverageChessBoard(tr, tc, dr, dc, s);
else // 此棋盘无特殊方格
{
// 用t号L型骨型牌覆盖左上角子棋盘的右下角
Board[tr + s - 1][tc + s - 1] = t;
// 覆盖左上角的其余方格
coverageChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
}
// 覆盖右上角子棋盘
if (dr < tr + s && dc >= tc + s)
coverageChessBoard(tr, tc + s, dr, dc, s);
else {
// 用t号L型骨型牌覆盖右上角子棋盘的左下角
Board[tr + s - 1][tc + s] = t;
// 覆盖右上角的其余方格
coverageChessBoard(tr, tc + s, tr + s - 1, tc + s, s);
}
// 覆盖左下角子棋盘
if (dr >= tr + s && dc < tc + s)
coverageChessBoard(tr + s, tc, dr, dc, s);
else {
// 用t号L型骨型牌覆盖左下角子棋盘的右上角
Board[tr + s][tc + s - 1] = t;
// 覆盖左下角的其余方格
coverageChessBoard(tr + s, tc, tr + s, tc + s - 1, s);
}
// 覆盖右下角子棋盘
if (dr >= tr + s && dc >= tc + s)
coverageChessBoard(tr + s, tc + s, dr, dc, s);
else {
// 用t号L型骨型牌覆盖右下角子棋盘的左上角
Board[tr + s][tc + s] = t;
// 覆盖右下角的其余方格
coverageChessBoard(tr + s, tc + s, tr + s, tc + s, s);
}
}
private void displayBoard(int size) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++)
System.out.printf("%4s", Board[i][j] + "");
System.out.println();
}
}
public static void main(String[] args) {
ChessboardCoverage chessboardCoverage = new ChessboardCoverage();
chessboardCoverage.coverageChessBoard(0, 0, 2, 2, 4);
chessboardCoverage.displayBoard(4);
}
}
分享到:
相关推荐
棋盘覆盖问题是递归的分治思想的典型应用,本文档利用c/c++ 实现棋盘覆盖问题
要求用L型骨牌无重叠覆盖满n*n的棋盘,其中棋盘上有一个特殊方格不能覆盖骨牌。用递归实现。
棋盘覆盖问题 棋盘覆盖问题_基于C++使用分治递归算法求解棋盘覆盖问题
在一个2的k次方乘以2的k次方个方格的棋盘中,恰有一个方格与其他方格不同为特殊方格,棋盘称为特殊棋盘,用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
棋盘覆盖问题递归分治
棋盘覆盖问题 使用分治递归来求解棋盘覆盖问题
在棋盘覆盖问题中,要用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。 当k>0时,将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘,特殊方格必位于4个较小子棋盘之一...
用分治法设计一个算法,使得:用若干个L型条块可以覆盖住B的除一个特殊方格外的所有方格。其中,一个L型条块可以覆盖3个方格。且任意两个L型条块不能重叠覆盖棋盘。 例如:如果n=2,则存在4个方格,其中,除一个方...
1. 编程实现整数的划分问题的递归算法 3. 编程实现特殊棋盘覆盖问题的求解
棋盘覆盖问题(c#图形界面),平时的算法实验作业,感觉写得还可以,分享给大家。
实验目的 (1)掌握分治法的设计思想; (2)学会应用分治法解决问题; 设计算法解决最大子段和或棋盘覆盖问题 实验环境 Win7 DevCPP
棋盘覆盖 3、问题分析、数学建模、算法设计 (一)不断将棋盘围绕中心划分为等分的四份,每次等分前根据特殊块的位置放置一个积木,直到棋盘的长度足够小(n=2)时,不再划分,进行填充。 (二)①若n=2,结束划分 ...
棋盘覆盖; 合并排序 循环赛日程表 递归算法:直接或者间接调用自身的算法称为递归算法。 适合递归算法的问题: 递归函数:用函数自身给出定义的函数。 递归结构:二叉树 可以转化为递归算法解决 例:递归函数—阶乘...
通过将规模为n的问题分解为k个规模较小的问题,这就是分治思想。棋盘覆盖每次将棋盘规模减小一半,直到问题得到解决。
包括win32控制台和MFC图像界面两个工程。使用分治递归策略计算棋盘覆盖问题。其中MFC程序使用了多线程的控制与同步。欢迎交流
阶乘函数,Fibonacci数列,基于递归的插入排序,时间递归方程和复杂性分析,整数划分问题,Hanoi塔问题,分治法的适用条件,二分搜索算法,大整数的乘法,Strassen矩阵乘法, 棋盘覆盖,合并排序,快速排序
U91193 棋盘覆盖 ▲ 有个重要的思想:为了达成分治的目的,要在没有真正特殊点的子棋盘内假设一个特殊点,以此出发才能继续分治 ▲ 此外,注意到在不同层函数(即不同大小的棋盘)之间,L型块编号应是递增的,但在同...