信息学竞赛中问题求解题常见考查题型分析

1信息学竞赛中问题求解题常见考查题型分析Climber.pI整理一、寻找假币问题...................................................................................................................2二、取石子游戏的策略及其应用...........................................................................................5三、抽屉原理...........................................................................................................................8四、容斥问题.........................................................................................................................10五、排列组合问题.................................................................................................................14六、逻辑推理问题.................................................................................................................19七、递推关系的建立及在信息学竞赛中的应用.................................................................23问题求解是信息技术竞赛初赛中常见题型，它共两题，每题5分，共10分。诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合问题、逻辑推理、递推关系等问题出现在问题求解中，但是在实际的竞赛中，问题求解得分率往往是不高的，下面我对问题求解的题型进行了一下探索。作者单位：江苏省洪泽县第二中学姓名：吴斌通讯地址：江苏省洪泽县第二中学电教中心组邮编：223100电话：[phone]QQ:372836808邮件地址：[e-mail]2一、寻找假币问题有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。之前我们已经研究过，3个硬币1次就能称出来，故而f(9)=2。不难推广到一般的情况：定理1.1f(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、左偏，假币在A2、右偏，假币在B3、平衡，假币在C无论哪种结果，我们都把假币的范围缩小到了3k个硬币里面。而f(3k)=k，故而f(3k+1)=k+1。综上，定理1.1成立。3稍经分析不难得到：定理1.2f(n)=n3log这个的证明和定理1.1完全类似，分nmod3=0,1,2适当讨论即可。我们必须注意到n3log是可行的，因为我们能够构造出这样一个方案。问题是它是否最优？我们采取的方案是每次将硬币尽量均匀的三分，这样做的根据就是天平只有三种结果：左偏、右偏、平衡。于是就能保证无论假币在哪一份都能将结果的范围缩小到原来的1/3。从感性上认识，n3log应该就是最优解了。为了更加严格的证明n3log的最优性，我们引进判定树的概念。下图就是n=9时的一种判定树：此题的判定树是这样一棵树：1、叶子节点代表一种可能的结果。2、非叶子节点代表一次称量。3、非叶子节点至多有三个儿子，分别代表天平的左偏、右偏、平衡三种情况。任意一种称量方案都能唯一的表示成一棵判定树；反过来一棵判定树也唯一对应一种称量方案。容易看出判定树的深度就是称量次数。这就是我们之所以引进它的原因。做出判断之前，谁也无法预知哪个硬币是假币，每个都有可能是我们的目标；因此一个有意义的判定树应该具有至少n个叶子节点。n个叶子节点的树的深度h≥n3log，故而可以证明，f(n)=n3log是最优的。我们的结论是：有n(n≥3)个硬币，其中一个是假币，假币的重量比其他的要重一些。给一架天平，至少称n3log次，就能找出那个假币。比较(1,2,3)与(4,5,6)=比较(1)与(2)13=2比较(7)与(8)79=8比较(4)与(5)46=54具体的方案是将硬币每次都尽量均匀的三分。让我们总结一下。“三分”是整个解法的核心。我们选择三分，而不是二分或者四分是有原因的，它的本质是由判定树的特殊结构——三叉树——所决定的。同时还必须注意一点，我们在三分的时候有两个字很讲究：“均匀”。实际上h≥n3log中的“=”当且仅当硬币被均匀的分配时才能达到。这里说的“均匀”是指“在最坏情况下获得最好的效果”。因为一棵树的深度是由它根节点儿子中深度最大的儿子决定的，为了使得整个树深度最小，我们就要务必使得深度最大的儿子深度最小，这就是“均匀”分配的理论根据。练习：第12届全国青少年信息学奥林匹克联赛初赛题现有80枚硬币，其中有一枚是假币，其重量稍重，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第1次的称重方法。请写出你的结果：_________________________________________________。答案：4次；第一步，分成三组：27，27，26，将前2组放到天平上。5二、取石子游戏的策略及其应用有一种很有意思的游戏，就是有物体若干堆，可以是石子或是围棋子等等均可。两个人轮流从堆中取物体若干，规定最后取光物体者取胜。取石子游戏是我国民间流传已久的一种博奕，在国外亦称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，a2，…，am；k中，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)来描述这类取石子游戏，一人取走一次石子相6当于用某个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}；a12010a23011a35101122n1n2n3因为其中n1=1，所以{2，3，5}是非偶数组。同样，对于3元数组{2，3，1}：a1210a2311a310122n1n2由于nj(j=1，2)为偶数，则{2，3，1}为偶数组。偶数组与非偶数组在T变换下具有如下性质：(1)偶数组经过一次T变换之后一定变为非偶数组；(2)对于非偶数组，一定可以找到某一个T变换，使其变为偶数组。这样我们容易判定：如果给定的m元数组是偶数组，则后取者必有获胜策略；相反，若给定m元数组为非偶数组，则先取者有方法获胜，因为给定的m元数组为偶数组，先取者无论怎样取，只能将偶数组变为非偶数组，后取者则有策略将此时的非偶数组变为偶数组，由于每次取走石子，剩下石子数目一定越来越小，而{0，0，…，0}是偶数组，所以后取者获胜，同理可证相反情况。例2有三堆石子，各堆数目分别是2、3、6，两人轮流取，取完的人为胜者，若甲先乙后，谁取胜？解：7a12010a23011a36110131n1n2n3ni为奇数i=1，2，3，所以{2，3，6}为非偶数，我们可