文档介绍：“工大出版社杯”第十六届西北工业大学数学
建模竞赛暨全国大学生数学建模竞赛选拔赛题目
A题
密封号
2016年5月3日
剪切线
密封号
2016年5月3日
机电学院第 8 队
队员1
队员2
队员3
姓名
姚泽全
张阳
杨儒童
班级
05011502
05011502
05011502
目录
一、摘要
二、问题一
三、问题二
四、问题三
五、参考文献
一、摘要
五子棋在中国文化里可谓是博大精深,蕴含着深刻的数学思想,而本文就对五子棋中的五连珠问题做出一些研究,在棋盘上的每个小方格中都放上棋子,从中取出一些棋子,使得棋盘上剩下的棋子,没有五个在一条直线(横、竖、斜方向)上依次相连,求满足条件的取出最少的棋子数。
对于这道题目而言,三个问题从特殊到一般,从二维平面到三维空间。对于二维特殊问题的求解,可以根据简单的数学推理与图形演示来表达。而对于二维平面和三维空间这个一般问题而言,就不能通过简单的图示来表示,只能够通过计算机编程与优化进行讨论,而对于解法,我们则采用回溯法和递归的思想。
针对问题一,在6*7的棋盘上取出一些棋子,我们采用数学推理证明的思想得出答案,通过画图找到一种取出8个棋子满足,之后我们通过在一些规律下的逻辑推理证明7个确实不满足要求,所以8个为最终解。
针对问题二,则是相对问题一的一般情况,将棋盘的大小扩充到m*n的情况,此时利用数学推理证明的思想是行不通的,我们的想法是首先采用0和1的思想,将需要取出的棋子的位置标为0,有棋子的位置标为1 。每一个棋盘的位置点可以用一个二维数组char[row][column]来表示。通过对题目的数学理解,我们发现此题与“八皇后问题”十分类似,都采用“马走日”的思想。但对于“五子连珠”问题,每行每列可以有多个“0”元素,显然较之复杂。但是我们可以将其抽象为“五皇后”问题,然后进行5*5矩阵的叠加与和递归的想法,首先把第一行处理,然后其他行列根据第一行进行排列,最后输出整个矩阵与所求k值。
之后利用这个数学模型求出17*13棋盘的满足条件的k值为44。
针对问题三,是在问题二的二维平面扩充到三维的立体网格m*n*p的棋盘,这个问题和第二问题的想法是相似的,只是将“平面八皇后问题”转化为“空间八皇后问题”。可以考虑将空间整数点用三维坐标表示后,首先固定其中一个与
X轴平行的平面作为初始平面(此平面的选取可以为任意与X轴,Y轴,Z轴垂直的平面),利用问题二中算法定出这个面的棋子摆放位置,然后分别利用其行,列来确定行列所在垂直平面上棋子的摆放位置,此时整个空间的点已经摆放完整,可以利用与最初选定的平面平行的平面进行验证斜线和这些平面上的点是否满足条件。最后利用计算机模型求出6*7*6的空间网格求出满足题意的最小k
值为51。
我们在建立模型时主要利用C++进行编程,但是在编程中,由于在编译中存在一些对编码的理解和知识的缺乏,使得所编代码只能解决一些相对较小的二阶矩阵,对于较大的矩阵,可以输出最终k值,但是由于在定义时内存较短,使得对于大矩阵已发生溢出现象。所以这是此程序需要优化的地方。
对于这类问题,如:五子连珠,井字游戏等一些有关于行,列,斜线不能有相同类型元素的排列上,均可以采取这种方法。利用回溯,递归,或者贪心的思想进行算法设计。
二、问题一
:
如图,在6×7 的长方形棋盘的每个小方格的中心点各放一个棋子。如果两个棋子所在的小方格共边或共顶点,那么称这两个棋子相连。现从这42 个棋子中取出一些,使得棋盘上剩下的棋子,没有五个在一条直线(横、竖、斜方向)上依次相连。请用数学的方法解决最少取出多少个棋子才能满足要求?并说明理由。同时给出一种去掉棋子的方式。
棋盘中用0表示取掉的棋子的位置,空白的位置表示有棋子。
我们通过画图假设取出的最少的棋子数为k=8使其满足题意,使得棋盘上剩下的棋子,没有五个在一条直线(横、竖、斜方向)上依次相连。
数学推理证明
(1)首先我们通过画图找到了一种k=8的情况是满足题意的,具体如下图:
1 2 3 4 5 6 7
0
0
0
0
0
0
0
0
1
2
3
4
5
6
(2)所以我们只需证明k=7的情况是不满足的。数