搜索
“工大出版社杯”第十六届西北工业大学数学建模竞赛暨全国大学生数学建模竞赛选拔赛题目A题密封号2016年5月3日剪切线密封号2016年5月3日机电学院第8队队员1队员2队员3姓名姚泽全张阳杨儒童班级0501150205011502050115021目录一、摘要二、问题一1.提出问题分析2.定义符号说明3.提出假设4.数学推理证明三、问题二1.提出问题2.问题分析3.定义符号说明4.模型建立5.具体情况模型求解6.模型检验与分析7.模型的评价四、问题三1.提出问题2.问题分析3.定义符号说明4.模型建立5.模型求解6.模型的评价五、参考文献2一、摘要五子棋在中国文化里可谓是博大精深，蕴含着深刻的数学思想，而本文就对五子棋中的五连珠问题做出一些研究，在棋盘上的每个小方格中都放上棋子，从中取出一些棋子，使得棋盘上剩下的棋子，没有五个在一条直线（横、竖、斜方向）上依次相连，求满足条件的取出最少的棋子数。对于这道题目而言，三个问题从特殊到一般，从二维平面到三维空间。对于二维特殊问题的求解，可以根据简单的数学推理与图形演示来表达。而对于二维平面和三维空间这个一般问题而言，就不能通过简单的图示来表示，只能够通过计算机编程与优化进行讨论，而对于解法，我们则采用回溯法和递归的思想。针对问题一，在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。3我们在建立模型时主要利用C++进行编程，但是在编程中，由于在编译中存在一些对编码的理解和知识的缺乏，使得所编代码只能解决一些相对较小的二阶矩阵，对于较大的矩阵，可以输出最终k值，但是由于在定义时内存较短，使得对于大矩阵已发生溢出现象。所以这是此程序需要优化的地方。对于这类问题，如：五子连珠，井字游戏等一些有关于行，列，斜线不能有相同类型元素的排列上，均可以采取这种方法。利用回溯，递归，或者贪心的思想进行算法设计。二、问题一1.提出问题：如图，在6×7的长方形棋盘的每个小方格的中心点各放一个棋子。如果两个棋子所在的小方格共边或共顶点，那么称这两个棋子相连。现从这42个棋子中取出一些，使得棋盘上剩下的棋子，没有五个在一条直线（横、竖、斜方向）上依次相连。请用数学的方法解决最少取出多少个棋子才能满足要求？并说明理由。同时给出一种去掉棋子的方式。2.符号定义说明棋盘中用0表示取掉的棋子的位置，空白的位置表示有棋子。3.提出假设我们通过画图假设取出的最少的棋子数为k=8使其满足题意，使得棋盘上剩下的棋子，没有五个在一条直线（横、竖、斜方向）上依次相连。4.数学推理证明4（1）首先我们通过画图找到了一种k=8的情况是满足题意的，具体如下图：1234567123456（2）所以我们只需证明k=7的情况是不满足的。数学推理证明如下：棋盘的大小是6*7的，一共有6行7列，所以我们可以看出，要是每一行只能取掉一个棋子时，使其满足每行的任意相邻5个元素不相连的话，那么每行只能在第3，4，5列填0。如果每行不在第3，4，5列填0时，那么每行必须要调2个0才能满足行的条件成立。假设一：当每行只有一个0时，每行的0必须在第3，4，5列时，此时k=6，而第1，2，6，7列是没有0的，显然是不满足列条成立。假设二：当有5行满足每行只有一个0（每行的0放在第3，4，5列）000000005其余的一行放2个0（不在3，4，5列）此时k=7；然后我们看这种情况下的列条件是否满足：当5行的0最多满足第3，4，5列的列条件，其余一行的2个0最多满足2列的列条件，这样的话，满足的最多的列条件也只能是5列，其余的两列是没有一个0的，是不满足所有的7列的列条件成立的。因此k=7不成立。具体的一种情况如下图：三、问题二1.提出问题请针对任意规模m*n的棋盘，要求满足的条件与问题1相同。问至少去掉多少个棋子，可以使没有五个在一条直线（横、竖、斜方向）上依次相连。并对13×17的长方形棋盘，给出具体的求解结果，并将最后结果给出直观的棋盘表格显示。2.问题分析问题二是相对问题一的一般情况，将棋盘的大小扩充到m*n的情况，此时利用数学推理证明的思想是行不通的，我们的想法是利用数学建模的方法建立一般这两列没有0，不满足列条件成立6模型，然后设计算法，利用C++编程软件求解。首先采用0和1的思想，将取出的棋子的位置标为0，有棋子的位置标为1。我们将此问题抽象为一个二维平面坐标问题，每一个整数点相当于一个棋子所在的位置。而二维平面问题又可以抽象为一个二维数组问题，先将整个数组初始化为1，然后利用二维数组可以很方便的对整个平面进行遍历寻求0的个数。每行、列、对角线不能有连续的5个1，且求最少0的个数，所以要求每行、列中必须有4个连续的1存在，这样才能保证0的个数最少。通过对题目的数学理解，我们发现此题与“八皇后问题”十分类似，都采用“马走日”的思想。而不同点在于：“八皇后问题”中每行每列只有一个元素，对角上也只有一个元素。但对于“五子连珠”问题，每行每列可以有多个“0”元素，显然较之复杂。但是我们可以将其抽象为“五皇后”问题，然后进行5*5矩阵的叠加与和递归的想法，首先把第一行处理，然后其他行列根据第一行进行排列，最后输出整个矩阵与所求k值。而这个问题可以理解为是八皇后问题的更深层次的拓展，八皇后要求每行每列且对角线均不能有皇后。而此题应该这样来思考：将每5*5的一个方格看作是一个方阵，然后依次进行填充，其中每行（5个数）中不相邻的两个0就相当于两个“皇后”。然后将每个分开的5*5方阵进行叠加，叠加放入如下：首先将第一个方阵放置作为初始，然后放置第二个方阵，若初始的列数此时大于两个方阵平行放置的列数，则依次放置，当出现初始列数小于方阵平行放置的列数，则将多余的列按照从左到右从下到上的顺序依次排列。而当行数小于平行放置的方阵行数和时，则将行进行拆解，放置方式方式与列放置相同。在此问题的求解过程中，通过查阅资料与数学规律的探索中发现，以象棋中“马走日”的方式对0的位置进行安排可以得到最少的0的位置的探索。当每5*5的方阵进行顺次排列后，0的位置总是有规律的出现在一个“日”字上，而这个并非巧合。因为在每个5*5的方阵中，0必须安放在每一行每一列中，否则在进行方阵的叠加时可能会导致某一行或者某一列出现大于5个的1的出现。而为了避免此种现象的发生同时使得每行每列只有一个0的占据，只有当0的排布成“日”字时才满足条件。所以最终在程序的编写时，必须按照0中“日”的排布规律来进行设计。而每个5*5的基础矩阵如下所示：73.定义符号说明1表示有棋子，0表示取掉棋子。4.模型建立首先考虑最简单的情况，当棋盘列数小于等于4时，不存在列项以及斜向的考虑，此时的问题就转化为数轴上摆放棋子的问题，此时就只需要考虑第一行棋子，它的摆放必然为隔四个取出一子。当列数大于4时，我们可以将复杂的棋盘进行分解，将其转化为5*5的形式，具体做法为：（1）首先定义一个row行column列的二维数组，数组可以理解为一个矩阵，所以rowcolumn之间没有严格的界定，即我们可以将棋盘旋转，为了编程方便，当出现rowcolumn时，进行平置矩阵。（2）用for循环将所有的初始值都赋为1，表示将棋盘上布满棋子。（3）由资料可知，马走日的方法能够实现5*5矩阵的优化，所以进行马走日的推广，即只要出现一个可以走日的地方，将该处的值赋为0，表示将该棋子拿走，并且每拿走一颗棋子，计数变量num加一（马走日）的示意图如下：11110101111110101111110118111101101111111011011110110111（4）将得到的新的矩阵输出，并且输出计数变量num的值。当行列数增加时，我们只需要进行的是5*5的小块进行堆砌。编程代码如下：#includeiostream#includecstring#includecmath#includeiomanipusingnamespacestd;intmain(){introw,column;cinrowcolumn;if(rowcolumn)swap(row,column);//平置矩阵charmap[row][column];intnum=0;for(inti=1;i=row;i++){for(intj=1;j=column;j++){map[i][j]='1';}}9if(column4){for(intj=1;j=column;j++){if(j%5==0){map[1][j]='0';num++;}}}for(inti=1;i=row;i++)//用来判断“马走日”{for(intj=1;j=column;j++){if(map[i][j]=='0'){if((i-1)0&&(i-1)=row&&(j-2)0&&(j-2)=column&&map[i-1][j-2]=='1'){map[i-1][j-2]='0';num++;}if((i-2)0&&(i-2)=row&&(j+1)0&&(j+1)=column&&map[i-2][j+1]=='1'){map[i-2][j+1]='0';num++;}if((i+1)0&&(i+1)=row&&(j+2)0&&(j+2)=column&&map[i+1][j+2]=='1'){map[i+1][j+2]='0';num++;}if((i+2)0&&(i+2)=row&&(j-1)0&&(j-1)=column&&map[i+2][j-1]=='1')10{map[i+2][j-1]='0';num++;}}}}for(inti=1;i=row;i++){for(intj=1;jcolumn;j++){coutmap[i][j];}coutmap[i][column];coutendl;}coutThethrownumberis:endl;coutnumendl;return0;}5.模型求解.运行结果如图11具体棋盘图如下：1111011110111101110111101111011110111011110111101110111101111011110111011110111101111111101111011110111011110111101111011101111011110111011110111101111011101111011110111111110111