tceic.com
简单学习网 让学习变简单
相关标签
当前位置:首页 >> 学科竞赛 >>

备战NOIP2010提高组初赛复习——问题求解篇


备战 NOIP2010 提高组初赛复习——问题求解篇

问题求解是信息技术竞赛初赛中常见题型,它共两题,每题 5 分,共 10 分。诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合问题、逻辑推理、 递推关系等问题出现在问题求解中,但是在实际的竞赛中,问题求解得分率往往 是不高的,下面我对问题求解的题型进行了一下探索。

一、寻找假币问题


有 n(n?3)个硬币,其中一个是假币,已知假币的重量比其他的要重一些, 你有一架天平。现在要称出哪个假币来。

解析: 首先我们先来考虑最简单的问题 1。为了方便叙述,把 n 个硬币按 1,2,?,n 顺次编号。 若 n=3,把一号硬币放在天平左边、二号硬币放在天平右边。如果天平: 1、左偏,一号重,是假币。 2、右偏,二号重,是假币。 3、保持平衡,那么一、二都是正常的硬币,因此就只有可能三号硬币是假 币了。 因此 n=3,至多一次就能称出哪个是假币。记作 f(3)=1。 下面考虑 n=9。把所有的硬币分成三组:A{1,2,3},B{4,5,6},C{7,8,9}。A 组 的硬币放在左边、B 组放在右边。如果天平: 1、左偏,则假币在 A 组里面。 2、右偏,则假币在 B 组里面。 3、保持平衡,假币在 C 组里面。 无论在哪个组里面,我们已经把假币的范围从“9”缩小到了“3”,也就是 减少到原来的 1/3。 之前我们已经研究过, 个硬币 1 次就能称出来, 3 故而 f(9)=2。 不难推广到一般的情况:

定理 1.1 f(3n)=n。 证明:n=1,2 时,已证。设 n=k 成立,则 f(3k)=k;下面考虑 n=k+1 的情况。 将 3k+1 个硬币分成三堆 A, B, C,使得|A|=|B|=|C|=3k。把 A 放在天平左边、 B 放在右边,天平: 1、左偏,假币在 A 2、右偏,假币在 B 3、平衡,假币在 C 无论哪种结果,我们都把假币的范围缩小到了 3k 个硬币里面。而 f(3k)=k, 故而 f(3k+1)=k+1。 综上,定理 1.1 成立。 稍经分析不难得到: 定理 1.2 f(n)= ?log 3 n ? 这个的证明和定理 1.1 完全类似,分 n mod 3 = 0, 1, 2 适当讨论即可。 我们必须注意到 ?log 3 n ? 是可行的,因为我们能够构造出这样一个方案。问题 是它是否最优? 我们采取的方案是每次将硬币尽量均匀的三分,这样做的根据就是天平只有 三种结果:左偏、右偏、平衡。于是就能保证无论假币在哪一份都能将结果的范 围缩小到原来的 1/3。从感性上认识, ?log 3 n ? 应该就是最优解了。 为了更加严格的证明 ?log 3 n ? 的最优性,我们引进判定树的概念。
下图就是 n=9 时的一种判定树: 比较(1,2,3)与(4,5,6) > 比较(1)与(2) > 1 3 = < 2 7 > 9 = 比较(7)与(8) = < 8 4 > < 比较(4)与(5) = 6 < 5

此题的判定树是这样一棵树:

1、叶子节点代表一种可能的结果。

2、非叶子节点代表一次称量。 3、非叶子节点至多有三个儿子,分别代表天平的左偏、右偏、平衡三种情 况。 任意一种称量方案都能唯一的表示成一棵判定树; 反过来一棵判定树也唯一 对应一种称量方案。 容易看出判定树的深度就是称量次数。这就是我们之所以引进它的原因。 做出判断之前, 谁也无法预知哪个硬币是假币, 每个都有可能是我们的目标; 因此一个有意义的判定树应该具有至少 n 个叶子节点。 n 个叶子节点的树的深度 h ? ?log 3 n ? ,故而可以证明,f(n)= ?log 3 n ? 是最 优的。 我们的结论是:有 n(n?3)个硬币,其中一个是假币,假币的重量比其他 的要重一些。给一架天平,至少称 ?log 3 n ? 次,就能找出那个假币。 具体的方案是将硬币每次都尽量均匀的三分。 让我们总结一下。 “三分”是整个解法的核心。我们选择三分,而不是二分或者四分是有原因 的,它的本质是由判定树的特殊结构——三叉树——所决定的。 同时还必须注意一点,我们在三分的时候有两个字很讲究:“均匀”。实际 上 h ? ?log 3 n ? 中的“=”当且仅当硬币被均匀的分配时才能达到。 这里说的“均匀”是指“在最坏情况下获得最好的效果”。因为一棵树的深 度是由它根节点儿子中深度最大的儿子决定的,为了使得整个树深度最小,我们 就要务必使得深度最大的儿子深度最小,这就是“均匀”分配的理论根据。 练习:第 12 届全国青少年信息学奥林匹克联赛初赛题 现有 80 枚硬币,其中有 一枚是假币,其重量稍重,所有真币的重量都相同,如果使 用不带砝码的天平 称重,最少需要称几次,就可以找出假币?你还要指出第 1 次的称重方法。请写 出你的结果:_________________________________________________。

答案:4 次 ;第一步,分成三组:27,27,26,将前 2 组放到天平上。

