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

1、上海市复旦附中张宁猜数问题的研究IOI2003国家集训队论文近年来，信息学奥赛的试题涵盖面越来越广，不仅在程序设计方面对选手掌握算法与数据结构的要求越来越高，对选手的数学水平也提出更高的要求。我个人对这个有趣的问题比较感兴趣，对题目进行了深入的思考，并将其推广到一般情形。下面将主要从数学证明的角度来分析问题，由于时间关系，我将略过原问题的证明，以及第一种简单的推广，选择第二种推广的部分证明进行讲解。（论文中有详细证明）而数学类问题的难度，并不在于编程，而在于思想。其中也不乏一些比较另类的数学题，如CTSC2001聪明的学生这样一道逻辑推理问题与竞赛中常考的组合数学题目不同，它并不要求选手掌握任

2、何高深的数学知识，但对选手的抽象思维能力提出了挑战。IOI2003国家集训队论文猜数问题的研究w 问题描述w 两个例子的分析w 问题分析w 一些定义w 思路分析w“终结情形”的条件w“一类情形”能否转化为“终结情形”w“二类情形”能否转化为“终结情形”w 编程实现中的若干问题w 结束语问题描述：一位逻辑学教授有n名非常善于推理且精于心算的学生。有一天,教授给他们n人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个大于0的整数，并将他们分成了两组（一组学生有m人，mn/2，学生并不知道如何分组），两组学生头上数的和相等。于是，每个学生都能看见贴在另外n-1个同学头上

3、的整数，但却看不见自己的数。教授轮流向n位学生发问：是否能够猜出自己头上的数。经过若干次的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误的报了出来。猜数问题的研究IOI2003国家集训队论文我们的问题就是：证明是否一定有人能够猜出自己头上的数，若有人能够猜出，则计算最早在第几次提问时有人先猜出头上的数，分析整个推理的过程，并总结出结论。由于当n=3时，m只能为2，即为聪明的学生的问题原形，在论文中第一部分给出了证明。而对于m=n-1时的情况，作为原题的第一种推广情形，在论文中第二部分给出证明。下面着重讨论n3，mn-1时的情况。猜数问题的研究IOI20

4、03国家集训队论文猜数问题的研究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，若我与第二位学生一组，则我

5、头上是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不能判断

6、是1还是3，回答：“猜不出”若我与第一位学生一组，则我头上是2+2-1=3，若我与第二位学生一组，则我头上是2+1-2=1，若我头上的数是，则第二位学生将看见三个数，1,1,2三个数，则他可以断定自己头上的数是2，但他并没有在我之前猜出，因此我头上一定不是1头上只可能为3回答：“我头上的数是3”IOI2003国家集训队论文猜数问题的研究我们先来分析一下，如何能够猜出自己头上的数。当某位学生假设自己头上是某数，并通过推理发现别人理应能够在前n-1次提问中最先猜出头上的数，就可以根据实际上别人并没有在他之前猜出这一矛盾来排除头上是某数的情况。而当某位学生能够排除所有不同于实际的可能值时他便猜出自己

7、头上的数了。这样我们能够设计出最基本的算法，在每一次提问时，站在被提问的学生的角度去考虑问题，逐一考虑每个学生想法，直至某位学生能够猜出头上的数。让我们来分析一下这样做的时间复杂度：由于考虑可能的分组情况不同，头上的数就有可能不同。因此对于每位学生头上的数最多有 种不同情况。因此对第N次提问，分析的复杂度为：可见，这样是不可能很好的解决问题的，我们必须从根本上去优化算法，唯一的途径就是从问题的本质去研究其中的联系，从而避开表面上繁琐的“思维嵌套”，即：在C的脑海中要考虑B是如何思考A的想法。mnC)(NmnCOIOI2003国家集训队论文猜数问题的研究猜数问题的研究1122第一位学生第二位学生

8、第三位学生第四位学生用n+1元组 来描述推理过程中的一种情形，其中n个人头上数分别为 ,从第一位学生开始提问，且当前的被提问者为第k位学生。对于n+1元组 ，第k位学生可以不依靠别人的回答进行推理，能够直接判断出自己头上数，称n+1元组描述的情形为“终结情形”。对于n+1元组 ，Ak n/2，则没有人能够猜出头上的数v若有两个最大数若n=4，则必然是头上数最大的人猜出头上的数，但需要通过推理才能确定由哪一人若n4，则没有人能够猜出头上的数v若只有一个最大数，则需进行推理若推理过程中出现“终结情形”，则可以直接得到结果，否则需要考虑每一种可能的分组情况，对有可能猜出头上数的学生，必然要满足如下条

9、件：任意可能分组C符合 ，满足MTGAk)(2)()(BGCG1AtAk且推理过程中，n个学生头上的数始终在减小IOI2003国家集训队论文猜数问题的研究虽然我们对问题进行了深入的分析，对推理加强了判定，对算法本质进行了优化，将解决问题的时间复杂度大幅度下降，但依然可能出现多种考虑情况。所以推理已不像聪明的学生那样是一个线性结构的推理，整个推理过程将成为树状结构。因此我们除了在算法本质上进行优化的同时，加强在编程实现的优化，由于考虑到我们总结出的推理方式中，n个学生头上的数始终在减小，因此我们可以采用纪录搜索的方式解决问题，为了加快检索速度，可以采用Hash表，并且我们为了方便描述一个情形，即n位学生头上的数，可以采用一个n位p进制数来描述。综合两方面的优化，我们已经较为圆满的解决了这个问题。我们深入地分析了一个逻辑推理问题，从综观全局的角度来考虑问题的本质联系，而非一味单纯地从每个人的思想出发，简化了最烦琐的“思维嵌套”，因此避免了问题规模随着推理次数急剧增长，有效地解决了问题。从基本的例子入手分析 考虑问题的本质从本质入手分析矛盾考虑何种情形为“终结情形”考虑何种情形能归结到“终结情形”分情况讨论并加以证明得出结论并形成算法相信对这样一道问题的解决，对处理繁琐的“思维嵌套”问题提供了一种可以借鉴的方法。IOI2003国家集训队论文猜数问题的研究谢谢！请多多指教