情况相关毕业论文格式模板范文与消除五子连珠情况的策略有关学年毕业论文范文

《消除五子连珠情况的策略》

本文是关于情况方面学年毕业论文范文和五子连珠和五子连珠情况和策略类专升本论文范文。

摘要五连珠是五子棋中抽象出来的问题,本文通过对五连珠问题的研究与求解,得到了在二维棋盘中,去掉最少棋子,以达到整个棋盘在横、竖、斜三个方向都不出现五子连珠的方法.

关键词抽屉原理n 皇后问题贪心算法回溯算法分治法

1 二维特殊问题

问题：有一个6×7 的长方形棋盘.现从这42 个棋子中取出一些,使得棋盘上剩下的棋子,没有五个在一条直线（横、竖、斜方向）上依次相连.请用数学的方法解决最少取出多少个棋子才能满足要求？并说明理由.同时给出一种去掉棋子的方式.

模型建立与解决：

1）符号说明.

K：当前取出棋子的个数

M：棋盘的长

N：棋盘的宽

Min ：最少需要取出的棋子个数

2）证明至少需要取出8 个棋子才能满足题意.6×7 棋盘相对比较特殊,于是我们将该棋盘做如下分割,A 区域：棋盘左侧五列；B 区域：右侧两列的上方五行；C区域：右侧两列下方一行.同时假设Ka 是A 区域需要取出的棋子数,Kb 是B 区域需要取出的棋子数,Kc 是C 区域需要取出的棋子数.

根据抽屉原理（也作鸽巢原理）,A 区域中的6 行×5列,假设只取出5 个棋子,则至少有一行没有取出棋子,也是说只取出五个棋子的情况下,必然有一行会出现连珠的情况.于是A 区域至少需要取出6 个,至于A 区域取出6 个的正确性会在下一步给出证明.即Ka≥6；

同理,对于B 区域的的5 行×2 列,至少需要取出2 个棋子,即Kb≥2；

对于C 区域,不能保证是否一定需要取出棋子,需要分情况考虑,所以它至少需要取出0 个棋子.Kc≥0；

所以,K等于Ka+Kb+Kc ≥6+2+0等于8 .即,至少需要取出8 个棋子才能满足要求.

3）举例证明当K等于8 的时候可以满足题意.

将左上角设为（0,0）,自左向右为X 轴正方向,自上向下为Y 轴正方向.则去掉的棋子坐标为（3,1）,（1,2）,（5,2）,（4,3）,（2,4）,（7,4）,（5,5）,（3,6）.综上所述：首先,已经证明取出的棋子个数不,小于8,才能满足题意.其次,我们找到了一种去掉8 个棋子的可行解.所以可以得出结论：最少取出8 个棋子即可.

2 二维一般问题

问题：对任意规模的棋盘,要求满足的条件与问题1 相同.问至少去掉多少个棋子,可以使没有五个在一条直线（横、竖、斜方向）上依次相连.

符号：

[decimal]：代表向下取整

K：当前取出棋子的个数

M：棋盘的长

N：棋盘的宽

Min：最少需要取出的棋子个数

T：特殊矩阵

Ka（Kb,KcKd）：A（B,C,R）区域需要取出棋子的个数模型的建立：

1）分割棋盘.

我们将一个M*N 的棋盘分割成如下图四个部分：A 区域；B 区域；C区域；D 区域.依次找到这些区域满足整个问题结果最小的条件下的最优解.