二、取石子游戏的策略及其应用
有一种很有意思的游戏, 就是有物体若干堆,可以是石子或是围棋子等等均 可。两个人轮流从堆中取物体若干,规定最后取光物体者取胜。取石子游戏是我 国民间流传已久的一种博奕,在国外亦称 Nim 游戏。别看这游戏极其简单,却蕴 含着深刻的道理。下面我们来分析一下要如何才能够取胜。 游戏Ⅰ 有若干堆任意数目的小石子{a1,a2,?,am}(m?1),两人轮流取 石子,每人每次可以从其中任意一堆中取,每次可以取 1、2、3、??或 k(1?k ?min{a1,a2,?,am})颗石子,把石子取完的人为胜者。 采用符号{a1,a2,?,am;k}来代表游戏Ⅰ中小石子的初始状况和限制条 件,一个人取一次石子实际上就是把{a1,a2,?,am;k}中某个分量 ai(1?i ?m)减小为 ai′,即{a1,a2,?,ai,?,am;k}—→{a1,a2,?,ai′,?, am;k}(0?ai′<ai),我们把这种取一次石子使数组发生的变换称为 T 变换,根 据现成博奕论先驱冯· 诺伊曼(VonNeumann)的“完全确定信息游戏必定存在一种 确定的获胜策略”的经典理论,要么对先取者存在某种取法,即某个 T 变换,无 论后取者如何取,先取者总有相应对策,直至最终取得胜利;要么无论先取者如 何取,后取者可以找到某种 T 变换,保证后取者总有相应策略获胜。为了解决游 戏{a1,a2,?,am;k}的对策,我们先看一个简单的例子。 例 1 桌上放着一堆小石子一共 100 颗,两人(甲、乙)轮流取,每次可以取 1 至 10 颗,取完的人为胜者,怎样才能取胜? 分析这个问题实际上是取石子游戏的特殊情形{100; 10},我们利用倒推法: 容易看出 11 是取胜的关键数学,因为到此时,不论对方(甲)取多少颗(大于 0 且小于 11),总留下大于 0 且小于 11 颗石子,这样乙方一次取完即获得胜利。 同样地分析,要取到 11 必须取到 22,33,44,55,66,77,88,99,这样我们 就知道了获胜之道: ①先取 1 颗石子,留下 99 颗,然后对方取 a(1?a?10)颗,己方取(11—a) 颗,就总能掌握这种致胜的关键数,从而确保获胜。②如果对方先取,己方只需 利用对方不知道其中奥秘, 争取到一个致胜数,就总能依①中方法取到下一个致 胜数,最后取得胜利。实际上,如果局中人均熟知获胜策略,那么开局的局势就 已经完全决定了结局的输赢, 1 其实是先取者必胜的局势,从这个例子的分析 例 过程我们得到启示:可以用同余理论来探讨一般情况。 一般地, 在取石子游戏{a1, ?, k 中, a2, am; ai≡ai′(modk+1)(i=1, ?, 2, m)其中 0?ai′?k,在{a1′,a2′,?,am′;k}中有取胜策略的一方在{a1, a2,?,am;k}中也有取胜策略。证明 在{a1′,a2′,?,am′;k}中有获胜 策略的一方,对于大于 k 的分量 ai(i=1,2,?,m 总能做到 ai≡ai′(modk+1), 即对方取 a(1??k),己方取 k+1-a,使两人各取一次之后该分量减小 k+1,也 就对第 i 堆各取 n(n?1)次之后石子数便由 ai=ai′+n(k+1)变成 ai′,故在 {a1′,a2′,?,am′;k}中有取胜策略的一方在{a1,a2,?,am;k}中也有 取胜策略。

游戏Ⅱ 有若干堆任意数目的小石子{a1,a2,?,am},两人轮流从中取石

子,每人每次可以取走任意一堆中任意数目的石子,不能不取,把石子取完的人 为胜者。 采用 m 元数组{a1,a2,?,am}(m?1)来描述这类取石子游戏,一人取走一 次石子相当于用某个 T 变换把其中某个分量 ai(1?i?m)减小为 ai′,即{a1, a2,?,ai,?,am}T{a1,a2,?,ai′,?,am}(0?ai′<ai)。 有趣的是为了解决这类一般情况,我们需要用到整数的二进位制,把 m 元数 组{a1,a2,?,am}中的每一个分量用二进位制数表示,ai(1?i?m)写在第 i 行,同时对齐二进位制数的位数,在列上作十进位制加法,其和写在第(m+1)行, 记为{n1,n2,?,nj,?,nl},如果所有这些和数 nj(1?j?l)均为偶数,我 们称这个 m 元数组为偶数组;若 nj(1?j?l),中有一个数为奇数,则称之为非 偶数组。 例如:对于 3 元数组{2,3,5}; a1 2 0 1 0 a2 3 0 1 1 a3 5 1 0 1 1 2 2 n1 n2 n3 因为其中 n1=1,所以{2,3,5}是非偶数组。 同样,对于 3 元数组{2,3,1}: a1 2 1 0 a2 3 1 1 a3 1 0 1 2 2 n1 n2 由于 nj(j=1,2)为偶数,则{2,3,1}为偶数组。 偶数组与非偶数组在 T 变换下具有如下性质: (1)偶数组经过一次 T 变换之后一定变为非偶数组; (2)对于非偶数组,一定可以找到某一个 T 变换,使其变为偶数组。 这样我们容易判定: 如果给定的 m 元数组是偶数组, 则后取者必有获胜策略; 相反,若给定 m 元数组为非偶数组,则先取者有方法获胜,因为给定的 m 元数组 为偶数组,先取者无论怎样取,只能将偶数组变为非偶数组,后取者则有策略将 此时的非偶数组变为偶数组,由于每次取走石子,剩下石子数目一定越来越小, 而{0,0,?,0}是偶数组,所以后取者获胜,同理可证相反情况。 例 2 有三堆石子,各堆数目分别是 2、3、6,两人轮流取,取完的人为胜者, 若甲先乙后,谁取胜? 解: a1 2 0 1 0 a2 3 0 1 1 a3 6 1 1 0 1 3 1 n1 n2 n3 ni 为奇数 i=1,2,3,所以{2,3,6}为非偶数,我们可以判定:先取者甲 获胜,依性质证明过程给出的操作方法,只需将 a3=6 变为 1,可以验证{2,3,

1}是偶数组,无论乙如只可能变成如下六种情形之一:{2,3,0},1},{2,1, 1},{2,0,1},{1,3,1},{0,3,1},都是非偶数组,同样按原方法可以将 其变 2}或{1,1},乙再取后,甲总能确保获胜。 例 3:第 12 届全国青少年信息学奥林匹克联赛初赛题现有 5 堆石子,石子数依次 为 3,5,7,19,50,甲乙两人轮流从任一堆中任取 (每次只能取自一堆,不 能不取) ,取最后一颗石子的一方获胜。 甲先取, 问甲有没有获胜策略 (即无论 乙 怎样取, 甲只要不失误, 都能获胜) ?如果有, 甲第一步应该在哪一堆里取多少? 请写出你的结果: _________________________________________________。 解:由游戏Ⅱ知,得到如下推理: 19 010011 7 000111 5 000101 3 000011 010010 (18)10 50-18=32 所以第 1 次只能在第 5 堆石子中取 32 粒,使得取出 32 粒后为偶数组。 最后我们看一道综合利用游戏Ⅰ、Ⅱ的例子: 例 4 在 3×25 的棋盘上放着三颗石 a、b、c(如图所示),两人轮流将石子向 右移人一次只可以移动其中一颗石子 1 至 5 后无格可走者为输家,若甲先行,乙 后行,赢? a b c 解 由 25≡7(mod6),根据游戏Ⅰ的策略{25,25,25;5}中有获胜策略的一 方在{7,7,7;5}中也有获胜方法,又把石子由图中所示{3,2,6}移到{7,7, 7}即相当于取石子游戏Ⅱ的{4,5,1},由于{4,5,1}是偶数组,故先移者输。

三、抽屉原理
“抽屉原理”最先是由 19 世纪的德国数学家迪里赫莱(Dirichlet)运用 于解决数学问题的,所以又称“迪里赫莱原理”,也有称“鸽巢原理”的。这个 原理可以简单地叙述为“把 10 个苹果,任意分放在 9 个抽屉里,则至少有一个 抽屉里含有两个或两个以上的苹果”。这个道理是非常明显的,但应用它却可以 解决许多有趣的问题, 并且常常得到一些令人惊异的结果。抽屉原理是国际国内 各级各类信息学竞赛中的重要内容,本讲就来学习它的有关知识及其应用。 一、知识点: 定理 1、如果把 n+1 个元素分成 n 个集合,那么不管怎么分,都存在一个集 合,其中至少有两个元素。 证明:(用反证法)若不存在至少有两个元素的集合,则每个集合至多 1 个元素, 从而 n 个集合至多有 n 个元素, 此与共有 n+1 个元素矛盾, 故命题成立。 在定理 1 的叙述中,可以把“元素”改为“物件”,把“集合”改成“抽 屉”,抽屉原理正是由此得名。 同样,可以把“元素”改成“鸽子”,把“分成 n 个集合”改成“飞进 n 个鸽笼中”。“鸽笼原理”由此得名。 二、讲解范例: 【例 1】一个小组共有 13 名同学,其中至少有 2 名同学同一个月过生日。为什 么? 【分析】每年里共有 12 个月,任何一个人的生日,一定在其中的某一个月。如 果把这 12 个月看成 12 个“抽屉”,把 13 名同学的生日看成 13 只“苹果”,把 13 只苹果放进 12 个抽屉里,一定有一个抽屉里至少放 2 个苹果,也就是说,至 少有 2 名同学在同一个月过生日。 【例 2】任意 4 个自然数,其中至少有两个数的差是 3 的倍数。这是为什么? 【分析与解】 首先我们要弄清这样一条规律: 如果两个自然数除以 3 的余数相同, 那么这两个自然数的差是 3 的倍数。 而任何一个自然数被 3 除的余数, 或者是 0, 或者是 1,或者是 2,根据这三种情况,可以把自然数分成 3 类,这 3 种类型就 是我们要制造的 3 个“抽屉”。我们把 4 个数看作“苹果”,根据抽屉原理,必 定有一个抽屉里至少有 2 个数。换句话说,4 个自然数分成 3 类,至少有两个是 同一类。既然是同一类,那么这两个数被 3 除的余数就一定相同。所以,任意 4 个自然数,至少有 2 个自然数的差是 3 的倍数。 【例 3】有规格尺寸相同的 5 种颜色的袜子各 15 只混装在箱内,试问不论如何 取,从箱中至少取出多少只就能保证有 3 双袜子(袜子无左、右之分)?

