第二章——建模方法示例
第二章 建模方法示例§2.1 棋子颜色的变化2.1.1. 问题描述任意拿出黑白两种颜色的棋子共 n 个,排成如图 2.1.1 所示的一个圆圈.然后在两颗颜色相同的棋子中间放一颗黑色棋子,在两颗颜色不同的棋子中间放一颗白色棋子,放完后撤掉原来的棋子.再重复以上的过程,这样放下一圈后就拿走前次的一圈棋子,问这样重复进行下去各棋子的颜色会怎样变化呢?请研究不同的 n 对应的规律.2.1.2. 基本假定 若两个图可以通过旋转某个角度后重合, 则认为它们是等价的.2.1.3. 建立模型首先，为了探索棋子颜色的变化规律，我们建立棋子颜色与实数的对应关系，因为“同色为黑，不同色为白” ，正好与实数中“同号乘积为正，异号乘积为负” 对应.于是建立“黑对应+1，白对应-1”的对应关系 .这样我们就可用棋子的对应“值”图2.1.1表示其颜色了.设 aj 表示第 j 个棋子的初值(+1 或-1)，j=1,2,n, 每个棋子的值就是上一步相邻的两个棋子的值之积，为观察每步的变化规律，以 n=5 为例看看 .表 2.1.1初 值 1a2a3a4a5a第 1 步 23451第 2 步 132423524125第 3 步 24a35a41a35a31a第 4 步 61354621635246124652第 5 步 50241505321043505341053发现规律了吗? 第 i 步的指数恰好是二项式 展开式的系数(杨辉三角形)iab一般地,第 i 步第 j 个棋子的值为, (i,j=1,2,3,n),012(,) iiiiCCjjjjfijaa当然下标的值是关于模 n 计算的. 2.1.4. 寻找规律通过对 f(i,j)的分析便可以知道棋子颜色的变化规律, 并且说明其原理.(1)无论棋子数 n 如何,初态如何, 变化最终总是周期性的.这是因为 n 个棋子的布局只有有限种, 且每步的变化规则是相同的.从而每步的布局由上一步的布局唯一确定.(2) 无论棋子数 n 如何, 初态如何, 每一步的白子数如果大于零,则总是偶数.因为每步可以把上一步视为初态, 故只需说明从初态到第一步的变化规律.若初值中有 s 个 -1, 且没有任两个相邻,则第一步就有 2s 个 -1.例如, n=8, ,其余为 1, 则2471a.123456781aaa若初值中有 s 个 -1, 且其中有 t 个相邻间隔,则第一步就有 2s-2t 个 -1.例如, n=8, , 其余为 1, 则其中有 3 个相邻间125681aa隔: . 只有 , 其余为 1.125681, , a:23456781a(3) 当 (m=1,2,)时,第 n 步全部棋子黑色,即n(,),2)fjj如果对 m 应用数学归纳法及其利用组合公式 1 112220mmmkkkjkjjCC可以证明 都是偶数, 故2(1,)mkn，(j=1,2,n)12 2(,) 1nCjjjnjfnjaa(4) 当 (m=1,2,)时,第 n+1 步与第 1 步等价2, (j=1,2,n)12111(1,) )nCjjjnjfnjaaaf例如 n=7 时, 第 8 步与第 1 步等价.(5) 当 (m=1,2,)时,第 n-1 步与第 1 步等价21n, (j=1,2,n)121(,) (,)nCjjjnjfaafj例如 n=9 时, 第 8 步与第 1 步等价.§2.2 商人们怎样安全过河2.2.1 问题描述三名商人各带一个随从乘船渡河，现此岸有一小船只能容纳两人，由他们自己划行.随从们密谋，在河的任一岸，一旦随从比商人多，就杀人抢劫.但是如何乘船渡河的大权由商人们掌握.商人们怎样才能安全过河？此类问题当然可以通过一番思考，拼揍出一个可行方案来.但是，我们现在希望能找到求解这类问题的规律性，这有利于编程和推广应用.2.2.2 模型的假设模型已理想化，不必再作假设.2.2.3 模型的构成此问题可视为一个多步决策问题，每一步就是一次渡河，每次渡河就是一次状态转移.1. 未考虑船时的安全状态设（x,y）表示此岸有 x 个商人和 y 个随从的状态，商人们安全是指在两岸都安全，故当 x=0,3 时，y=0,1,2,3 均可，而当 x=1,2 时,此岸要求 xy,对岸要求 3-x3-y, 综合即 x=y安全状态= 0,123 0,3y12x当当从而此岸在以下状态时，商人们在两岸都安全 (3,3) (3,2) (3,1) (3,0) (2,2)(1,1) (0,3) (0,2) (0,1) (0,0)2. 考虑船时此岸的安全状态用（x,y,z ）表示此岸的状态，x,y 的含义同前，z 表示此岸的船数.即 z=1 时，船在此岸，z=0 时，船在对岸.此岸的安全状态有：(3,3,1) (3,2,1) (3,1,1) (2,2,1) (3,0,1) (0,3,1) (0,2,1) (1,1,1) (0,1,1)(3,2,0) (3,1,0) (2,2,0) (3,0,0) (0,3,0) (0,2,0) (1,1,0) (0,1,0) (0,0,0)2.2.4 模型求解所谓求解，就是寻找此岸状态从(3,3,1)转移到(0,0,0)的方案.根据题意，状态转移时要满足下面的规则：1. z 从 1 变为 0 与从 0 变为 1 交替进行；2.当 z 从 1 变为 0 时，即船从此岸到对岸，此岸人数减少1 或 2 个；即(x,y,1)(u,v,0)时, ux, vy, u+v=x+y-1 或 u+v=x+y-23. .当 z 从 0 变为 1 时，即船从对岸到此岸，此岸人数增加1 或 2 个；即(x,y,0)(u,v,1)时, ux, vy, u+v=x+y+1 或u+v=x+y+24.不重复已出现过的状态，如(3,3,1)(3,1,0)(3,3,1) ；若一状态 A 可转移到另一状态 B，则我们用一箭号将这两个状态联结起来。按照以上规则，求解过程如图 2.2.1（总人数从多到少排列）(3,3,1) (3,2,0)(3,2,1) (3,1,0)(3,1,1) (2,2,0)(2,2,1) (3,0,0)(3,0,1) (0,3,0)(0,3,1) (0,2,0)(0,2,1) (1,1,0)(1,1,1) (0,1,0)(0,1,1) (0,0,0)其解即：(3,3,1)(3,1,0) 或(2,2,0)(3,2,1) (3,0,0)(3,1,1)(1,1,0)图2.2.1(2,2,1)(0,2,0)(0,3,1) (0,1,0)(0,2,1)或(1,1,1)(0,0,0)可见，有四个渡河方案，每个方案经 11 步.可解释如下:(1) 2 随从(或 1 商人 1 随从)去(7) 2 商人去(2) 1 随从(或 1 商人 )回 (8) 1 随从回(3) 2 随从去 (9) 2 随从去(4) 1 随从回 (10) 1 随从(或 1 商人 )回(5) 2 商人去 (11) 2 随从( 或 1 商人 1 随从)去(6) 1 商人 1 随从回2.2.5 平面坐标解法设 x 为商人数，y 为随从数，在 xoy 平面上作分析.如图，先把此岸的安全状态点标出.用 di 表示第 i 次状态转移，i 为奇数时，船从此岸到对岸，x, y 只能减少，不能增加，且 x+ y 至多减少 2，即移向左下方，且至多移两格.i 为偶数时相反.怎样从状态(3,3)转移到(0,0)? 过程如图 2.2.2 所示.2.2.6 进一步的思考(1)若船的情况不变，则 2 名商人 2 个随从如何安全渡河？ 答案：(2,2)(1,1) 或(2,0)(2,1) (0,1)(1,1) 或(0,2)(0,0) （2）m 名商人 m 个随从(m4)能否安全渡河？答案：m 名商人 m 个随从(m4)无法安全渡河,如 m=4 时的图图 2.2.2d4 d5图 2.2.32.2.4，d7 就无法作不重复的转移.其他情况也一样.（3）一般地，m 个商人 n 个随从,m >n 能否安全渡河? 若能,怎样渡河？答案：当 x=0,m 时，y=0,1,2,n 均可，而当 x=1,2,m-1 时,此岸要求 xy,对岸要求 m-xn-y, 综合即 0x-y m-n安全状态=0,12.,n ,-(m)yx12.m-yx， 当， 当此时商人们必能安全渡河.若以 m=4,n=3 为例，则求解过程如图 2.2.5§2.3 公平的席位分配图 2.2.4图 2.2.52.3.1 问题的提出设某校有 3 个系共 200 名学生，其中甲系 100 人，乙系 60人，丙系 40 人，现要选出 20 名学生代表组成学生会，公平的办法是按学生人数的比例分配席位，即甲乙丙系分别占 10、6、4个席位.若按学生人数的比例分配的席位数不是整数，就会带来一些麻烦.比如甲系 103 人，乙系 63 人，丙系 34 人，怎么分？过去的惯例是这样分配的:先按比例分配,甲、乙、丙系分别应得10.3、6.3 和 3.4 席,舍去小数部分后分别得 10、6、3 席,剩下的 1席分给“损失”最大(即小数部分最大)的丙系,于是三个系仍分别占 10、6、4 席.假定学生会的席位数增加到 21 位，按上述方法重新分配，结果如表 2.3.1 所示，甲乙丙系分别占 11、7、3 席.表 2.3.120 席的分配 21 席的分配系别 人数 比例按比例分 实际分配 按比例分 实际分配甲 103 51.5 10.3 10 10.815 11乙 63 31.5 6.3 6 6.615 7丙 34 17.0 3.4 4 3.570 3合计 200 100.0 20.0 20 21.000 21此分配结果,对丙系显然是不公平的,因为席位增加了,而丙系得到的席位反而减少了.2.3.2 符号和假设我们要解决的是这样的一个问题：某校共有 m 个系，第 i 系学生数为 ni(i=1,2,m)，校学生会共设 N 个席位.怎样才能公平地把这些席位分配给各系？显然，m，n i(i=1,2,m)应为正整数，全校学生数记为.假设每个系至少应分得一个席位（否则把其剔除） ，至i1多分得 ni(i=1,2,m)个席位，n>N m.全校而言，每个席位代表的学生数记为 a=n/N,第 i 系按学生数比例应分得的席位为，最后实际分得的席位数为 Ni(1 Ni ni,整数)，每aNniii个席位代表的学生数为 (i=1,2,m).iiNna2.3.3 确定“公平”的标准我们可以提出不同的标准来衡量分配方案的”公平” 的程度, 例如标准 1 要求 最小（对不同方案而言）; amxz ii标准 2 要求 最小;ii|1标准 3 要求 最大; anz i标准 4 要求 最小;mii)(122.3.4 “判别数 ”分配方法按标准 1, 可认为，a i 越大的系越吃亏，故应尽量优先照顾之. i 取整后，每个席位代表的学生数为 ()(1)iiii iana其中 ，称为判别数. 表示 i 小数部分. i 越大的系越吃iii亏，按标准 1，应优先照顾.分配方法的算法流程如图 2.3.1，其中 .i11 mmiiirN例 2.3.1 对刚才的例子用此算法重新分配, 先算 i， 再算 i 然后进行分配.图2.3.1对 i 较大的 r 个系分配席位 Ni= i+1否是开始输入 ni 与 N计算 n 与 i i 全为整数吗？计算 i 与 rNi= i输出各 Ni结束剔除已分配席位的系和席位数有为 0 的 吗?
