资源预览内容
第1页 / 共4页
第2页 / 共4页
第3页 / 共4页
第4页 / 共4页
亲,该文档总共4页全部预览完了,如果喜欢就下载吧!
资源描述
1图 1 A5A4A3A1A2B6B3B4B5B2B1BA图 2一类计数问题的解答模式江苏省无锡市第一中学李广修(214031)两个经典问题:问题 1 (参见文 1),如图 1,墙上挂着两串 礼物 A i (i=1,2,,5)和 B j(j=1,2,,6) ,每次从某一串的最下端摘取一件礼物,这样摘了 11 次,可将礼物全部摘完,那么对于这 11 件礼物共有多少种不同的摘取顺序?问题 2(参见文 2),如图 2,求从点 A 顺着纵线或横线走(在纵线与横线交点处可以改变方向)到点 B 的最短路径数.我们来分析这两个问题的共性:(1)都是计数型问题.(2)都含有“阵线分明”的两类元素.在问题 1 中,两类元素是 A 类礼物和 B 类礼物,它们各自串在一起;在问题 2 中两类元素是横线段和纵线段.(3)每类元素有确定的顺序.在问题 1 中,摘取礼物之前每类礼物顺序已定,每次都是从某串礼物的最下端摘起;在问题 2 中,所有的横线段具有从左至右的顺序,所有的纵线段具有从上至下的顺序.(4)在两类元素合并操作时,一类元素在整体中的“位次”确定以后(他们的先后“位次”不改变) ,另一类元素在整体中的“位次”2A2A1 A5A4A3B3 B6B5B4B1 B2BA图 3也就随之唯一确定.我们将这类计数问题称为分类有序混排计数问题. 我们再来分别解答这两个问题:问题 1 解答:将一排 11 个空格 ,从左至右依次记为第 1 格,第 2 格,第 11 格,对摘取的礼物作如下放置:第 1 次摘取的礼物,放置于第 1 个空格中,第 2 次摘取的礼物放置于第 2 个空格中,第 11 次摘取的礼物放置于第 11 个空格中.例如,摘取礼物顺序是 B1, B2, B3, A1, B4, A2, B5, A3 , A4, A5, B6时,我们用 来表示. 这样放置摘取礼物的方法,使得放置礼物 Ai(i=1,2,,4)格子的序号比放置礼物 A i1 格子的序号小,放置礼物 Bj(j =1,2,,5)格子的序号比放置礼物 Bj1 格子的序号小.所以,当 A 类礼物按某种方式在 11 个空格中放置以后,B 类礼物的放置方式也就唯一确定了.不同放置礼物顺序数,就是在 11 个空格中放置 A 类礼物的不同方法数,也就是摘取 11 件礼物的不同顺序数,即 462. 51C问题 2 解答:我们第 i 列 6 条横线段记为 x i(i =1,2,8) ,第 j 行的纵条线段记为 yj(j=1,2,5). 例如图 3 中从点 A 到点 B的一种最短路径(由粗线条所连接的折线)表示为 x1y1x2x3y2y3x4x5y4x6x7x8y5 .这样的表示,使得所有最短路径和xi(i=1 ,2,8)与 yj(j=1 ,2,5)某个排序对应,又 xi 的排序确定之后, yj 的排序也唯一确定了,即确定3A1B2 A4A3A2 B5B1 B3 B4 B7B6 A6 A7A5某个 A 到 B 的最短路径.由于 xi 要在 xi1 前(i=1,2,7) ,故它的不同排序数有 =1287 种 ,从而,从点 A 到点 B 的最短路径数为 1287. 813C由上面的解答,我们可以概括出分类有序混排计数问题的解答模式: 首先,辨别它是有序混排问题;其次,弄清楚问题中两类元素各有多少个参加“排位”. 最后,计算出“排位”数.其中,弄清楚问题中两类元素各有多少个参加“排位”是关键也是难点,需要通过对几个具体“排位”观察、概括,才能获得参与“排位”的两类元素数目.比如对于问题 2,要经过几次具体最短路径走法的“比划” ,才可能发现每次“排位”x i 与 yi 的一个“排位”. 分类有序混排计数问题的求解模式的应用:问题 3:甲、乙两队各出 7 名队员按事先确定好的顺序出场参加围棋擂台赛.双方先由 1 号队员比赛,负者被淘汰,胜者再与负方2 号队员比赛,直到有一方队员全被淘汰为止,这时另一方就获得了胜利.这样,就形成一种比赛过程.那么所有可能出现的比赛过程有多少种?解:这是一个分类有序混排计数问题. 记甲队 1 至 7 号队员分别为 A1,A 2,A 7;乙队 1 至 7 号队员分别为 B1, B2, , B7.假设在比赛结束后,让两个队队员这样排成一行:从左至右依次为第一场比赛被淘汰的队员,第二场比赛被淘汰的队员,最后一场比赛被淘汰的队员(只能是 A 7 或 B7),接下来排未被淘汰的队员. 假如未被淘汰的队员仅剩一人,则让这名队员排在最右边;假如未被淘汰的队员有多名,这多名队员必是同一个队的,让这些队员按4A1B2 A4A3A2 B5B1 B3 B4 B7B6 A6 A7A5A1B2 A4A3A2 B5B1 B3 B4 B7B6 A6 A7A5事先确定好的顺序排位.显然,这样排队,使得甲乙两队 14 名队员都排在其中,并且 A i1 在 A i 的右边(i=1,2, ,6)(A i1 和 A i 不一定相邻) ;B i1 在 Bi 的右边(i=1,2,,6)( Bi1 和 Bi不一定相邻).假如排在甲队队员 A i、 A i1 (i=1,2,,6)之间有乙队队员,则这些乙队队员是被甲队队员 A i1 所淘汰的.假如排在乙队队员Bi、B i1 (i=1,2,,6)之间有甲队队员,则这些甲队员是被乙队队员 Bi 1 所淘汰的.排在最左边的某个队队员以及与之连排在一起的该队队员,是被另一个队的 1 号队员所淘汰的. 例如, 表示乙队第 1、2 名队员被甲队第 1 名队员所淘汰,甲队第 1、2 名队员被乙队第 3 名队员所淘汰,甲队第 6、7 名队员还未上场就已经获得胜利.这样的排队方式和甲、乙两队的比赛过程一一对应,从而所有可能出现的比赛过程有 =3432 种. 41C参考文献周士藩. 逐点累加法例析.中学数学月刊.2006.6赵红玲. 矩形格中的最短路径与杨辉三角.数学教学.2004.2(本文载于数学教学2007 年 4 期)
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号