【分析与解】试想一下,从箱中取出 6 只、9 只袜子,能配成 3 双袜子吗?回答 是否定的。按 5 种颜色制作 5 个抽屉,根据抽屉原理 1,只要取出 6 只袜子就总 有一只抽屉里装 2 只,这 2 只就可配成一双。拿走这一双,尚剩 4 只,如果再补 进 2 只又成 6 只,再根据抽屉原理 1,又可配成一双拿走。如果再补进 2 只,又 可取得第 3 双。所以,至少要取 6+2+2=10 只袜子,就一定会配成 3 双。 【例 4】一个布袋中有 35 个同样大小的木球,其中白、黄、红三种颜色球各有 10 个,另外还有 3 个蓝色球、2 个绿色球,试问一次至少取出多少个球,才能保 证取出的球中至少有 4 个是同一颜色的球? 【分析与解】从最“不利”的取出情况入手。 最不利的情况是首先取出的 5 个球中,有 3 个是蓝色球、2 个绿色球。 接下来,把白、黄、红三色看作三个抽屉,由于这三种颜色球相等均超过 4 个,所以,根据抽屉原理 2,只要取出的球数多于(4-1)×3=9 个,即至少应取 出 10 个球,就可以保证取出的球至少有 4 个是同一抽屉(同一颜色)里的球。 故总共至少应取出 10+5=15 个球,才能符合要求。 思考:把题中要求改为 4 个不同色,或者是两两同色,情形又如何? 当我们遇到 “判别具有某种事物的性质有没有, 至少有几个” 这样的问题时, 想到它——抽屉原理,这是你的一条“决胜”之路。 【例 5】 .现有 64 只乒乓球, 个乒乓球盒, 18 每个盒子里最多可以放 6 只乒乓球, 至少有 个乒乓球盒子里的乒乓球数目相同? 【分析与解】:18 个乒乓球盒,每个盒子里至多可以放 6 只乒乓球。为使相同 乒乓球个数的盒子尽可能少,可以这样放:先把盒子分成 6 份,每份有 18÷6=3 (只),分别在每一份的 3 个盒子中放入 1 只、2 只、3 只、4 只、5 只、6 只乒 乓球,即 3 个盒子中放了 1 只乒乓球,3 个盒中放了 2 只乒乓球??3 个盒子中 放了 6 只乒乓球。这样,18 个盒子中共放了乒乓球 (1+2+3+4+5+6)×3=63(只)。 把以上 6 种不同的放法当做抽屉,这样剩下 64-63=1(只)乒乓球不管放入 哪一个抽屉里的任何一个盒子里(除已放满 6 只乒乓球的抽屉外),都将使该盒 子中的乒乓球数增加 1 只, 这时与比该抽屉每盒乒乓数多 1 的抽屉中的 3 个盒子 里的乒乓球数相等。 例如剩下的 1 只乒乓球放进原来有 2 只乒乓球的一个盒子里, 该盒乒乓球就成了 3 只,再加上原来装有 3 只乒乓球的 3 个盒子,这样就有 4 个盒子里装有 3 个乒乓球。所以至少有 4 个乒乓球盒里的乒乓球数目相同。

提示语 抽屉原理还可以反过来理解:假如把 n+1 个苹果放到 n 个抽屉里,放 2 个或 2 个以上苹果的抽屉一个也没有(与“必有一个抽屉放 2 个或 2 个以上的苹 果”相反),那么,每个抽屉最多只放 1 个苹果,n 个抽屉最多有 n 个苹果,与 “n+1 个苹果”的条件矛盾。 运用抽屉原理的关键是“制造抽屉”。通常,可采用把 n 个“苹果”进行 合理分类的方法来制造抽屉。 比如,若干个同学可按出生的月份不同分为 12 类, 自然数可按被 3 除所得余数分为 3 类等等。

四、容斥问题
在 19 世纪末, 德国数学家康托系统地描绘了一个能够为全部数学提供基础 的通用数学框架, 他创立的这个学科一直是我们数学发展的根植地,这个学科就 叫做集合论。它的概念与方法已经有效地渗透到所有的现代数学。可以认为,数 学的所有内容都是在“集合”中讨论、生长的。容斥问题在信息学竞赛的问题求 解中也经常出现。

一、知识点 1、集合与元素:把一类事物的全体放在一起就形成一个集合。每个集合总是由 一些成员组成的,集合的这些成员,叫做这个集合的元素。 如:集合 A={0,1,2,3,??,9},其中 0,1,2,?9 为 A 的元素。 2、并集:由所有属于集合 A 或集合 B 的元素所组成的集合,叫做 A,B 的并集, 记作 A∪B,记号“∪”读作“并”。A∪B 读作“A 并 B”,用图表示为图中阴影 部分表示集合 A,B 的并集 A∪B。

例:已知 6 的约数集合为 A={1,2,3,6},10 的约数集合为 B={1,2,5,10}, 则 A∪B={1,2,3,5,6,10} 3、交集:A、B 两个集合公共的元素,也就是那些既属于 A,又属于 B 的元素, 它们组成的集合叫做 A 和 B 的交集,记作“A∩B”,读作“A 交 B”,如图阴影 表示:

例:已知 6 的约数集合 A={1,2,3,6},10 的约数集合 B={1,2,5,10},则 A ∩B={1,2}。 4、容斥原理(包含与排除原理): (用|A|表示集合 A 中元素的个数,如 A={1,2,3},则|A|=3) 原理一:给定两个集合 A 和 B,要计算 A∪B 中元素的个数,可以分成两步进行: 第一步:先求出∣A∣+∣B∣(或者说把 A,B 的一切元素都“包含”进来,加在 一起); 第二步:减去∣A∩B∣(即“排除”加了两次的元素) 总结为公式:|A∪B|=∣A∣+∣B∣-∣A∩B∣ 原理二:给定三个集合 A,B,C。要计算 A∪B∪C 中元素的个数,可以分三步进 行: 第一步:先求∣A∣+∣B∣+∣C∣; 第二步:减去∣A∩B∣,∣B∩C∣,∣C∩A∣; 第三步:再加上∣A∩B∩C∣。

即有以下公式: ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣-∣A∩B∣-∣B∩C∣- |C∩A|+|A∩B∩C∣ 二、解题思路: 遇到集合问题,首先要弄请:集合里的元素是什么。 集合新名词新概念多。如集合、元素、有限集、无限集、列举法、描述法、 子集、真子集、空集、非空集合、全集、补集、交集、并集等。新关系新符号多, 如属于、不属于、包含、包含于、真包含、真包含于、相等、不相等、相交、相 并、互补(∈、 、 、 、N、N※、Z、Q、R、∩、∪、CsA、I、 =、≠??)

等,这些新概念新关系,多而抽象。在这千头万绪中,应该抓住“元素”这个关 键,因为集合是由元素确定的,“子、全、补、交、并、空”等集合也都是通过 元素来定义的。集合中元素的特征即“确定性”,“互异性”、“无序性”也就 是元素的性质。 集合的分类(有限集与无限集)与表示方法(列举法与描述法)也是 通过元素来刻画的。元素是集合的基本内核,研究集合,首先就要确定集合里的 元素是什么。

三、例题分析: 例 1 求不超过 20 的正整数中是 2 的倍数或 3 的倍数的数共有多少个。 分析:设 A={20 以内 2 的倍数},B={20 以内 3 的倍数},显然,要求计算 2 或 3 的倍数个数,即求∣A∪B∣。 解 1:A={2,4,6,?20},共有 10 个元素,即|A|=10 B={3,6,9,?18},共有 6 个元素,即|B|=6 A∩B={既是 2 的倍数又是 3 的倍数}={6,12,18},共有 3 个元素,即|A∩B|=3 所以∣A∪B∣=∣A∣+∣B∣-∣A∩B∣=10+6-3=13,即 A∪B 中共有 13 个元素。 解 2:本题可直观地用图示法解答

如图,其中,圆 A 中放的是不超过 20 的正整数中 2 的倍数的全体;圆 B 中放的是不 超过 20 的正整数中 3 的倍数的全体,其中阴影部分的数 6,12,18 是既是 2 的倍数 又是 3 的倍数的数(即 A∩B 中的数)只要数一数集合 A∪B 中的数的个数即可。

例 2 某班统计考试成绩, 数学得 90 分上的有 25 人;语文得 90 分以上的有 21 人;两科中至少有一科在 90 分以上的有 38 人。问两科都在 90 分以上的有多少 人? 解:设 A={数学成绩 90 分以上的学生} B={语文成绩 90 分以上的学生} 那么,集合 A∪B 表示两科中至少有一科在 90 分以上的学生,由题意知, ∣A∣=25,∣B∣=21,∣A∪B∣=38 现要求两科均在 90 分以上的学生人数,即求∣A∩B∣,由容斥原理得 ∣A∩B∣=∣A∣+∣B∣-∣A∪B∣=25+21-38=8 点评:解决本题首先要根据题意,设出集合 A,B,并且会表示 A∪B,A∩B,再 利用容斥原理求解。 例 3 某班同学中有 39 人打篮球,37 人跑步,25 人既打篮球又跑步,问全班 参加篮球、跑步这两项体育活动的总人数是多少? 解:设 A={打篮球的同学};B={跑步的同学} 则 A∩B={既打篮球又跑步的同学} A∪B={参加打篮球或跑步的同学} 应用容斥原理∣A∪B∣=∣A∣+∣B∣-∣A∩B∣=39+37-25=51(人) 例 4 某年级的课外学科小组分为数学、语文、外语三个小组,参加数学小组 的有 23 人,参加语文小组的有 27 人,参加外语小组的有 18 人;同时参加数学、 语文两个小组的有 4 人,同时参加数学、外语小组的有 7 人,同时参加语文、外 语小组的有 5 人;三个小组都参加的有 2 人。问:这个年级参加课外学科小组共 有多少人? 解 1:设 A={数学小组的同学},B={语文小组的同学},C={外语小组的同学}, A∩B={数学、语文小组的同学},A∩C={参加数学、外语小组的同学},B∩C={参 加语文、外语小组的同学},A∩B∩C={三个小组都参加的同学} 由题意知:∣A∣=23,∣B∣=27,∣C∣=18 ∣A∩B∣=4,∣A∩C∣=7,∣B∩C∣=5,∣A∩B∩C∣=2 根据容斥原理二得: ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣-∣A∩B∣-∣A∩C|-∣B∩C|+|A∩B∩C∣ =23+27+18-(4+5+7)+2 =54(人) 解 2: 利用图示法逐个填写各区域所表示的集合的元素的个数,然后求出最 后结果。

