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

《算法合集之《猜数问题的研究》.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、比较另类的数学题，如CTSC2001《聪明的学生》这样一道逻辑推理问题与竞赛中常考的组合数学题目不同，它并不要求选手掌握任何高深的数学知识，但对选手的抽象思维能力提出了挑战。IOI2003国家集训队论文猜数问题的研究问题描述两个例子的分析问题分析一些定义思路分析“终结情形”的条件“一类情形”能否转化为“终结情形”“二类情形”能否转化为“终结情形”编程实现中的若干问题结束语问题描述：一位逻辑学教授有n名非常善于推理且精于心算的学生。有一天,教授给他们n人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都

3、写了一个大于0的整数，并将他们分成了两组（一组学生有m人，m≥n/2，学生并不知道如何分组），两组学生头上数的和相等。于是，每个学生都能看见贴在另外n-1个同学头上的整数，但却看不见自己的数。教授轮流向n位学生发问：是否能够猜出自己头上的数。经过若干次的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误的报了出来。猜数问题的研究IOI2003国家集训队论文我们的问题就是：证明是否一定有人能够猜出自己头上的数，若有人能够猜出，则计算最早在第几次提问时有人先猜出头上的数，分析整个推理的过

4、程，并总结出结论。由于当n=3时，m只能为2，即为《聪明的学生》的问题原形，在论文中第一部分给出了证明。而对于m=n-1时的情况，作为原题的第一种推广情形，在论文中第二部分给出证明。下面着重讨论n>3，m

5、猜不出”若我与第一位学生一组，则我头上是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人若我与第一位

6、学生一组，则我头上是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

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

8、的算法，在每一次提问时，站在被提问的学生的角度去考虑问题，逐一考虑每个学生想法，直至某位学生能够猜出头上的数。让我们来分析一下这样做的时间复杂度：由于考虑可能的分组情况不同，头上的数就有可能不同。因此对于每位学生头上的数最多有种不同情况。因此对第N次提问，分析的复杂度为：可见，这样是不可能很好的解决问题的，我们必须从