•
问题描述:
残缺棋盘是一个有2k×2k(k≥1)个方格的棋盘,其中恰有一个方格残缺。如图给出k=1时各种可能的残缺棋盘,其中残缺的方格用阴影表示。
• 残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。在此覆盖中要求:
1)两个三格板不能重叠
2)三格板不能覆盖残缺方格,但必须覆盖其他所有的方格。
小格子数(2k×2k -1)三格板中小格子数3。所以所需要的三格板总数为(2k×2k
-1 )/3。
•
例如,一个4*4的残缺棋盘2k*2k
以k=2时的问题为例,用二分法进行分解,得到的四个k=1的棋盘。但要注意这四个棋盘,并不都是与原问题相似且独立的子问题。
因为当如图中的残缺方格在左上部时,第1个子问题与原问题相似,而右上角、左下角和右下角三个子棋盘(也就是图中标识为2、3、4号子棋盘),并不是原问题的相似子问题,自然也就不能独立求解了。当使用一个①号三格板覆盖2、3、4号三个子棋盘的各一个方格后,我们把覆盖后的方格,也看作是残缺方格(称为“伪”残缺方格),这时的2、3、4号子问题就是独立且与原问题相似的子问题了。
•
问题分析
从以上例子还可以发现
当残缺方格在第1个子棋盘,用①号三格板覆盖其余三个子棋盘的交界方格,可以使另外三个子棋盘转化为独立子问题;
当残缺方格在第2个子棋盘时,则首先用②号三格板进行棋盘覆盖
当残缺方格在第3个子棋盘时,则首先用③号三格板进行棋盘覆盖
当残缺方格在第4个子棋盘时,则首先用④号三格板进行棋盘覆盖,这样就使另外三个子棋盘转化为独立子问题。
程序代码思路:
表示方法:每个三格板需要用同一个数字表示,不同三格板编号不同。
源码:
#include <iostream>
#include <iomanip>
using namespace std;
int board[100][100]; //存放棋盘L型的标号数组;
int tile=1; // L型骨牌号
void chessBoard(int tr, int tc, int dr, int dc, int size)
{
if (size==1)
return;
int t = tile++; // L型骨牌号
int s = size/2; // 分割棋盘
//________________________________________________ 覆盖左上角子棋盘
if (dr<tr+s&&dc<tc+s) // 特殊方格在此棋盘中
chessBoard(tr, tc, dr, dc, s);
else // 此棋盘中无特殊方格
{
board[tr+s-1][tc+s-1]=t; // 用 t 号L型骨牌覆盖右下角
chessBoard(tr,tc,tr+s-1, tc+s-1, s);// 覆盖其余方格
}
//________________________________________________ 覆盖右上角子棋盘
if (dr < tr + s && dc >= tc + s) // 特殊方格在此棋盘中
chessBoard(tr, tc+s, dr, dc, s);
else // 此棋盘中无特殊方格
{
board[tr + s - 1][tc + s] = t; //用t号L型骨牌覆盖左下角
chessBoard(tr, tc+s, tr+s-1, tc+s, s);// 覆盖其余方格
}
//_______________________________________________ 覆盖左下角子棋盘
if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中
chessBoard(tr+s, tc, dr, dc, s);
else // 此棋盘中无特殊方格
{
board[tr + s][tc + s - 1] = t; // 用 t 号L型骨牌覆盖右上角
chessBoard(tr+s, tc, tr+s, tc+s-1, s);// 覆盖其余方格
}
//__________________________________________________ 覆盖右下角子棋盘
if (dr >= tr + s && dc >= tc + s) // 特殊方格在此棋盘中
chessBoard(tr+s, tc+s, dr, dc, s);
else
{
board[tr + s][tc + s] = t; // 用 t 号L型骨牌覆盖左上角
chessBoard(tr+s, tc+s, tr+s, tc+s, s); // 覆盖其余方格
}
}
int main()
{
int size,dr,dc;
cout<<"\t\t\t棋盘覆盖问题\n";
cout<<"2^k×2^k 个方格变长size(size=2,4,8,16,32,64):";
cin>>size;
cout<<"分别输入特殊块的行下标dr,列下标dc(0-"<<(size-1)<<"):";
cin>>dr>>dc;
board[dr][dc]=0;
cout<<"棋盘覆盖图:\n";
chessBoard(0, 0, dr, dc, size);
int i,j;
for( i=0;i<size;i++)
{
for( j=0;j<size;j++)
cout<<setw(6)<<board[i][j];//setw(6)//输出量不足6个字符时在左面填充空白
cout<<endl<<endl;
}
return 0;
}
分治递归执行步骤:
1)chessBoard(0, 0, 0, 0, 4);
{ t=1; s=2;
chessBoard(0, 0, 0, 0, 2);
{ t=2; s=1;
chessBoard(0, 0, 0, 0, 1);
{ s==1
return
}
以下三步
将左上角 三格板 用t=2覆盖
}
return
以下三步 对右上递归 先 用t=1 覆盖左下
左下递归 先 用t=1 覆盖右上
右下递归 先 用t=1 覆盖左上
递归处理类似。
}
分享到:
相关推荐
用分而治之方法可以很好地解决残缺棋盘问题。
使用JAVA解决残缺棋盘覆盖问题:一个n*n的棋盘上有一个缺陷点,该点不能被覆盖,剩下的格子全部用三盒板覆盖。应用的是分治法。
残缺棋盘(defective chessboard)是一个有2k×2k 个方格的棋盘,其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘,其中残缺的方格用阴影表示。注重当k= 0时,仅存在一种可能的残缺棋盘(如图1 4 - ...
主要介绍了Java基于分治算法实现的棋盘覆盖问题,简单描述了棋盘覆盖问题,并结合具体实例形式分析了java基于分治算法实现棋盘覆盖问题的相关操作技巧,需要的朋友可以参考下
算法分析与设计 课程中分治策略的典型例子,采用MFC文档编程可视化实现算法; 能够手动进行对棋盘的颜色填充,并能显示棋盘中的填充数值。 由于这是课程作业,时间紧而赶制的,封装性可能比较差。 我用的版本是C++...
算法代码,5种算法的代码文档。还有一个算法合集之《分治算法在树的路径问题中的应用》pdf文档。
残缺棋盘覆盖仿真,功能包括 (1)自定义棋盘大小 (2)随机产生残缺块位置 (3)用4种不同颜色标识不同的三角板 (4)自动给出覆盖过程(速度可调) (5)对各种三角板进行自动计数
这个是残缺棋盘设计报告,有用的,看看吧 1问题描述与作业要求 3 1.1 问题描述 3 1.2 作业要求 4 2 算法分析与实现 4 2.1 算法分析 4 2.2算法实现的核心数据结构 5 2.3分治法的编程实现 5 3 数据结构设计 7 3.1棋盘...
利用MFC实现的残缺棋盘,点击窗口任一位置确定残缺位置。主要是分治算法。
利用分治算法求解残缺棋盘分布的c++算法
递归法求解,分治算法
利用Java编写的一款桌面应用,目的在于模拟和演示分治算法在残缺棋盘覆盖问题中的计算过程。该应用能调整棋盘大小和覆盖速度,每一类模块都有单独的颜色,4类模块的配色方案随机生成,而且还可以选择手动覆盖。
算法分析的分治法解棋盘的JAVA源代码 可以有输入的 希望可以对大家有帮助
典型算法设计技巧的介绍,主要包括贪婪算法、分治算法、动态规划、回溯算法和随机化算法等 应用 应用部分是上述数据结构和典型算法的一些应用示例,具体包括事件驱动模拟、等价类、残缺棋盘和图象压缩等问题的讨论,...
功能齐全,实现残缺棋盘分治算法的可视化。界面美观,有较强的参考价值
算法系列(一):棋盘覆盖 博客地址:http://blog.csdn.net/qq_22145801/article/