设 A、B、C 分别表示参加数学、语文、外语小组的同学的集合,其图分割成七 个互不相交的区域,区域Ⅶ(即 A∩B∩C)表示三个小组都参加的同学的集合,

由题意,应填 2。区域Ⅳ表示仅参加数学与语文小组的同学的集合,其人数为 4-2=2(人)。区域Ⅵ表示仅参加数学与外语小组的同学的集合,其人数为 7-2=5 (人) 区域Ⅴ表示仅参加语文、 。 外语小组的同学的集合, 其人数为 5-2=3 (人) 。 区域Ⅰ表示只参加数学小组的同学的集合,其人数为 23-2-2-5=14(人)。同理 可把区域Ⅱ、Ⅲ所表示的集合的人数逐个算出,分别填入相应的区域内,则参加 课外小组的人数为; 14+20+8+2+5+3+2=54(人) 点评:解法 2 简单直观,不易出错。由于各个区域所表示的集合的元素个数都计 算出来了,因此提供了较多的信息,易于回答各种方式的提问。 例 5 学校教导处对 100 名同学进行调查,结果有 58 人喜欢看球赛,有 38 人 喜欢看戏剧, 52 人喜欢看电影。 有 另外还知道, 既喜欢看球赛又喜欢看戏剧 (但 不喜欢看电影)的有 6 人,既喜欢看电影又喜欢看戏剧(但不喜欢看球赛)的有 4 人,三种都喜欢的有 12 人。问有多少同学只喜欢看电影?有多少同学既喜欢 看球赛又喜欢看电影(但不喜欢看戏剧)?(假定每人至少喜欢一项) 解法 1:画三个圆圈使它们两两相交,彼此分成 7 部分(如图)这三个圆圈分 别表示三种不同爱好的同学的集合,由于三种都喜欢的有 12 人,把 12 填在三个 圆圈的公共部分内(图中阴影部分),其它 6 部分填上题目中所给出的不同爱好 的同学的人数(注意,有的部分的人数要经过简单的计算)其中设既喜欢看电影 又喜欢看球赛的人数为χ ,这样,全班同学人数就是这 7 部分人数的和,即 16+4+6+(40-χ )+(36-χ )+12=100 解得 χ =14 只喜欢看电影的人数为 36-14=22

解法 2: A={喜欢看球赛的人}, 设 B={喜欢看戏剧的人}, C={喜欢看电影的人}, 依题目的条件有|A∪B∪C|=100,|A∩B|=6+12=18 (这里加 12 是因为三种都喜欢 的人当然喜欢其中的两种),|B∩C|=4+12=16,|A∩B∩C|=12,再设|A∩C|=12+ χ 由容斥原理二:|A∪B∪C |=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C| 得:100=58+38+52-(18+16+х +12)+12 解得:х =14 ∴36-14=22 所以既喜欢看电影又喜欢看球赛的人数为 14,只喜欢看电影的人数为 22。

五、排列组合问题
一、知识点: 1 分类计数原理:做一件事情,完成它可以有 n 类办法,在第一类办法中有 m1 种 不同的方法,在第二类办法中有 m2 种不同的方法,??,在第 n 类办法中有 mn
王新敞
奎屯 新疆

种不同的方法 那么完成这件事共有 N ? m1 ? m2 ? ? ? mn 种不同的方法
王新敞
奎屯 新疆

王新敞
奎屯

新疆

2.分步计数原理:做一件事情,完成它需要分成 n 个步骤,做第一步有 m1 种不 同的方法,做第二步有 m2 种不同的方法,??,做第 n 步有 mn 种不同的方法, 那么完成这件事有 N ? m1 ? m2 ??? mn 种不同的方法 3.排列的概念:从 n 个不同元素中,任取 m ( m ? n )个元素(这里的被取元素 各不相同)按照一定的顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一 个排列 4.排列数的定义:从 n 个不同元素中,任取 m ( m ? n )个元素的所有排列的个 Am 数叫做从 n 个元素中取出 m 元素的排列数,用符号 n 表示 Am ? n(n ? 1)(n ? 2)? (n ? m ? 1) m, n ? N ? , m ? n 5.排列数公式: n ( )
王新敞
奎屯 新疆

王新敞
奎屯

新疆

王新敞
奎屯

新疆

6 阶乘: n ! 表示正整数 1 到 n 的连乘积,叫做 n 的阶乘 规定 0! ? 1. n! m A 7.排列数的另一个计算公式: n = (n ? m)!
王新敞
奎屯 新疆

王新敞
奎屯

新疆

王新敞
奎屯

新疆

王新敞
奎屯

新疆

? m ? n ? 个元素并成一组,叫做 8 组合的概念:一般地,从 n 个不同元素中取出 m 从 n 个不同元素中取出 m 个元素的一个组合 ? m ? n ? 个元素的所有组合的个数, 9.组合数的概念:从 n 个不同元素中取出 m Cm 叫做从 n 个不同元素中取出 m 个元素的组合数.用符号 n 表示.
王新敞
奎屯 新疆

王新敞
奎屯

新疆

10.组合数公式: n! C m? n m!(n ? m)! (n, m ? N ? , 且m ? n) 或 11 组合数的性质 1:
王新敞
奎屯 新疆

Cnm ?

Anm n(n ? 1)(n ? 2)? (n ? m ? 1) ? m Am m!

王新敞
奎屯

新疆

王新敞
奎屯

新疆

.规定: m C m C m ?1 C 2: n ?1 = n + n

C ?C
m n

n?m n

0 Cn ? 1



王新敞
奎屯

新疆

12.圆排列 (1) A ? {a1 , a2 , a3 ,?, an } 的 n 个元素中,每次取出 r 个元素排在一个圆环 由 上,叫做一个圆排列(或叫环状排列). (2)圆排列有三个特点:(i)无头无尾;(ii)按照同一方向转换后仍是 同一排列;(iii)两个圆排列只有在元素不同或者元素虽然相同,但元素之间

的顺序不同,才是不同的圆排列. (3)定理:在 A ? {a1 , a2 , a3 ,?, an } 的 n 个元素中,每次取出 r 个不同的元素 进行圆排列,圆排列数为
Pnr . r

13.可重排列 允许元素重复出现的排列,叫做有重复的排列. 在 m 个不同的元素中,每次取出 n 个元素,元素可以重复出现,按照一定的 顺序那么第一、第二、?、第 n 位是的选取元素的方法都是 m 种,所以从 m 个不 同的元素中,每次取出 n 个元素的可重复的排列数为 m n . 14.不尽相异元素的全排列 如果 n 个元素中,有 p1 个元素相同,又有 p 2 个元素相同,?,又有 p s 个元 素相同( p1 ? p 2 ? ? ? p s ? n ),这 n 个元素全部取的排列叫做不尽相异的 n 个 n! 元素的全排列,它的排列数是 p1!? p 2 !?? ? p s ! 15.可重组合 (1)从 n 个元素,每次取出 p 个元素,允许所取的元素重复出现 1,2,?, p 次的 组合叫从 n 个元素取出 p 个有重复的组合.
r (2)定理:从 n 个元素每次取出 p 个元素有重复的组合数为: H np ? C n ? ( p ?1)

