《信息学竞赛中问题求解常见题分析一》由会员分享，可在线阅读，更多相关《信息学竞赛中问题求解常见题分析一（22页珍藏版）》请在金锄头文库上搜索。
1、信息学竞赛中问题求解常见题分析（一）逻辑推理问题问题求解是信息学竞赛初赛中常见题型，它共两题，每题5分，共10分。诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合、逻辑推理、递推关系等问题出现在问题求解中。逻辑推理问题通常把只涉及一些相互的关联条件或关系，极少给出数量关系与几何图形的一类非常规数学问题叫逻辑推理问题。处理这类问题，要从一些关联的条件出发，应用某些数学知识，甚至日常生活常识，依据一定的思维规律(机智灵活、准确敏捷的思考)，通过分析、推理、排除不可能情况(剔除不合理成分)，然后作出正确的判断。逻辑推理问题中常用到以下三条逻辑基本规律： (1)同一律：是指同一东西(对象)，它是什
2、么就是什么，不能模棱两可，亦此亦彼；(2)矛盾律：是指互相对立(矛盾)的事不能都真，二者必有一假(即同一思想不能既真又假)；(3)排中律：是指两个不相容的判断不能都假，二者必有一真(即任何判断或同一思想不能既不真也不假)。逻辑推理问题条件扑朔迷离，层次重叠纷纭，没有一定的定理可以依据，无现成公式可用，无模式可循，靠的是逻辑推理。可画框图，紧抓关系，细抠条件，寻找突破口，穷追到底，层层进逼，以求找到答案。本文结合一些赛题，谈谈处理逻辑推理问题的一些主要方法。一、利用逻辑原理，直接推理对于一些简单的逻辑推理问题，往往只需以似真推理为主，直接通过分析就可以得出正确的结果。用这种方法解决“真假话”问题
3、尤为有效。例1住在某个旅馆的同一房间的四个人A，B，C，D正在听一组流行音乐，他们当中有一个人在修指甲，一个人在写信，一个人躺在床上，一个人在看书。 1A不在修指甲，也不在看书； 2B不躺在床上，也不在修指甲；3如果A不躺在床上，那么D不在修指甲；4C既不在看书，也不在修指甲；5D不在看书，也不躺在床上。她们各自在做什么呢?解：由1，2，4，5知，既不是A，B在修指甲，也不是C在修指甲，因此 修指甲的应该是D；但这与3的结论相矛盾，所以3的前提肯定不成 立，即A应该是躺在床上；在4中C既不看书又不修指甲，由前面分析， C又不可能躺在床上，所以C是在写信；而B则是在看书。二、利用表格辅助推理某些
4、逻辑推理问题中，有时会涉及很多对象，每个对象又有几种不同情况，同时还给出不同对象之间不同情况的判断,要求推出确定的结论。对于这类问题，通常可以利用表格把本来凌乱的信息集中整理出来，方便推理。例2甲、乙、丙、丁、戊五名同学参加推铅球比赛，通过抽签决定出赛川页序，在未公布顺序之前每人都对出赛顺序进行了猜测。甲猜：乙第三，丙第五；乙猜：戊第四，丁第五；丙猜：甲第一，戊第四；丁猜：丙第一，乙第二；戊猜：甲第三，丁第四。老师说每人的出赛川页序都至少被一人所猜中。第一、第三、第五分别是哪位同学?解：本题相互关系过于复杂，不便分析和推断，不妨由已知条件列表如下：顺序人名一二三四五甲乙丙乙戊丁丙甲戊丁丙乙戊甲
5、丁由于每人的出赛川页序至少被一人所猜中，所以戊第四，丁第五，丙吝一，甲第三，乙第二；出赛的顺序：丙乙甲戊丁。例3某校举办作文比赛，A，B，C，D四位同学参加比赛，其中只有一位同学获奖。老师为了解比赛情况，分别向选手询问，回答如下： A：我获了奖； B：我没有获奖，C也没有获奖； C：是A获奖或B获奖； D：是B获奖； 事后证实，有两人的话符合事实，哪位同学获了奖?解：“某人获奖就将此人记为“l”，否则为“0”。根据四个人的话可得下表。获奖者说话者ABCDA1000B1001C1100D0100由表可知，若是A获奖，则有3人说的话符合事实，只有B获奖时，有两人的话符合事实。三、利用计算辅助推理
6、某些逻辑推理问题常常有几个未知量同时存在，或答案有多种可能性，解题时需要充分利用已知条件进行计算，并通过对计算结果的分析，推理得出正确的结论。例4学校进行了一次考试，考试的科目是语文、历史、数学、物理和英语，每科满分为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四人的 总分，
7、再从得分最低的E出发进行推断，即可逐步得出结果。(1) 由已知可得5人的总分为5X(”2+3+4+5)二75分。 因A得24分，故B，C，D，E共得7524：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 的物理得5分，故语文、历史、数学、英语各5分。(4) C的总分为13分，且有四科得分相同，故得分情况只能是一科 5分，四科各2分或一科1分，四科各3分。因5分为A，、E所得，则C 的四
8、科各得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分。例5赵、钱、孙、李四人，一个是教师，一个是售货员，一个是工人， 一个是机关干部。试根据以下条件，判断这四人的职业。(1)赵和钱是邻居，每天一起骑车上班； (2)钱比孙年龄大； (3)赵在教李打太极拳； (4)教师每天步行去上班； (5)售货员的邻居不是机关干部；(6)机关干部和工人互不相识；(7)机关干部比售货员
9、和工人年龄都大。解：由条件(4)和条件(1)可知赵、钱都不是教师。由条件(2)和条件 (7)，可推知孙不是干部。如果是的话，钱不是工人或售货员，钱又不是 教师，于是，钱也是干部，矛盾。这样我们得到下表。下面几步推理也用 表格说明。 四、利用图形辅助推理 美国数学家斯蒂恩说过广如果一个特定的问题可以被转化成一个 图形，那么，思想就整体地把握了问题，并且能创造性地思索问题解法。 例6A，B，C，D，E五支球队进行单循环比赛(每两支球队间都要进行一场比赛)，当比赛进行到一定阶段时，统计A，B，C，D四个球队已经赛过的场数，依次为A队4场，B队3场，C队2场，D队1场，这时，E队已赛过的场数是()。A
10、1 B2 C3 D4 解：用五个点分别表示A，B，C，D，E五支球队，将它们之间比赛的情况用右图表示出来。信息学竞赛中问题求解常见题分析（二）递推问题 瞬息万变的世界，每一件事物都在随时间的流逝发生着微妙的变化。而在这纷繁的变幻中，许多现象的变化是有规律的，这种规律往往呈现出前因和后果的关系。即是说，某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。本文将围绕着递推关系的三大基本问题中如何建立递推关系展开论述，并通过例题说明递推关系在当今信息学竞赛中的应用。 一、递推关系的定义相信每个人对递推关系都不陌生，但若要说究竟满足什么样的条件就是递推关系，可能每个人又会有不同的说法。为了更好
11、地研究递推关系，首先让我们明确什么是递推关系。【定义l】给定一个数的序列H0，H1，Hn若存在整数no，使当n=no时，可以用等号将Hn与其前面的某些项Hn。(0=in)联系起来，这样的式子就叫做递推关系。二、递推关系的建立递推关系中存在着三大基本问题：如何建立递推关系，已给的递推关系有何性质，以及如何求解递推关系。建立递推关系的关键在于寻找第n项与前面几项的关系式，以及初始项的值。它不是一种抽象的概念，是需要针对某一具体题目或一类题目而言的。在下文中，我们将对五种典型的递推关系的建立作比较深入具体的讨论。1 四种典型的递推关系 Fibonacci数列型在所有的递推关系中，Fibonacci数
12、列应该是最为大家所熟悉的，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
13、=l，F3=F2+F1=2，F4=F3+F2=3，F5=F4+F3=5，。IIHanoi塔问题问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a，b，c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图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拄
14、移到c柱：最后，将b柱上的小盘子移到c柱上，共计3个盘次，故h2=3。依此类推，当a柱上有n(n2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b拄上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c拄上；总共移动hn-1+1+ hn-1个盘次。因此hn=2hn-1+1边界条件：hn-1=1平面分割问题问题的提出：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。解：设an为n条封闭曲线把平面分割成的区域个数。 由图2可以看出：a2-a1=2；a3-a2=4；a4-a3=6。从
15、这些式子中可以看出。an-an-1=2(n-1)。当然，上面的式子只是我们通过观察4幅图后得出的结论，它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有n-1条曲线将平面分割成an-1个区域后，第n条曲线每与曲线相交一次，就会增加一个区域，因为平面上已有了n-1条封闭曲线，条件中第n条曲线与已有的每一条闭曲线恰好相交于两点，且不会与任两条曲线交于同一点，故平面上一共增加2(n-1)个区域，加上已有的an-1个区域，一共有an-1+2(n-1)个区域。所以本题的递推关系是an=an-1+2(n-1)，边界条件是a1=1图2平面分割问题是竞赛中经常触及到的一类问题，由于其灵活多变，常常让选手感到棘手 . Catalan数 Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形部分的个数问题时得到的，它经常出现在组合计数问题中问题的提出：在一个凸n边形中，通过不相交于n边形内部的对角线，
