论文--一类猜数问题的研究

《论文--一类猜数问题的研究 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一类猜数问题的研究【摘要】猜数问题是信息学竞赛中一种常见的类似博弈的问题。其中部分的问题是给出猜的数与被猜数之间的大小关系作为回答信息。作为信息学竞赛中一类经常出现的问题，很有研究的意义与价值。本文重点对这类问题的不同形式的解法进行讨论与研究。本文先提出了一个看似复杂、棘手的问题，然后慢慢通过分析剖析其本质，提出一个行之有效的解法，并在此基础上对其他相关的问题展开讨论。【关键字】二分法、递推法、数学模型、动态规划【引言】信息学竞赛中常常看到诸如此类的问题：现在有一个数X，是1~N之内的。你每次可以猜一个数Y，然后会根据你提供的Y与X的大小关系，给出XY三种回答。

2、你要用尽量少的询问次数把X猜出来，也就是得到X=Y的回答。那么在最坏情况下至少需要多少次呢？有很多问题都是在这个基础上进行了扩充和加强，从而变成了棘手的问题，但是它们的本质是相同的。所以对这类问题的研究，并进行一定的整理和归纳还是很有必要的。【正文】一、问题的提出引言中已经对本文要讨论的问题类型作了基本定义，下面就来看一道如上文所说被“扩充和加强了的”猜数问题。模型王子：TL家有无数个高达机器人的模型，这已经不是一个秘密。终于有一天，你忍不住了，问TL：你家到底有多少个模型呢？TL：就是不告诉你J。You：说吧说吧，别保密了咯，我不会让老师知道的。TL：这样吧，我让你猜，你每次猜

3、一个数，我会告诉你比这个数大还是小。你快点猜出来，我马上就要去奶奶家吃饭去了。你以你的打字速度每1s可以提一个问题，但是由于该遭天杀的网络延迟。TL的回答要在1s之后才会传到你这里来。也就是说，只有当你提出了下一个问题之后，这个问题的答案才会告诉你。同时，由于TL心高气傲。如果你低估他拥有的模型数量，他就会生气。如果你低估了他K（1<=K<=100）次，他就不再陪你玩了。你最开始已经知道，TL的模型数量至少有1个，至多不超过N（1<=N<=105）个。下面是一个N=6时的可能的询问过程：事件时间You：你有3个模型吧？1sTL：网络延迟，没反应……1sYou：你有5个吧？2sTL

4、：你怕我像你一样，只有3个模型！！！（生气）2sYou：哦哦哦哦哦，那你有6个？3sTL：显然没有5个那么多。哪个像你那么有钱K。3sYou：你有4个模型吧。4sTL：都说了没有5个，你还问有没有6个。4sYou：你肯定是有4个模型咯。5sTL：对对对，我有4个模型。傻瓜，猜这么久。5s你现在已经知道TL的模型数量不少于1个，不超过N个。并且知道TL生气K次之后就不会再陪你玩了，请你算算，最优询问策略在最坏情况下，至少需要多少秒才能问出具体的模型数量。把这道题目抽象一下，会发现就是在引言中所讲的猜数问题原型上加上了几个限制条件。本题是说：有一个被猜数X，是1到N的范围内的整数，你

5、每次可以给出一个整数Y。你会在你问下一个问题之后得到你这个问题的回答，即X与Y的大小关系。并且如果你得到了K次X

6、请问在最坏情况下至少需要几次才能保证猜出X。通常能够想到的方法就是基于二分的询问，这是依据经验得来的。具体上说就是：如果已知X在[L,R]之内，那么令，如果YX则可以确定X在[L,Mid-1]之内，若Y=X则表示已经猜出来了。上面算法的最优性是显然的，因为每次都将区间尽量均分，使得最坏情况下，下一次需要处理的区间的大小尽可能的小。具体证明这里就略过。需要注意的是，问题要求的是次数。那么需要询问的次数是不是简单的，显然不是的。因为对于每次询问的回答有三种可能，即还存在X=Y的关系。用数学的语言描述，设f(i)表示询问i次询问能够处理长度

7、为f(i)的区间，下图分析了f(i)应该满足的关系。当回答为XY时，X可能出现的区间。LRY当进行完了一次询问之后，就只剩下i-1次询问了。绿色区间的长度和红色区间的长度不能超过i-1次询问能够处理的范围。也就是说绿色区间和红色区间的长度最大也就是f(i-1)。这样，我们就得到了相应的递推式：当回答X>Y之后还剩下i-1次提问机会。能够处理长度为f(i-1)的区间。当回答X