二、解题思路: 排列组合题的求解策略 (1)排除:对有限条件的问题,先从总体考虑,再把不符合条件的所有情况排 除,这是解决排列组合题的常用策略. (2)分类与分步 有些问题的处理可分成若干类,用加法原理,要注意每两类的交集为空集, 所有各类的并集是全集; 有些问题的处理分成几个步骤,把各个步骤的方法数相 乘,即得总的方法数,这是乘法原理. (3)对称思想:两类情形出现的机会均等,可用总数取半得每种情形的方法数. (4)插空:某些元素不能相邻或某些元素在特殊位置时可采用插空法.即先安 排好没有限制条件的元素, 然后将有限制条件的元素按要求插入到排好的元素之 间. (5)捆绑:把相邻的若干特殊元素“捆绑”为一个“大元素”,然后与其它“普 通元素”全排列,然后再“松绑”,将这些特殊元素在这些位置上全排列. (6)隔板模型:对于将不可辨的球装入可辨的盒子中,求装的方法数,常用隔 板模型. 如将 12 个完全相同的球排成一列,在它们之间形成的 11 个缝隙中任意 3 插入 3 块隔板,把球分成 4 堆,分别装入 4 个不同的盒子中的方法数应为 C11 , 这也就是方程 a ? b ? c ? d ? 12 的正整数解的个数.

解排列组合问题,首先要弄清一件事是“分类”还是“分步”完成,对于元 素之间的关系,还要考虑“是有序”的还是“无序的”,也就是会正确使用分类 计数原理和分步计数原理、排列定义和组合定义,其次,对一些复杂的带有附加 条件的问题,需掌握以下几种常用的解题方法:

三、讲解范例: 一、相临问题——整体捆绑法 例 1.7 名学生站成一排,甲、乙必须站在一起有多少不同排法? 解:两个元素排在一起的问题可用“捆绑”法解决,先将甲乙二人看作一个元 素与其他五人进行排列,并考虑甲乙二人的顺序,所以共有 种。 捆绑法:要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需 要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素 内部也可以作排列.一般地: 个人站成一排,其中某 个人相邻,可用“捆绑” 法解决,共有 种排法。 练习:5 个男生 3 个女生排成一排,3 个女生要排在一起,有多少种不同的排法? 分析 此题涉及到的是排队问题,对于女生有特殊的限制,因此,女生是特殊元素, 并且要求她们要相邻,因此可以将她们看成是一个元素来解决问题. 解 因为女生要排在一起,所以可以将 3 个女生看成是一个人,与 5 个男生作全 P6 P3 排列,有 6 种排法,其中女生内部也有 3 种排法,根据乘法原理,共有 P66 P33 种不同的排法. 二、不相临问题——选空插入法 例 2. 7 名学生站成一排,甲乙互不相邻有多少不同排法? 解:甲、乙二人不相邻的排法一般应用“插空”法,所以甲、乙二人不相邻的 排法总数应为: 种 . 插入法:对于某两个元素或者几个元素要求不相邻的问题,可以用插入法.即先 排好没有限制条件的元素,然后将有限制条件的元素按要求插入排好元素的空档 之中即可.若 个人站成一排,其中 个人不相邻,可用“插空”法解决,共有 种排法。 练习: 学校组织老师学生一起看电影,同一排电影票 12 张。8 个学生,4 个老 师,要求老师在学生中间,且老师互不相邻,共有多少种不同的坐法? 分析 此题涉及到的是不相邻问题,并且是对老师有特殊的要求,因此老师是特殊 元素,在解决时就要特殊对待.所涉及问题是排列问题. 8 解 先排学生共有 P8 种排法,然后把老师插入学生之间的空档,共有 7 个空档可
P4 插,选其中的 4 个空档,共有 7 种选法.根据乘法原理,共有的不同坐法为 P88 P74 种. 三、复杂问题——总体排除法或排异法 有些问题直接法考虑比较难比较复杂,或分类不清或多种时,而它的反面往往比 较简捷,可考虑用“排除法”,先求出它的反面,再从整体中排除.解决几何问题 必须注意几何图形本身对其构成元素的限制。

例 3.正六边形的中心和顶点共 7 个点,以其中 3 个点为顶点的三角形共有 个. 解:从 7 个点中取 3 个点的取法有 种,但其中正六边形的对角线所含的中

心和顶点三点共线不能组成三角形, 3 条, 有 所以满足条件的三角形共有 - 3=32 个. 练习: 我们班里有 43 位同学,从中任抽 5 人,正、副班长、团支部书记至少有一 人在内的抽法有多少种? 分析 此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容 易造成各种情况遗漏或者重复的情况.而如果从此问题相反的方面去考虑的话, 不但容易理解,而且在计算中也是非常的简便.这样就可以简化计算过程. 5 解 43 人中任抽 5 人的方法有 C43 种,正副班长,团支部书记都不在内的抽法有
5 5 C43 ? C40 种,所以正副班长,团支部书记至少有 1 人在内的抽法有 种. 四、特殊元素——优先考虑法 对于含有限定条件的排列组合应用题,可以考虑优先安排特殊位置,然后 再考虑其他位置的安排。 例 4. 1 名老师和 4 名获奖学生排成一排照像留念,若老师不排在两端,则 共有不同的排法 种. 解:先考虑特殊元素(老师)的排法,因老师不排在两端,故可在中间三个位 5 C40

置上任选一个位置,有 种,而其余学生的排法有 种,所以共有 = 72 种不同的排法. 例 5.乒乓球队的 10 名队员中有 3 名主力队员,派 5 名队员参加比赛,3 名主 力队员要安排在第一、三、五位置,其余 7 名队员选 2 名安排在第二、四位置, 那么不同的出场安排共有 种. 解:由于第一、三、五位置特殊,只能安排主力队员,有 名队员选出 2 名安排在第二、四位置,有 种排法,而其余 7

种排法,所以不同的出场安排共

有 =252 种. 五、多元问题——分类讨论法 对于元素多,选取情况多,可按要求进行分类讨论,最后总计。 例 6.某班新年联欢会原定的 5 个节目已排成节目单,开演前又增加了两个新 节目.如果将这两个节目插入原节目单中,那么不同插法的种数为(A ) A.42 B.30 C.20 D.12 解:增加的两个新节目,可分为相临与不相临两种情况:1.不相临:共有 A62 种;2.相临:共有 A22A61 种。故不同插法的种数为:A62 +A22A61=42 ,故选 A。 六、混合问题——先选后排法 对于排列组合的混合应用题,可采取先选取元素,后进行排列的策略. 例 7. 12 名同学分别到三个不同的路口进行车流量的调查,若每个路口 4 人,则不同的分配方案共有( ) A. 种 B. 种 C. 种 D. 种

解:本试题属于均分组问题。 则 12 名同学均分成 3 组共有

种方法,分

配到三个不同的路口的不同的分配方案共有: 种,故选 A。 例 8.从黄瓜、白菜、油菜、扁豆 4 种蔬菜品种中选出 3 种,分别种在不同土 质的三块土地上,其中黄瓜必须种植,不同的种植方法共有( ) A.24 种 B.18 种 C.12 种 D.6 种 2 解:先选后排,分步实施. 由题意,不同的选法有: C3 种,不同的排法有: 1 A3 ·A22,故不同的种植方法共有 A31·C32·A22=12,故应选 C. 七.相同元素分配——档板分隔法 例 9.把 10 本相同的书发给编号为 1、2、3 的三个学生阅览室,每个阅览室分 得的书的本数不小于其编号数,试求不同分法的种数。请用尽可能多的方法求 解,并思考这些方法是否适合更一般的情况?本题考查组合问题。 解:先让 2、3 号阅览室依次分得 1 本书、2 本书;再对余下的 7 本书进行分配, 保证每个阅览室至少得一本书,这相当于在 7 本相同书之间的 6 个“空档”内 插入两个相同“I”(一般可视为“隔板”)共有 种插法,即有 15 种分法。 八.转化法: 对于某些较复杂的、或较抽象的排列组合问题,可以利用转化思想,将其化归为 简单的、具体的问题来求解. 例 10 高二年级 8 个班,组织一个 12 个人的年级学生分会,每班要求至少 1 人,名 额分配方案有多少种? 分析 此题若直接去考虑的话,就会比较复杂.但如果我们将其转换为等价的其他 问题,就会显得比较清楚,方法简单,结果容易理解. 解: 此题可以转化为:将 12 个相同的白球分成 8 份,有多少种不同的分法问题, 因此须把这 12 个白球排成一排,在 11 个空档中放上 7 个相同的黑球,每个空档最 7 多放一个,即可将白球分成 8 份,显然有 C11 种不同的放法,所以名额分配方案
7 有 C11 种. 总之,排列、组合应用题的解题思路可总结为:排组分清,加乘明确;有序 排列,无序组合;分类为加,分步为乘。 具体说,解排列组合的应用题,通常有以下途径: (1)以元素为主体,即先满足特殊元素的要求,再考虑其他元素。 (2)以位置为主体,即先满足特殊位置的要求,再考虑其他位置。 (3)先不考虑附加条件,计算出排列或组合数,再减去不合要求的排列组合数。

