棋盘覆盖问题_8乘8棋盘覆盖怎么覆盖「建议收藏」

棋盘覆盖问题_8乘8棋盘覆盖怎么覆盖「建议收藏」算法棋盘覆盖一、什么是棋盘覆盖在一个2kⅹ2k个方格组成的棋盘中,若恰有一个方格与其他方格不同,则称该方格为特殊方格,且称该棋盘为一特殊棋盘

棋盘覆盖

一、什么是棋盘覆盖

在一个2kⅹ2k个方格组成的棋盘中,若恰有一个方格与其他方格不同,则称该方格为特殊方格,且称该棋盘为一特殊棋盘。

显然,特殊方格出现的位置有4种情况,即k>=0,有4k 种不同的特殊棋盘

棋盘覆盖:用4种不同的L型骨牌覆盖一个给定的特殊棋盘(即特殊方格的位置已经确定了)上除去特殊方格外的所有方格,且任何两个L型骨牌不得重复覆盖。

2

按照规则,我们很容易知道,在2kⅹ2k的棋盘覆盖中,用到的L型骨盘数恰为(4k-1)/3,即(所有方格个数-特殊方格个数)/3

如下图,为k=2时的一个特殊棋盘(相同颜色的三个小方格组成一个L型骨牌)和4种不同形态的L型骨牌,蓝色的为特殊方格

1

二、证明棋盘覆盖有解

数学归纳法

  • 当n=1(2ⅹ2棋盘),该问题有解

    3

  • 假设当n=k时(2kⅹ2k棋盘),该问题有解

  • 那么当n=k+1时(2k+1ⅹ2k+1棋盘),将棋盘划分为4个2kⅹ2k子棋盘,特殊方格位于4个子棋盘之一中,而其他3个子棋盘中无特殊方格。

    • 如何将这3个无特殊方格的子棋盘转化为特殊棋盘?

    • 用一个L型骨牌覆盖这3个较小棋盘的会合处,将原问题转化为4个n=k时的子问题,因为n=k时有解,所以n=k+1时也有解。

      4

三、实现棋盘覆盖的思路和方法

棋盘覆盖实现的基本方法为分治法

分治法的基本思路:将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。递归地解决这些子问题,然后将各个子问题的解合并得到原问题的解。简单地说,就是将规模为n的问题自顶向下分解,直到小问题分解到足够小,可以解决时,再自底向上合并,从而得到原来的解。

当k=0时(1ⅹ1棋盘),及特殊方格,骨牌数为0

当k >0时,将2kⅹ2k棋盘分割为4个2k-1ⅹ2k-1子棋盘了,如图

5

特殊方格位于4个较小子棋盘之一中,而其余3个子棋盘中无特殊方格。

在递归之前要将原问题转化为4个较小规模的相同子问题。(用一个L型骨牌覆盖这3个子棋盘的会合处),如图

6

从图上可以看出,这三个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格,从而将问题分解为4个较小规模的棋盘覆盖问题。

递归地使用这种分割方法,直至棋盘简化为1ⅹ1棋盘,就结束递归。

四、棋盘覆盖的具体实现代码

代码分析

—-> 对每个子棋盘按照左上,右上,右下,左下的顺时针顺序铺满棋盘。(顺序不一样,铺出来的编号也不一样)

每次都对分割后的四个小方块进行判断,判断特殊方格是否在里面。

  • 如果特殊方块在里面,这直接递归下去即可,

  • 如果不在,这根据分割的四个方块的不同位置,把右下角、左下角、左上角、右上角的方格标记为特殊方块,然后继续递归。

在递归函数里,还要有一个变量h来记录边的方格数,每次对方块进行划分时,边的方格数都会减半,这个变量是为了方便判断特殊方格的位置。

代码实现

x:棋盘左上角方格的行号

y:棋盘左上角方格的列号

a:特殊方格的行号

b:特殊方格的列号

length:2k,棋盘规模:2kⅹ2k

#include<iostream>
#include<iomanip>  
//setw(n)是c++中在输出操作中使用的字段宽度设置,n表示字段宽度。
using namespace std;

int matrix[100][100];
int num = 0;
void chessBoard(int x, int y, int a, int b, int length);

int main()
{
	int a, b, length;
	cout << "请输入棋盘的行列号";
	cin >> length;
	cout << "请输入特殊方格的行列号";
	cin >> a >> b;
	matrix[a][b] = 0;

	chessBoard(1, 1, a, b, length);

	for (int i = 1; i <= length; i++){
		for (int j = 1; j <= length; j++){
			cout << setw(4) << matrix[i][j];
		}
		cout << endl;
	}

	return 0;
}
void chessBoard(int x, int y, int a, int b, int length) {
	//如果棋盘上只有一个方格,且该方格为一特殊方格
	if (length == 1){  
		return;
	}
	int h = length / 2;   //分割棋盘
	int t = ++num;        //L型骨牌号(从1开始)
	/*左上角*/
	if (a < x + h && b < y + h){   //特殊方格在此棋盘中则划分
		chessBoard(x, y, a, b, h);   
	}else{   //否则先覆盖右下角的方格(用t号L型骨牌),再划分
		matrix[x + h - 1][y + h - 1] = t;
		chessBoard(x, y, x + h - 1, y + h- 1, h);
	}
	/*右上角*/
	if (a < x + h && b >= y + h){  //特殊方格在此棋盘中则划分
		chessBoard(x, y + h, a, b, h);
	}else{   //否则先覆盖左下角的方格(用t号L型骨牌),再划分
		matrix[x + h - 1][y + h] = t;
		chessBoard(x, y + h, x + h - 1, y + h, h);
	}
	/*右下角*/
	if (a >= x + h && b >= y + h){  //特殊方格在此棋盘中则划分
		chessBoard(x + h, y + h, a, b, h);
	}else{   //否则先覆盖左上角的方格(用t号L型骨牌),再划分
		matrix[x + h][y + h] = t;
		chessBoard(x + h, y + h, x + h, y + h, h);
	}
	/*左下角*/
	if (a >= x + h && b < y + h){  //特殊方格在此棋盘中则划分
		chessBoard(x + h, y, a, b, h);
	}else{   //否则先覆盖右上角的方格(用t号L型骨牌),再划分
		matrix[x + h][y + h - 1] = t;
		chessBoard(x + h, y, x + h, y + h - 1, h);
	}
}

运行结果如下图

7

参考链接:https://www.cnblogs.com/crx234/p/5988055.html

五、算法分析

设T(k)是如上算法覆盖一个2kⅹ2k期盼所用的时间

8

由于覆盖一个2kⅹ2k期盼所需的L型骨牌个数为(4k-1)/3

9

故该算法为渐近意义下的最优算法。

今天的文章棋盘覆盖问题_8乘8棋盘覆盖怎么覆盖「建议收藏」分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/72483.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注