算法合集之《猜数问题的研究》.ppt

猜数问题的研究 聪明的学生 一题的推广,上海市复旦附中 张宁,猜数问题的研究,IOI2003国家集训队论文,近年来，信息学奥赛的试题涵盖面越来越广，不仅在程序设计方面对选手掌握算法与数据结构的要求越来越高，对选手的数学水平也提出更高的要求。,我个人对这个有趣的问题比较感兴趣，对题目进行了深入的思考，并将其推广到一般情形。下面将主要从数学证明的角度来分析问题，由于时间关系，我将略过原问题的证明，以及第一种简单的推广，选择第二种推广的部分证明进行讲解。（论文中有详细证明）,而数学类问题的难度，并不在于编程，而在于思想。其中也不乏一些比较另类的数学题，如CTSC2001聪明的学生这样一道逻辑推理问题与竞赛中常考的组合数学题目不同，它并不要求选手掌握任何高深的数学知识，但对选手的抽象思维能力提出了挑战。,IOI2003国家集训队论文,猜数问题的研究,问题描述 两个例子的分析 问题分析 一些定义 思路分析 “终结情形”的条件 “一类情形”能否转化为“终结情形” “二类情形”能否转化为“终结情形” 编程实现中的若干问题 结束语,问题描述： 一位逻辑学教授有n名非常善于推理且精于心算的学生。有一天,教授给他们n人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个大于0的整数，并将他们分成了两组（一组学生有m人，mn/2，学生并不知道如何分组），两组学生头上数的和相等。于是，每个学生都能看见贴在另外n-1个同学头上的整数，但却看不见自己的数。 教授轮流向n位学生发问：是否能够猜出自己头上的数。经过若干次的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误的报了出来。,猜数问题的研究,IOI2003国家集训队论文,我们的问题就是：证明是否一定有人能够猜出自己头上的数，若有人能够猜出，则计算最早在第几次提问时有人先猜出头上的数，分析整个推理的过程，并总结出结论。,由于当n=3时，m只能为2，即为聪明的学生的问题原形，在论文中第一部分给出了证明。而对于m=n-1时的情况，作为原题的第一种推广情形，在论文中第二部分给出证明。下面着重讨论n3，mn-1时的情况。,猜数问题的研究,IOI2003国家集训队论文,猜数问题的研究,IOI2003国家集训队论文,有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”,有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次提问中最先猜出头上的数，就可以根据实际上别人并没有在他之前猜出这一矛盾来排除头上是某数的情况。 而当某位学生能够排除所有不同于实际的可能值时他便猜出自己头上的数了。 这样我们能够设计出最基本的算法，在每一次提问时，站在被提问的学生的角度去考虑问题，逐一考虑每个学生想法，直至某位学生能够猜出头上的数。,让我们来分析一下这样做的时间复杂度： 由于考虑可能的分组情况不同，头上的数就有可能不同。因此对于每位学生头上的数最多有 种不同情况。 因此对第N次提问，分析的复杂度为： 可见，这样是不可能很好的解决问题的，我们必须从根本上去优化算法，唯一的途径就是从问题的本质去研究其中的联系，从而避开表面上繁琐的“思维嵌套”，即：在C的脑海中要考虑B是如何思考A的想法。,IOI2003国家集训队论文,猜数问题的研究,猜数问题的研究,1,1,2,2,第一位学生,第二位学生,第三位学生,第四位学生,用n+1元组 来描述推理过程中的一种情形，其中n个人头上数分别为 ,从第一位学生开始提问，且当前的被提问者为第k位学生。,对于n+1元组 ，第k位学生可以不依靠别人的回答进行推理，能够直接判断出自己头上数，称n+1元组描述的情形为“终结情形”。,对于n+1元组 ，Ak maxA1,A2,An，称n+1元组描述的情形为“一类情形”。 对于n+1元组 ，Ak =maxA1,A2,An，称n+1元组描述的情形为“二类情形”。,如(1,1,2,2,1)，(1,1,2,2,2)为“一类情形”，(1,1,2,2,3)，(1,1,2,2,4)为“二类情形”,在左边的例子中，若对第一位学生进行提问，可以用5元组(1,1,2,2,1)来表示,在左边的例子中，若对第三位学生进行提问时，第三位学生可以直接推理出头上的数是2，因此5元组(1,1,2,2,3)是“终结情形”,IOI2003国家集训队论文,有4位学生，且每组有2人,猜数问题的研究,IOI2003国家集训队论文,对于 ，用X指代第k位学生推测的任意一种分组情况。定义 为第k位学生假设分组X情况下两组学生头上数的和。记 为所推测出的头上数的可能值。,1,1,2,2,第一位学生,第二位学生,第三位学生,第四位学生,右面的例子中，对每位学生，都有三种不同的分组情况： 1.一与二一组，三与四一组 2.一与三一组，二与四一组 3.一与四一组，二与三一组 当第一位学生推测自己与第二位学生同一组时，可以计算出另一组学生头上数的和2+2=4，进而可以推测出在这种情况下自己头上的数有可能为4-1=3,有4位学生，且每组有2人,定义 ，其中 定义分组T：选取第 位学生为一组，剩下的学生为另一组（第k位学生在这一组）。则,右面的例子中，对第一位学生，分组T为，一与二一组，三与四一组。,注意到mn/2，因此,对于 任意一个分组X，设,G(T)=2+2=4,=2+2-1=3 2,显然有,M=1+2+2=5,在上例中，考虑第一位学生,IOI2003国家集训队论文,猜数问题的研究,每位学生由于不能直接判断头上一定是某数，就只能采取排除法。由于他们不会猜错，因此只需考虑他们如何能够排除头上数不同于实际的可能情况。显然只有通过推理导出矛盾，才能够得到有用的信息，排除某些可能情况。因此，问题的关键就在于分析如何导出矛盾。,IOI2003国家集训队论文,猜数问题的研究,IOI2003国家集训队论文,猜数问题的研究,我们已在定义中将能够不通过推理直接猜出头上的数的情况，称之为“终结情形”。考虑上面的分析，若某人处于“终结情形”，而他却没有猜出头上的数，这显然是一个矛盾。而对于不是“终结情形”的情况，则需要进行推理。因此问题转变为考虑怎样的情况为“终结情形”，以及怎样的情况能够通过推理转变为“终结情形”，可见解决问题的关键，在于深入分析“终结情形”。,IOI2003国家集训队论文,猜数问题的研究,而我们之所以在定义中将所有学生分成了两类考虑：“一类情形”及“二类情形”，是受到原问题聪明的学生的启发，虽然在推广的问题中，头上数最大的学生不再处于十分特殊的地位，即头上数为其余学生头上数的和，并且可能有不止一人头上的数为最大数。但我们有理由相信这依然是解决问题的一个入手点。,考虑在分组T的情况下 这种情况不同于实际情况，需要进行推理。得到结论：“一类情形”不可能为“终结情形”。,若不存在可能的分组C满足 ，即任意分组 即,要使得 为终结情形 ，必然要满足在分组T的情况下 。因此实际分组B满足 ，因此可得， 。,考虑“终结情形”的条件：,当 为“一类情形 ”,当 为“二类情形 ”,显然 ，在此条件下，若存在可能的分组C满足 ， 。显然由于 为终结情形，必然有 ，,IOI2003国家集训队论文,猜数问题的研究,当 不全相等时，必然有 ，考虑如下分组C：第 位学生为一组，第 位学生为一组，此时显然有,进一步分析对可能的分组C满足 ，何时满足 ，分两种情况考虑：,需满足 ，因此 而 矛盾。因此，若 ， 不可能为终结情形.。,IOI2003国家集训队论文,猜数问题的研究,当 全相等时，不妨设 ， 考虑分组C：m个头上数为q的学生为一组，剩下的学生为一组（第k位学生在这组中）。 由于 ，因此 。 当 时，再来考虑分组D：头上数是p的学生与n-m-1个头上数是q的学生在一组, 剩下学生为一组。 。 由于 ，因此 ，观察得到的两个不等式，显然矛盾，因此当 时，若 ， 不可能为终结情形。 当 时，可以得到 ，且 。,IOI2003国家集训队论文,猜数问题的研究,因此终结情形的条件为 或 为二类情形，且,有4位学生，且每组有2人,在左例中，可以用上述结论，推出第三、四位学生可以不依靠别人的回答进行推理，直接猜出头上的数,IOI2003国家集训队论文,猜数问题的研究,IOI2003国家集训队论文,猜数问题的研究,我们可以考虑所有能够猜出自己头上数的“一类情形”中所用猜测次数最少的情况，利用极端性原则，用反证法可以证明，任何“一类情形”的被提问者都不可能最先猜出自己头上的数。由于证明过程非常繁琐，考虑到时间关系，这里将不给出详细的证明过程。 由于推理过程中是利用产生矛盾来得出结果的，因此我们利用上面这一结论，可以忽略推理过程中所有的“一类情形”，即我们只需考虑头上数最大的学生的想法。,IOI2003国家集训队论文,猜数问题的研究,由于关于这一部分的证明极其繁琐，考虑到时间关系，下面只能给出一些结论,若n个学生头上的数都相等，则第一位学生可以猜出头上的数。 若n个学生头上的数不全相等 若有三个以上的最大数或mn/2，则没有人能够猜出头上的数 若有两个最大数 若n=4，则必然是头上数最大的人猜出头上的数，但需要通过推理才能确定由哪一人 若n4，则没有人能够猜出头上的数 若只有一个最大数，则需进行推理,若推理过程中出现“终结情形”，则可以直接得到结果，否则需要考虑每一种可能的分组情况，对有可能猜出头上数的学生，必然要满足如下条件： 任意可能分组C符合 ，满足,且推理过程中，n个学生头上的数始终在减小,IOI2003国家集训队论文,猜数问题的研究,虽然我们对问题进行了深入的分析，对推理加强了判定，对算法本质进行了优化，将解决问题的时间复杂度大幅度下降，但依然可能出现多种考虑情况。所以推理已不像聪明的学生那样是一个线性结构的推理，整个推理过程将成为树状结构。 因此我们除了在算法本质上进行优化的同时，加强在编程实现的优化，由于考虑到我们总结出的推理方式中，n个学生头上的数始终在减小，因此我们可以采用纪录搜索的方式解决问题，为了加快检索速度，可以采用Hash表，并且我们为了方便描述一个情形，即n位学生头上的数，可以采用一个n位p进制数来描述。 综合两方面的优化，我们已经较为圆满的解决了这个问题。,我们深入地分析了一个逻辑推理问题，从综观全局的角度来考虑问题的本质联系，而非一味单纯地从每个人的思想出发，简化了最烦琐的“思维嵌套”，因此避免了问题规模随着推理次数急剧增长，有效地解决了问题。 从基本的例子入手分析 考虑问题的本质从本质入手分析矛盾考虑何种情形为“终结情形”考虑何种情形能归结到“终结情形”分情况讨论并加以证明得出结论并形成算法 相信对这样一道问题的解决，对处理繁琐的“思维嵌套”问题提供了一种可以借鉴的方法。,IOI2003国家集训队论文,猜数问题的研究,谢谢！,请多多指教,