六、逻辑推理问题
通常把只涉及一些相互关联 (或依存) 条件或关系, 极少给出 (不直接赋与) 数量关系与几何图形的一类非标准(常规)数学问题叫逻辑推理问题,处理这类 问题,要从一些关联的条件出发,应用某些数学知识,甚至日常生活常识,依据 一定的思维规律(机智灵活、准确敏捷的思考),通过分析、推理、排除不可能 情况(剔除不合理成分),然后作出正确的判断。 逻辑推理问题中常用到以下三条逻辑基本规律: (1)同一律:是指同一东西(对象)。它是什么就是什么,不能模棱两可, 亦此亦彼; (2)矛盾律:是指互相对立(矛盾)的事不能都真,二者必有一假(即同 一思想不能既真又假); (3)排中律:是指两个不相容的判断不能都假,二者必有一真(即任何判 断或同一思想不能既不真也不假)。 逻辑推理问题条件扑朔迷离,层次重叠纷纭,没有一定的定理可以依据,无 现成公式可用,无模式可循,靠的是逻辑推理。可画框图、紧抓关系、细抠条件, 寻找突破口,穷追到底,层层进逼,以求找到答案。 本文结合一些赛题,谈谈处理逻辑推理问题的一些主要方法。 一、利用逻辑原理,直接推理 对于一些简单的逻辑推理问题,往往只需以似真推理为主,直接通过分析就 可以得出正确的结果。用这种方法解决“真假话”问题尤为有效。 住在某个旅馆的同一房间的四个人 A、B、C、D 正在听一组流行音乐,她们 当中有一个人在修指甲,一个人在写信,一个人躺在床上,另一个人在看书。 1.A 不在修指甲,也不在看书; 2.B 不躺在床上,也不在修指甲; 3.如果 A 不躺在床上,那么 D 不在修指甲; 4.C 既不在看书,也不在修指甲; 5.D 不在看书,也不躺在床上。 她们各自在做什么呢? 由 1、2、4、5 知,既不是 A、B 在修指甲,也不是 C 在修指甲,因此修指甲 的应该是 D;但这与 3 的结论相矛盾,所以 3 的前提肯定不成立,即 A 应该是躺 在床上;在 4 中 C 既不看书又不修指甲,由前面分析,C 又不可能躺在床上,所 以 C 是在写信;而 B 则是在看书。 二、利用表格辅助推理 某些逻辑推理问题中,有时会涉及很多对象,每个对象又有几种不同情况,同 时还给出不同对象之间不同情况的判断,要求推出确定的结论。对于这类问题, 通常可以利用表格把本来凌乱的信息集中整理出来,方便推理。 甲、乙、丙、丁、戊五名同学参加推铅球比赛,通过抽签决定出赛顺序,在

未公布顺序之前每人都对出赛顺序进行了猜测。甲猜:乙第三,丙第五;乙猜: 戊第四,丁第五;丙猜:甲第一,戊第四;丁猜:丙第一,乙第二;戊猜:甲第 三,丁第四。老师说每人的出赛顺序都至少被一人所猜中。第一、第三、第五分 别是哪位同学?

解:本题相互关系过于复杂,不便分析和推断,不妨由已知条件列表如下: 由于每人的出赛顺序至少被一人所猜中,所以戊第四,丁第五,丙第一,甲 第三,乙第二;出赛的顺序:丙乙甲戊丁 例 5. 某校举办作文比赛,A、B、C、D 四位同学参加比赛,其中只有一位同 学获奖。老师为了解比赛情况,分别向选手询问,回答如下: A:我获了奖; B:我没有获奖,C 也没有获奖 C:是 A 获奖或 B 获奖 D:是 B 获奖 事后证实,有两人的话符合事实,哪位同学获了奖?

解:“某人获奖”就将此人记为“1”,否则为“0”。根据四个人的话可得 下表。 由表可知,若是 A 获奖,则有 3 人说的话符合事实,只有 B 获奖时,有两人 的话符合事实。 三、利用计算辅助推理 某些逻辑推理问题常常有几个未知量同时存在,或答案有多种可能性,解题 时需要充分利用已知条件进行计算,并通过对计算结果的分析,推理得出正确的 结论。 例5 学校进行了一次考试,考试的科目是语文、历史、数学、物理和英 语,每科满分为 5 分,其余等级依次是 4、3、2、1 分。今已知按总分由多到少 排列着五名学生,A、B、C、D、E 满足下列条件: (1)在同一科目中以及在总分数中没有得同样分数的人; (2)A 的总分是 24 分; (3)C 有四门得了相同的分数;

(4)E 语文得 3 分,物理得 5 分; (5)D 的历史得 4 分。 试求题目中未直接给出的各人其它各科的成绩? 讲解:先从五人的总分入手,再扣掉 A 的得分,得出 B、C、D、E 四人的总分, 再从得分最低的 E 出发进行推断,即可逐步得出结果。 (1)由已知可得 5 人的总分为 5×(1+2+3+4+5)=75 分。 因 A 得 24 分,故 B、C、D、E 共得 75-24=51 分 又 E 两科得 8 分,故 E(还有三科)至少得 11 分 稍加验算可知:B、C、D、E 的得分情况应该是 15、13、12、11。 (2)E 两科 8 分,总分 11 分,因而 E 的英语、历史、数学各得 1 分。 (3)A 的总分是 24 分,故只有一科得 4 分,其它各科均是 5 分,因 E 的物 理得 4 分,故语文、历史、数学、英语各五分。 (4)C 的总分为 13 分,且有四科得分相同,故得分情况只能是一科五分, 四科各 2 分或一科 1 分,四科各 3 分。因 5 分为 A、E 所得,则 C 的四科各得 3 分,一科得 1 分,又因 E 语文得 3 分,故 C 语文得 1 分,其余各科得 3 分。 (5)D 的总分是 12 分,历史得 4 分,余下 8 分,因全部 5 分为 A、E 所得, 全部 3 分为 C、E 所得,四个 1 分为 C、E 所得,故除历史外,D 的其它各科各得 2 分。 显然,B 的语文、数学、英语皆得 4 分,历史 2 分,物理 1 分。 【例 9】赵、钱、孙、李四人,一个是教师,一个是售货员,一个是工人, 一个是机关干部。试根据以下条件,判断这四人的职业。 (1)赵和钱是邻居,每天一起骑车上班; (2)钱比孙年龄大; (3)赵在教李打太极拳; (4)教师每天步行去上班; (5)售货员的邻居不是机关干部; (6)机关干部和工人互不相识; (7)机关干部比售货员和工人年龄都大。

【分析】由条件(4)和条件(1)可知赵、钱都不是教师。由条件(2)和 条件(7),可推知孙不是干部。如果是的话,钱不是工人或售货员,钱又不是 教师。于是,钱也是干部,矛盾。这样我们得到下表。下面几步推理也用表格说 明。 四、利用图形辅助推理

美国数学家斯蒂恩说过: “如果一个特定的问题可以被转化成一个图形,那么, 思想就整体地把握了问题,并且能创造性地思索问题解法。” A、 C、 E 五支球队进行单循环比赛 B、 D、 (每两支球队间都要进行一场比赛) , 当比赛进行到一定阶段时,统计 A、B、C、D 四个球队已经赛过的场数,依次为 A 队 4 场,B 队 3 场,C 队 2 场,D 队 1 场,这时,E 队已赛过的场数是() A. 1 B. 2 C. 3 D. 4

解:用五个点分别表示 A、B、C、D、E 五支球队,将它们之间比赛的情况用 图 1 表示出来。 A 队已经赛过 4 场,由于是“单循环比赛”,这说明 A 与 B、C、D、E 四支 球队各赛了 1 场;D 队赛过 1 场,是与 A 队赛过的;B 队 3 场,不可能与 D 队比 赛,是与 A、C、E 各赛 1 场;C 队 2 场,是与 A、B 赛的,从图中可以看出,E 队已经赛了 2 场。

