俞鑫 棋盘中的棋盘——浅谈棋盘的分割思想.pptVIP

有了模块1和模块2这两样工具，对m×n真棋盘的分割就得心应手了。对任意的m×n的真棋盘，当n≥5时，对于棋盘中最左边的3列棋子形成的m×3的棋盘，我们通过下面的操作将其去除。 1、当m是3的倍数时 首先将左边3列分成m/3个3×3的子棋盘。 算法分析 再将每个3×3的子棋盘分成3个3×1的子棋盘。 每次对最上方最左边的3×1子棋盘进行操作，由于其左方无棋子，可以保证它是模块1，将其去除。 2、当m模3余1时 由于m≥2，故m至少是4，m×3棋盘最上方的2×3子棋盘是一个模块2，将其去除。 算法分析 (m-2)×3棋盘最上方的2×3子棋盘也是一个模块2，将其去除。 对于剩下的(m-4)×3棋盘，由于m-4是3的倍数，同1进行操作，将其去除。 3、当m模3余2时 m×3棋盘最上方的2×3子棋盘是一个模块2，将其去除。 算法分析 对于剩下的(m-2)×3棋盘，由于m-2是3的倍数，同1进行操作，将其去除。 设m与p关于3同余，n与q关于3同余(2≤p,q≤4) ，对于任意的m×n的真棋盘，当n ≥5时，不断通过上述操作除去最左边3行，真棋盘规模将发生如下变化： 再将棋盘顺时针旋转90度，真棋盘规模变为q×m，继续进行上述操作： 现在，我们只要对p×q的真棋盘进行操作，便可得到m×n的真棋盘经过操作最少能得到的棋子数的上界。 算法分析 m×n?m×(n-3)?m×(n-6)?…?m×q 再将棋盘顺时针旋转90度，真棋盘规模变为p×q。 q×m?q×(m-3)?q×(m-6)?…?q×p * * ——浅谈棋盘的分割思想 上海市复旦附中 俞鑫 信息学是一门综合性的学科，也是一门充满乐趣的学科。 棋盘，作为一个重要的数学模型，以其趣味性和复杂的数学特性经常受到出题者的青睐。 因此，深入研究棋盘中蕴含的算法思想对于一名信息学爱好者而言是十分必要的。在此，我将着重说明棋盘中的一种重要思想——棋盘的分割思想。 引言 子棋盘3 子棋盘2 子棋盘1 对于一个m×n的棋盘，它所含的子棋盘共有Cm×Cn个，而其分割方法更是不计其数。巧妙地对棋盘进行分割，可以解决许多种类的棋盘问题。 2 2 引言 例一：棋盘覆盖（经典问题) 题目描述： 在一个2k×2k方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一特殊方格，且称该棋盘为一特殊棋盘。显然特殊方格在棋盘上出现的位置有4k种情形。因而对任何k≥0，有4k种不同的特殊棋盘。图中的特殊棋盘是当k=2时16个特殊棋盘中的一个。 在棋盘覆盖问题中，我们要用以下4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 现求一种覆盖方法。 4种不同形态的L型骨牌 输入：第一行为k（棋盘的尺寸），第二行为x,y (1 ≤ x,y ≤ 2k ) ，分别表示特殊方格所在行与列。 输出：共2k行，每行2k个数，分别表示覆盖该格的L型的编号（特殊格用0表示）。 输入： 2 1 2 输出： 1 0 2 2 1 1 3 2 4 3 3 5 4 4 5 5 样例： 算法分析 由棋盘尺寸为2k×2k ，我们可以想到将其分割成四个尺寸为2k-1×2k-1的子棋盘 可是，由于含特殊方格的子棋盘与其它子棋盘不同，问题还是没有解决。 算法分析 只要稍作思考，我们就可以发现，只要将L型如图放置在棋盘的中央，就可以使四个子棋盘都变成特殊棋盘。此时问题也变成了四个相同的子问题，只需运用简单的递归就可以解决这道问题了。 程序实现 二位数组num: 覆盖该格的L型的编号，下文所说的 对方格赋值即对其对应的num赋值。 x1,y1: 当前棋盘左上角方格的行号与列号 x2,y2: 当前棋盘右下角方格的行号与列号 x3,y3: 当前棋盘中特殊格的行号与列号 ck: 当前棋盘的尺寸（ 2ck×2ck ） cnum: 当前L型骨牌的编号 初始值： k ck 1 y x 2k 2k 1 1 cnum y3 x3 y2 x2 y1 x1 开始时，将num[x,y]设为0 当ck=0时：棋盘尺寸为1×1，该格为已赋值的特殊格，不进行任何操作。 当ck0时：设xm为(x1+x2+1)/2，ym为(y1+y2+1)/2， xm ym x1 x2 y1 y2 比较x3与xm，y3与ym的大小就能知道特殊格所在子棋盘的位置，将另外三个子棋盘中靠近棋盘中央的三个方格赋值为cnum，并分别作为这三个子棋盘的特殊格。随后cnum增加1。再对这四个棋盘分别进行处理。 程序实现 时间复杂度：O(4