信息学竞赛中问题求解常见题型.doc

信息学竞赛中问题求解常见题分析（一） 逻辑推理问题 问题求解是信息学竞赛初赛中常见题型，它共两题，每题5分，共10分。十六届增加了比重，有三题，占15分。诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合、逻辑推理、递推关系等问题出现在问题求解中。 逻辑推理问题 通常把只涉及一些相互的关联条件或关系，极少给出数量关系与几何图形的一类非常规数学问题叫逻辑推理问题。处理这类问题，要从一些关联的条件出发，应用某些数学知识，甚至日常生活常识，依据一定的思维规律(机智灵活、准确敏捷的思考)，通过分析、推理、排除不可能情况(剔除不合理成分)，然后作出正确的判断。 逻辑推理问题中常用到以下三条逻辑基本规律： (1)同一律：是指同一东西(对象)，它是什么就是什么，不能模棱两可，亦此亦彼； (2)矛盾律：是指互相对立(矛盾)的事不能都真，二者必有一假(即同一思想不能既真又假)； (3)排中律：是指两个不相容的判断不能都假，二者必有一真(即任何判断或同一思想不能既不真也不假)。 逻辑推理问题条件扑朔迷离，层次重叠纷纭，没有一定的定理可以依据，无现成公式可用，无模式可循，靠的是逻辑推理。可画框图，紧抓关系，细抠条件，寻找突破口，穷追到底，层层进逼，以求找到答案。 本文结合一些赛题，谈谈处理逻辑推理问题的一些主要方法。 一、利用逻辑原理，直接推理 对于一些简单的逻辑推理问题，往往只需以似真推理为主，直接通过分析就可以得出正确的结果。用这种方法解决“真假话”问题尤为有效。 例1．住在某个旅馆的同一房间的四个人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则是在看书。 二、利用表格辅助推理 某些逻辑推理问题中，有时会涉及很多对象，每个对象又有几种不同情况，同时还给出不同对象之间不同情况的判断,要求推出确定的结论。对于这类问题，通常可以利用表格把本来凌乱的信息集中整理出来，方便推理。 例2．甲、乙、丙、丁、戊五名同学参加推铅球比赛，通过抽签决定出赛川页序，在未公布顺序之前每人都对出赛顺序进行了猜测。甲猜：乙第三，丙第五；乙猜：戊第四，丁第五；丙猜：甲第一，戊第四；丁猜：丙第一，乙第二；戊猜：甲第三，丁第四。老师说每人的出赛川页序都至少被一人所猜中。第一、第三、第五分别是哪位同学? 解：本题相互关系过于复杂，不便分析和推断，不妨由已知条件列表如下： 由于每人的出赛川页序至少被一人所猜中，所以戊第四，丁第五，丙吝一，甲第三，乙第二；出赛的顺序：丙乙甲戊丁。 例3．某校举办作文比赛，A，B，C，D四位同学参加比赛，其中只有一位同学获奖。老师为了解比赛情况，分别向选手询问，回答如下： A：我获了奖； B：我没有获奖，C也没有获奖； C：是A获奖或B获奖； D：是B获奖； 事后证实，有两人的话符合事实，哪位同学获了奖? 解：“某人获奖’’就将此人记为“l”，否则为“0”。根据四个人的话可得下表。 由表可知，若是A获奖，则有3人说的话符合事实，只有B获奖时，有两人的话符合事实。 三、利用计算辅助推理 某些逻辑推理问题常常有几个未知量同时存在，或答案有多种可能性，解题时需要充分利用已知条件进行计算，并通过对计算结果的分析，推理得出正确的结论。 例4．学校进行了一次考试，考试的科目是语文、历史、数学、物理和英语，每科满分为5分，其余等级依次是4、3、2、1分。今已知按总分由多到少排列着五名学生，A，B，C，D，E满足下列条件： 在同一科目中以及在总分数中没有得同样分数的人；(2)A的总分是24分；(3)C有四门得了相同的分数；(4)E语文得3分，物理得5分；(5)D的历史得4分。试求题目中未直接给出的各人其他各科的成绩。 解：先从五人的总分入手，再扣掉A的得分，得出B，C，D，E四人的 总分，再从得分最低的E出发进行推断，即可逐步得出结果。 由已知可得5人的总分为5X(”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。 E两科8分，总分11分，因而E的英语、历史、数学各得1分。 A的总分是24分，故只有一科