七、递推关系的建立及在信息学竞赛中的应用
瞬息变幻的世界, 每一件事物都在随时间的流逝发生着微妙的变化。而 在这纷繁的变幻中, 许多现象的变化是有规律的,这种规律往往呈现出前因和后 果的关系。 即是说, 某种现象的变化结果与紧靠它前面变化的一个或一些结果紧 密关联。所谓“三岁看老” ,说的就是这个道理。这一道理也正体现了递推的思 想。递推关系几乎在所有的数学分支中都有重要作用,在一切向“更快、更高、 更强”看齐的当今信息学奥林匹克竞赛中更因简洁高效而显示出其独具的魅力。 在递推关系发挥重要作用的今天,深入研究其性质、特点便成为一件十分必要的 事情。本文就将围绕着递推关系的三大基本问题中的如何建立递推关系展开论 述,并通过例题说明递推关系在当今信息学竞赛中的应用。

一、 递推关系的定义 相信每个人对递推关系都不陌生, 但若要说究竟满足什么样的条件就是 递推关系,可能每个人又会有不同的说法。为了更好地研究递推关系,首先让我 们明确什么是递推关系。 【定义 1】给定一个数的序列 H0,H1,?,Hn,?若存在整数 n0,使当 n ? n0 时, 可以用等号(或大于号、小于号)将 Hn 与其前面的某些项 Hn(0 ? i<n)联系起来, 这样的式子就叫做递推关系。

二、 递推关系的建立 递推关系中存在着三大基本问题: 如何建立递推关系, 已给的递推关系 有何性质, 以及如何求解递推关系。 建立递推关系的关键在于寻找第 n 项与前面 几项的关系式,以及初始项的值。它不是一种抽象的概念,是需要针对某一具体 题目或一类题目而言的。 在下文中,我们将对五种典型的递推关系的建立作比较 深入具体的讨论。

1.四种典型的递推关系

Ⅰ.Fibonacci 数列
在所有的递推关系中,Fibonacci 数列应该是最为大家所熟悉的。在最基 础的程序设计语言 Logo 语言中, 就有很多这类的题目。 而在较为复杂的 Basic、 Pascal、C 语言中,Fibonacci 数列类的题目因为解法相对容易一些,逐渐退 出了竞赛的舞台。可是这不等于说 Fibonacci 数列没有研究价值,恰恰相反,

一些此类的题目还是能给我们一定的启发的。 Fibonacci 数列的代表问题是由意大利著名数学家 Fibonacci 于 1202 年 提出的“兔子繁殖问题”(又称“Fibonacci 问题”)。 问题的提出: 有雌雄一对兔子,假定过两个月便可繁殖雌雄各一的一对小 兔子。问过 n 个月后共有多少对兔子? 解:设满 x 个月共有兔子 Fx 对,其中当月新生的兔子数目为 Nx 对。第 x-1 个月 留下的兔子数目设为 Ox 对。则: Fx=Nx+Ox 而 Ox=Fx-1, Nx=Ox-1=Fx-2 (即第 x-2 个月的所有兔子到第 x 个月都有繁殖能力了) ∴ Fx=Fx-1+Fx-2 边界条件: F0=0,F1=1 由上面的递推关系可依次得到 F2=F1+F0=1,F3=F2+F1=2,F4=F3+F2=3,F5=F4+F3=5,??。

Ⅱ.Hanoi 塔问题
问题的提出:Hanoi 塔由 n 个大小不同的圆盘和三根木柱 a,b,c 组成。开 始时,这 n 个圆盘由大到小依次套在 a 柱上,如图 1 所示。

a

b

c

图1

要求把 a 柱上 n 个圆盘按下述规则移到 c 柱上: (1)一次只能移一个圆盘; (2)圆盘只能在三个柱上存放; (3)在移动过程中,不允许大盘压小盘。 问将这 n 个盘子从 a 柱移动到 c 柱上,总计需要移动多少个盘次? 解:设 hn 为 n 个盘子从 a 柱移到 c 柱所需移动的盘次。显然,当 n=1 时, 只需把 a 柱上的盘子直接移动到 c 柱就可以了,故 h1=1。当 n=2 时,先将 a

柱上面的小盘子移动到 b 柱上去;然后将大盘子从 a 柱移到 c 柱;最后,将 b 柱上的小盘子移到 c 柱上,共记 3 个盘次,故 h2=3。以此类推,当 a 柱上 有 n(n ? 2)个盘子时,总是先借助 c 柱把上面的 n-1 个盘子移动到 b 柱上, 然后把 a 柱最下面的盘子移动到 c 柱上;再借助 a 柱把 b 柱上的 n-1 个盘子 移动到 c 柱上;总共移动 hn-1+1+hn-1 个盘次。 ∴hn=2hn-1+1 边界条件:hn-1=1

Ⅲ.平面分割问题
问题的提出:设有 n 条封闭曲线画在平面上,而任何两条封闭曲线恰好相 交于两点,且任何三条封闭曲线不相交于同一点,问这些封闭曲线把平面分割 成的区域个数。

1 1 2

4 3 5 3

1 4 7 2

8 6 10 11

14 6 12 3 2 1 8 4 5 9 7 13

n=1

n=2
图2

n=3

n=4

解: an 为 n 条封闭曲线把平面分割成的区域个数。 由图 2 可以看出: 2-a1=2; 设 a a3-a2=4;a4-a3=6。从这些式子中可以看出 an-an-1=2(n-1)。当然,上面的式子只 是我们通过观察 4 幅图后得出的结论,它的正确性尚不能保证。下面不妨让我 们来试着证明一下。当平面上已有 n-1 条曲线将平面分割成 an-1 个区域后,第 n-1 条曲线每与曲线相交一次,就会增加一个区域,因为平面上已有了 n-1 条 封闭曲线,且第 n 条曲线与已有的每一条闭曲线恰好相交于两点,且不会与任 两条曲线交于同一点,故平面上一共增加 2(n-1)个区域,加上已有的 an-1 个区 域,一共有 an-1+2(n-1)个区域。所以本题的递推关系是 an=an-1+2(n-1),边界条 件是 a1=1。 平面分割问题是竞赛中经常触及到的一类问题,由于其灵活多变,常常 让选手感到棘手,

Ⅳ.Catalan 数

Catalan 数首先是由 Euler 在精确计算对凸 n 边形的不同的对角三角形剖 分的个数问题时得到的,它经常出现在组合计数问题中。 问题的提出:在一个凸 n 边形中,通过不相交于 n 边形内部的对角线,把 n 边形拆分成若干三角形,不同的拆分数目用 hn 表之,hn 即为 Catalan 数。例 如五边形有如下五种拆分方案(图 6-4),故 h5=5。求对于一个任意的凸 n 边形 相应的 hn。

图3

解:设 Cn 表示凸 n 边形的拆分方案总数。由题目中的要求可知一个凸 n 边形的 任意一条边都必然是一个三角形的一条边,边 P1 Pn 也不例外,再根据“不在 同一直线上的三点可以确定一个三角形”,只要在 P2,P3,??,Pn-1 点中找一 个点 Pk(1<k<n),与 P1、Pn 共同构成一个三角形的三个顶点,就将 n 边形分成 了三个不相交的部分(如图 3 所示), 我们分别称之为区域①、 区域②、 区域③, 其中区域③必定是一个三角形,区域①是一个凸 k 边 形,区域②是一个凸 n-k+1 边形,区域①的拆分方案 P2 P3 总数是 Ck, 区域②的拆分方案数为 Cn-k+1, 故包含△P1PkPn ① 的 n 边形的拆分方案数为 CkCn-k+1 种,而 Pk 可以是 P2, Pk P1 P3,??,Pn-1 种任一点,根据加法原理,凸 n 边形的 ③
Pn ② Pn--1

三角拆分方案总数为 ? C i C n ?i ?1 ,同时考虑到计算的方
i ?2

n ?1

图4

便,约定边界条件 C2=1。

小结:通过上面对四种典型的递推关系建立过程的探讨,可知对待递推 类的题目,要具体情况具体分析,通过找到某状态与其前面状态的联系,建立相 应的递推关系。 例题精讲 例 1、在一个正六边形的六个区域中的每一个 区域染上红、黄、蓝、紫四种颜色之一,要求相邻的 两个区域染色不相同,则有多少种不同的染色方法?

F E
【分析】本问题属于排列组合方面的问题。

A D

B C

思路一:利用排列组合的知识进行求解,由于图形的特殊性,可以按 A、C、E 染色情况进行分类。 思路二:将该图形抽象出来,形成一般的问题: “将圆分为 n(n ? 2) 个扇形, 每个扇形区域染上红、黄、蓝、紫四种颜色之一,要求相邻的扇形区域染色不相 同,问有多少种染色方法?”先求通项 a n 或递推关系,再求 a 6 。 【解答】解法一:按 A、C、E 染色情况进行分类: (1)若 A、C、E 染一种色,则此时共有 4 ? 3 ? 3 ? 3 ? 108 种方法; (2)若 A、C、E 染三种色,则此时共有 P43 ? 2 ? 2 ? 2 ? 192 种方法;
2 (3)若 E、C、A 染二种色,则此时共有 P42 ? C3 ? 3 ? 2 ? 2 ? 432 种。

