论文—浅谈棋盘的分割思想》.doc

棋盘中的棋盘——浅谈棋盘的分割思想【摘要】现在的信息学竞赛题目,经常以某种数学模型作为出题媒介,使题目充满乐趣性和深厚的数学底蕴,而棋盘就是其中一种重要的数学模型。本文着重对棋盘的一种重要思想——棋盘的分割思想进行分析,并引入两道典型例题,说明棋盘分割应遵循的规律,使读者能对纷繁复杂的棋盘分割有一定的了解。【关键词】数学模型棋盘算法思想【正文】引言信息学是一门综合性的学科,也是一门充满乐趣的学科。棋盘,作为一个重要的数学模型,以其趣味性和复杂的数学特性经常受到出题者的青睐。因此,深入研究棋盘中蕴含的算法思想对于一名信息学爱好者而言是十分必要的。在此,我将着重说明棋盘中的一种重要思想——棋盘的分割思想。子棋盘3子棋盘2子棋盘1对于一个m×n的棋盘,个,而其分割方法更是不计其数。巧妙地对棋盘进行分割,可以解决许多种类的棋盘问题。例一:棋盘覆盖(经典问题)题目描述:在一个2k×2k方格组成的棋盘中,若恰有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一特殊棋盘。显然特殊方格在棋盘上出现的位置有4k种情形。因而对任何k≥0,有4k种不同的特殊棋盘。图中的特殊棋盘是当k=2时16个特殊棋盘中的一个。4种不同形态的L型骨牌在棋盘覆盖问题中,我们要用以下4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。易知,在任何一个2k×2k的棋盘覆盖中,用道的L型骨牌个数恰为(4k-1)/3。现求一种覆盖方法。输入:第一行为k(棋盘的尺寸),第二行为x,y(1≤x,y≤2k),分别表示特殊方格所在行与列。输出:共2k行,每行2k个数,分别表示覆盖该格的L型的编号(特殊格用0表示)。样例:输入:212输出:10221**********算法分析由棋盘尺寸为2k×2k,我们可以想到将其分割成四个尺寸为2k-1×2k-1的子棋盘可是,由于含特殊方格的子棋盘与其它子棋盘不同,问题还是没有解决。只要稍作思考,我们就可以发现,只要将L型如图放置在棋盘的中央,就可以使四个子棋盘都变成特殊棋盘。此时问题也变成了四个相同的子问题,只需运用简单的递归就可以解决这道问题了。二位数组num:覆盖该格的L型的编号,下文所说的对方格赋值即对其对应的num赋值。x1,y1:当前棋盘左上角方格的行号与列号x2,y2:当前棋盘右下角方格的行号与列号x3,y3:当前棋盘中特殊格的行号与列号ck:当前棋盘的尺寸(2ck×um:umy3x3y2x2y1x1初始值:开始时,将num[x,y]设为0当ck=0时:棋盘尺寸为1×1,该格为已赋值的特殊格,不进行任何操作。xmymx1x2y1y2当ck>0时:设xm为(x1+x2+1)/2,ym为(y1+y2+1)/2,比较x3与xm,y3与ym的大小就能知道特殊格所在子棋盘的位置,um,并分别作为这三个子棋盘的特殊格。um增加1。再对这四个棋盘分别进行递归处理。复杂度分析时间复杂度:O(4k)空间复杂度:O(4k)由于覆盖一个2k×2k棋盘所需的L型骨牌个数为(4k–1)/3,故该算法是一个在渐进意义下最优的算法。,要遵循以下两点:。。但如果分割后必定留下剩余部分又该如何呢?下面这道例题就是用来解答这个问题的。例二:孔明棋问题(URAL1051)题目描述:在一个无限大的棋盘的节点上有一些棋子,这些棋子构成一个m×n的矩形(m为高度,n为宽度且1≤m,n≤1000)。你可以用一个棋子跳过另一个相邻的棋子,被跳过的棋子将被移去,请你求出最少能剩下几个棋子。一种移动方法输入:m,n输出:最少能剩下的棋子数样例:输入:34输出:2下面是一种走法:算法分析图(b)由于m=1或n=1的情况比较特殊,我们先处理m,n≥2的情况。为了叙述方便,我们称由棋子所在格子组成的棋盘为“真棋盘”。通过样例,我们可以发现,对于图(a)中位于4、5、6格的连续三个棋子,若第1、2、3格上无棋子而第7、8、9格上均有棋子的话,则可以通过图(b)的操作将这三个棋子移去。我们称4、5、6三颗棋子为模块1。963852741图(a)模块1剩余部分但是经过一些尝试后,我们发现只使用模块1对m×n的真棋盘进行分割效果并不理想。原因在于模块1每次对连续3行同时进行处理,当m不是3的倍数时,分割后总会留下剩余部分。(必须注意的是,图中用蓝框框起来的部分,必须等到其左边的棋子被去除后,才能成为模块1。)