算法合集之〔猜数问题的研究〕.ppt

猜数问题的研究——《聪明的学生》 一题的推广 上海市复旦附中张宁 问题描述 两个例子的分析 问题分析 一些定义 思路分析 “终结情形”的条件 “一类情形”能否转化为“终结情形” “二类情形”能否转化为“终结情形” 编程实现中的若干问题 结束语 谢谢！ * * 猜数问题的研究 IOI2003国家集训队论文 近年来，信息学奥赛的试题涵盖面越来越广，不仅在程序设计方面对选手掌握算法与数据结构的要求越来越高，对选手的数学水平也提出更高的要求。 我个人对这个有趣的问题比较感兴趣，对题目进行了深入的思考，并将其推广到一般情形。下面将主要从数学证明的角度来分析问题，由于时间关系，我将略过原问题的证明，以及第一种简单的推广，选择第二种推广的部分证明进行讲解。（论文中有详细证明） 而数学类问题的难度，并不在于编程，而在于思想。其中也不乏一些比较另类的数学题，如CTSC2001《聪明的学生》这样一道逻辑推理问题与竞赛中常考的组合数学题目不同，它并不要求选手掌握任何高深的数学知识，但对选手的抽象思维能力提出了挑战。 IOI2003国家集训队论文 猜数问题的研究 问题描述： 一位逻辑学教授有n名非常善于推理且精于心算的学生。有一天,教授给他们n人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个大于0的整数，并将他们分成了两组（一组学生有m人，m≥n/2，学生并不知道如何分组），两组学生头上数的和相等。于是，每个学生都能看见贴在另外n-1个同学头上的整数，但却看不见自己的数。 教授轮流向n位学生发问：是否能够猜出自己头上的数。经过若干次的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误的报了出来。 猜数问题的研究 IOI2003国家集训队论文 我们的问题就是：证明是否一定有人能够猜出自己头上的数，若有人能够猜出，则计算最早在第几次提问时有人先猜出头上的数，分析整个推理的过程，并总结出结论。 由于当n=3时，m只能为2，即为《聪明的学生》的问题原形，在论文中第一部分给出了证明。而对于m=n-1时的情况，作为原题的第一种推广情形，在论文中第二部分给出证明。下面着重讨论n3，mn-1时的情况。 猜数问题的研究 IOI2003国家集训队论文 猜数问题的研究 IOI2003国家集训队论文 1 第一位学生 1 第二位学生 2 第四位学生 2 第三位学生 有4位学生，且每组有2人 我与第二位学生一组，头上是2+2-1=3 我与第三位学生一组，头上是1+2-2=1 我与第四位学生一组，头上是1+2-2=1 不能判断是1还是3， 回答：“猜不出” 若我与第一位学生一组，则我头上是2+2-1=3，第一位学生将看到三个数为3,2,1，第一位学生不能确定自己头上是4还是2，因此他猜不出，我也无法排除这种情况。 若我与第三位学生一组，… 若我与第四位学生一组， … 不能判断是1还是3， 回答：“猜不出” 若我与第一位学生一组，则我头上是2+1-1=2，… 若我与第二位学生一组，则我头上是2+1-1=2， … 若我与第四位学生一组，则我头上是1+1-2=0，不可能 头上只可能为2 回答：“我头上的数是2” 1 第一位学生 2 第二位学生 2 第四位学生 3 第三位学生 有4位学生，且每组有2人 若我与第一位学生一组，则我头上是3+2-1=4，第一位学生将看到三个数为4,3,2，第一位学生不能确定自己头上是5,3,1中哪一种，因此他猜不出，我也无法排除这种情况。 若我与第三位学生一组，… 若我与第四位学生一组， … 不能判断是４还是２， 回答：“猜不出” 猜数问题的研究 IOI2003国家集训队论文 我与第二位学生一组，头上是3+2-2=3 我与第三位学生一组，头上是2+2-3=1 我与第四位学生一组，头上是3+2-2=3 不能判断是1还是3， 回答：“猜不出” 若我与第一位学生一组，则我头上是2+2-1=3，… 若我与第二位学生一组，则我头上是2+1-2=1， … 若我头上的数是１，则第二位学生将看见三个数，1,1,2三个数，则他可以断定自己头上的数是2，但他并没有在我之前猜出，因此我头上一定不是1 头上只可能为3 回答：“我头上的数是3” IOI2003国家集训队论文 猜数问题的研究 我们先来分析一下，如何能够猜出自己头上的数。当某位学生假设自己头上是某数，并通过推理发现别人理应能够在前n-1次提问中最先猜出头上的数，就可以根据实际上别人并没有在他之前猜出这一矛盾来排除头上是某数的情况。 而当某位学生能够排除所有不同于实际的可能值时他便猜出自己头上的数了。 这样我们能够设计出最基本的算法，在每一次提问时，站在被提问的学生的角度去考虑问题，逐一考虑每个学生想法，直至某位学生能够猜出头上的