故总计共有 108+192+432=732 种方法。 解法二:将问题抽象成一般问题:“将圆分为 n(n ? 2) 个扇形,每个扇形区 域染上红、黄、蓝、紫四种颜色之一,要求相邻的扇形区域染色不相同,记 染色方法总数为 a n ,求 a 6 ”。
?a ? a n ?1 ? 4 ? 3n ?1 ( n ? 3) 由已知条件容易建立递推关系 ? n 。 ? a 2 ? 12

由该递推关系易求出 a3 ? 24, a4 ? 84, a5 ? 240, a6 ? 732 。 【评注】(1)解法一中若不按 A、C、E 染色情况进行分类可能比较复杂, 并且当 E、C、A 染二种色时,计算染法数比较容易出错; (2)解法二中关键之处在于建立递推式子,但递推式子建立后计算比 较方便。 例 2 有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房,不能反向爬行。试求出蜜 蜂从蜂房 a 爬到蜂房 b 的可能路线数。

??

3 4

5 6

7 8

9 10

11 12

13 14

??

图6

解: 这是一道很典型的 Fibonacci 数列类题目, 其中的递推关系很明显。 “蜜 由于 蜂只能爬向右侧相邻的蜂房,不能反向爬行”的限制,决定了蜜蜂到 b 点的路径 只能是从 b-1 点或 b-2 点到达的,故 fn=fn-1+fn-2 (a+2 ? n ? b),边界条件 fa=1, fa+1=1。 附程序:

program Pro_1;{蜂巢问题,最大范围:目标点与出发点之差不超过 40000} type Tarr=array[1..10000] of byte; Tnum=array[1..4] of ^Tarr; Tlen=array[1..4] of word; var start,finish:longint; {出发点和目标点} num:Tnum; {num[1]?num[3]分别保存到达相邻三个蜂巢的路径数;num[4]是用于交换 的临时变量} len:Tlen; {len[i]表示 num[i]的长度} procedure DataInit;{数据初始化} var i:integer; begin for i:=1 to 3 do begin new(num[i]); fillchar(num[i]^,sizeof(num[i]^),0); num[i]^[1]:=1; len[i]:=1; end; end; procedure Add;{高精度加法运算:num[3]=num[1]+num[2]} var i,carry:word;{carry 是进位数字} begin carry:=0; for i:=1 to len[2] do begin carry:=carry+num[2]^[i]+num[1]^[i]; num[3]^[i]:=carry mod 10; carry:=carry div 10; end; len[3]:=i; if carry>0 then begin inc(len[3]); num[3]^[i+1]:=carry; end; end;

procedure Work;{求从出发点到目标点的路径总数} var i:longint; begin num[1]^[1]:=1; num[2]^[1]:=1; for i:=start+2 to finish do begin Add;{高精度加法运算:num[3]=num[1]+num[2]} num[4]:=num[1]; num[1]:=num[2]; num[2]:=num[3]; num[3]:=num[4]; len[4]:=len[1]; move(len[2],len[1],6); end; end; procedure Out;{输出结果} var i:integer; begin for i:=len[2] downto 1 do write(num[2]^[i]); writeln; end; begin DataInit; {数据初始化} write('Input: '); readln(start,finish); Work; {求从出发点到目标点的路径总数} Out; {输出结果} end. 练习: 第 1 题(5 分),有 5 本不同的数学书分给 5 个男同学,有 4 本不同的英 语书分给 4 个女同学, 将全部书收回来后再从新发给他们,与原方案都不相同的 方案有________种。 答案: 5!*4!+D(5)*D(4)=1140480 其中:D(n)=(n-1)*(D(n-1)+D(n-2)) D(1)=0 D(2)=1 (n > 2)

第 2 题(5 分),在 m*n 的棋盘上,每个方格(单位正方形,即边长为 1 的正方形)的顶点称为格点。以格点为顶点的多边形称为格点多边形。若设格点 凸 N 边形面积的最小值为 gn,格点凸 N 边形内部(非顶点的)格点的个数的最小 值为 fn,则 gn 和 fn 的关系式为 gn=___________。 答案: Gn= fn+N/2-1 ( N >= 3 )

第 3 题(8 分),有位小同学喜欢在方阵中填数字,规则是按下图示例从 右上角开始,按斜线填数字,碰到边界就重新。显然,数字 1 在坐标(1,5)位置, 数字 25 在坐标(5,1)位置。后来这位小朋友想知道,对于 N 阶的方阵,随机取 一个位置(x,y),并规定 x≤y,问这个位置上应该填的数字是多少?5 阶方阵的 示例图如下: 11 16 20 23 25 答案: (N-y+x)*(N-y+x-1)/2+x 第 4 题(5 分),把三角形各边分成 n 等分,过每一分点分别做各边的平 行线, 得到一些由三角形的边和这些平行线所组成的平行四边形。 为已知整数, n 能组成_______个平行四边形。 答案: 3*C(n+2,4) 7 12 17 21 24 4 8 13 18 22 2 5 9 14 19 1 3 6 10 15

第 5 题(5 分),由 a,b,c3 个不同的数字组成一个 N 位数,要求不出 现两个 a 相邻, 也不出现两个 b 相邻, 这样的 N 位数的个数为 AN, AN-1 和 AN-2 用 表示 AN 的关系式为:AN=_______________。 答案: AN= 2*AN-1+AN-2

作者单位:江苏省洪泽县第二中学 姓 名:吴斌

通讯地址:江苏省洪泽县第二中学电教中心组 邮编: 电 223100

话:13912054539

QQ:372836808 邮件地址:HZEZDJZX@126.COM


推荐相关:

备战NOIP2010提高组初赛复习——问题求解篇

备战NOIP2010提高组初赛复习——问题求解篇_学科竞赛_高中教育_教育专区。备战 NOIP2010 提高组初赛复习——问题求解篇 问题求解是信息技术竞赛初赛中常见题型,它共两...


备战NOIP2010提高组初赛复习——算法篇之算法设计的常用策略

备战NOIP2010提高组初赛复习——算法篇之算法设计的常用策略_其它课程_高中教育_...算法设计的这种策略称之为分 治策略,即对问题分而治之。用分治策略求解一个...


备战NOIP2010提高组初赛复习——数据结构篇

备战NOIP2010提高组初赛复习——数据结构篇_工学_高等教育_教育专区。提高组初赛...采用首尾相 接的循环队列结构后,可以有效地解决假溢出的问题,避免数据元素的移动...


NOIP初赛复习——算法1

OK 备战 NOIP2010 提高组初赛复习——算法篇之算法设计的常用策略程序设计主要...§5.1 对应的策略将问题 A 对应另一个便于思考或有求解方法的问题 B,化繁...


Noip2010提高组初赛试题及详细解析(C语言)

Noip2010提高组初赛试题及详细解析(C语言)_建筑/土木_工程科技_专业资料。第十六...问题求解(共 3 题,每题 5 分,共计 15 分) 1.yyxy xx yyxy xyx xx ...


NOIP2010提高组初赛标准答案(C&C++)

如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 NOIP2010提高组初赛标准答案(C&C++) 为了那些喜欢C语言的同学而收集为了...


NOIP2010初赛程序填空

备战NOIP初赛问题求解之排... 3页 免费 冬令营讲稿 52页 免费 noip初赛选择题专题训练 7页 免费 NOIP2010初赛提高组-Pasca... 11页 免费如要投诉违规内容,请到...


NOIP2010提高组初赛试题答案C++

问题求解:(共 3 题,每空 5 分,共计 15 分) 1.yyxy xx yyxy xyx xx...NOIP2010提高组初赛答案 11页 免费 备战NOIP2010提高组初赛... 46页 免费 NOIP...


Noip2010提高组初赛试题及答案(C语言)

Noip2010提高组初赛试题及答案(C语言)_初一数学_数学_初中教育_教育专区。第...问题求解(共 3 题,每题 5 分,共计 15 分) 1.yyxy xx yyxy xyx xx ...


深入Noip2010初赛试题和全解

令信息学竞赛选手能更好地备战往后数届的 Noip 初赛,让初赛不再成为一个问题...(普及组仅有单项选择题,提高组则有单项选择 题与不定项选择题)、问题求解、...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com