欢迎来到文档下载导航网!

组合数学CH01[共64页].ppt

时间:2020-12-10|当前位置:首页 > 教育文档 > 高等教育 > |用户下载:

组合数学CH01[共64页].ppt


本文档部分文本预览

组合数学;*;*;*;四色问题;装箱问题;过河问题;*;*;棋盘完美覆盖问题; 组合数学简称 组合学, Combinatorics ;*;*;*;*;*; (1) 存在性问题对于模式要证明或否定它的存在;(3) 构造性问题 通过程序化的方法把相应的模式枚举或构造出来;*;1;*;*;*;*;例 1.1 证明不存在2阶幻方; 幻方的构造性问题(1)奇数阶幻方的构造;如果行号变成0(第1行上面一行),则改成第n行相应列对应的方格。如果列号变成n+1(第n列右面一列),则改成第1列相应行对应的方格。如果轮到的方格已经填有数字或者到了第0行第n+1列对应的方格,则退到前一个方格正下方的方格。 ;例1.2 利用连续摆放法构造5阶幻方 ;(2)偶数阶幻方的构造 当n=4k的时候,即双偶数的情况,对称法。先把n×n的方阵分成上、下、左、右四个2k×2k的方阵。然后对于左上的2k×2k方阵进行处理,每行每列任意取一半(k个)的方格做标记,如我们把这些方格涂成阴影。;然后按照对称轴将这种标记方式向下和向右作对称图形。经过处理后使得n×n的方阵的每一行和每一列都有一半(n/2)的方格被涂成阴影。接下来,把从1开始的数字依次往方格里面填。第一遍:从第1行第1列的方格开始往右,不是阴影,则填数字,如果是阴影的方格,不填数字,但相应的数字加1。第1行填完后,是第2行第1列的方格,依次,最后是第n行第n列的方格。;这样填完之后,有一半的方格被填上了数字。第二遍,从第n行第n列的方格开始依次往左,规则同前,从1开始的数字依次往方格里面填。第n行结束之后,是第n-1行第n列的方格。依次,最后是第1行第1列的方格。最后就得到了幻方。; 例1.3 利用对称法构造4阶幻方 ;当n=4k+2,所谓的单偶数的情况。首先把n×n的方阵分成上、下、左、右四个(2k+1)×(2k+1)的方阵,为了表达方便,依次把左上、右下、右上、左下的方阵编号为A,B,C,D。采用连续摆数法,把1~(2k+1)2放在A中做成第一个幻方;把(2k+1)2+1~2(2k+1)2放在B中成第二个幻方。;把2(2k+1)2+1~3(2k+1)2放在C中成第三个幻方。把3(2k+1)2+1~4(2k+1)2放在D中成第四个幻方。然后,在A的各行从第1列开始向右取m个(m=(n-2)/4)方格,但中间一行(k+1行)从第2列开始。;把??些方格中的数字与D中相应位置的数字对换。在C中各行最后一列起向左各取m-1个方格,把这些方格中的数字与B中相应位置的数字对换。最后,就得到了幻方。;例1.4 构造6阶幻方 ;1; 幻方的计数问题 ; 5阶幻方 基本形式有275305224个;§1.2 拉丁方问题;拉丁方存在性问题 ;n阶拉丁方是存在的 构造方法如下:第1行为(1,2,3…,n)第2行是(2,3,…,n,1),…第k行为(k,k+1,…,n,1, …,k-1),…,第n行为(n,…,3, 2, 1)。 ;例1.5 设计一个药物临床试验以测试五种药物对人体的药效。这五种药物编号1,2,3,4,5。然后选取5个人,并给每人不同的药。为了消除个体对药物的反应偏差,要求在连续5天里进行测试,每人每天吃一种药物。而为了消除服药时间造成药效的偏差,要求2个人不能在同1 天吃相同的药。 ;最后满足要求的实验是要形成由1,2,3,4,5构成的5×5的方阵,其中每行每列中没有相同的数字,即5阶拉丁方的构造问题。;2; 正交拉丁方;*;*;*;*;*;*;*;§1.3 涂色问题 ;例1.6 对正三角形的三个顶点涂以红、蓝(r和b)两种颜色,求有多少种不同的涂色方案? ; 涂色方案可分成四类:;;如果考虑正三角形可以旋转,则(3),(4),(5)显然是同一个涂色方案,(6),(7),(8)也是同一个涂色方案,这样涂色方案数就变成了4种。如果变成了空间的四面体了,即加上空间的旋转之后,涂色方法的计算将更加复杂。要涂色的点和可选颜色的数目如再增加的话,枚举方法就不奏效了;*;*;*;*;*;*

继续预览文档剩余内容

温馨提示:本页预览文本内容并非错乱,是从文档中提取部分无格式预览!如您需要正常预览文档全文,请点击下方按钮↓↓↓

上一篇:教务行政管理617.docx

栏    目:高等教育

下一篇:社区管理学题库(次)(资料).pdf

本文标题:组合数学CH01[共64页].ppt

本文地址:https://www.365weibook.com/html/20201210/467433.html

    正常预览或下载提示:

    本页面文档预览是由服务器自动提取的部分内容,并不是文档错乱。如您需要预览全文或下载文档,请点击页面左侧(点击去预览文档全文或下载文档)按钮,进行全文预览或下载。

推荐下载

联系我们 | 广告投放 |网站地图

免责申明:本网站不提供任何形式的下载服务,因此与之有关的知识产权纠纷本网站不承担任何责任。

如果侵犯了您的权利,请与我们联系,我们将进行删除处理。