龙凡《一类猜数问题的研究》

2006年全国信息学冬令营讲座一类猜数问题的研究长沙市雅礼中学龙凡【摘要】猜数问题是信息学竞赛中一种常见的类似博弈的问题。其中部分的问题是给出猜的数与被猜数之间的大小关系作为回答信息。作为信息学竞赛中一类经常出现的问题，很有研究的意义与价值。本文重点对这类问题的不同形式的解法进行讨论与研究。本文先提出了一个看似复杂、棘手的问题，然后慢慢通过分析剖析其本质，提出一个行之有效的解法，并在此基础上对其他相关的问题展开讨论。【关键字】二分法、递推法、数学模型、动态规划【引言】信息学竞赛中常常看到诸如此类的问题：现在有一个数X，是1~N之内的。你每次可以猜一个数Y，然后会根据你提供的Y与X的大小关系，给出XY，X=Y，XY三种回答。你要用尽量少的询问次数把X猜出来，也就是得到X=Y的回答。那么在最坏情况下至少需要多少次呢？有很多问题都是在这个基础上进行了扩充和加强，从而变成了棘手的问题，但是它们的本质是相同的。所以对这类问题的研究，并进行一定的整理和归纳还是很有必要的。【正文】一、问题的提出引言中已经对本文要讨论的问题类型作了基本定义，下面就来看一道如上文所说被“扩充和加强了的”猜数问题。模型王子：TL家有无数个高达机器人的模型，这已经不是一个秘密。终于有一天，你忍不住了，问TL：你家到底有多少个模型呢？TL：就是不告诉你。You：说吧说吧，别保密了咯，我不会让老师知道的。TL：这样吧，我让你猜，你每次猜一个数，我会告诉你比这个数大还是小。你快点猜出来，我马上就要去奶奶家吃饭去了。你以你的打字速度每1s可以提一个问题，但是由于该遭天杀的网络延迟。TL的回答要在1s之后才会传到你这里来。也就是说，只有当你提出了下一个问题之后，这个问题的答案才会告诉你。同时，由于TL心高气傲。如果你低估他拥有的模型数量，他就会生气。如果你低估了他K（1=K=100）次，他就不再陪你玩了。你最开始已经知道，TL的模型数量至少有1个，至多不超过N（1=N=105）个。下面是一个N=6时的可能的询问过程：2006年全国信息学冬令营讲座事件时间You：你有3个模型吧？1sTL：网络延迟，没反应……1sYou：你有5个吧？2sTL：你怕我像你一样，只有3个模型！！！（生气）2sYou：哦哦哦哦哦，那你有6个？3sTL：显然没有5个那么多。哪个像你那么有钱。3sYou：你有4个模型吧。4sTL：都说了没有5个，你还问有没有6个。4sYou：你肯定是有4个模型咯。5sTL：对对对，我有4个模型。傻瓜，猜这么久。5s你现在已经知道TL的模型数量不少于1个，不超过N个。并且知道TL生气K次之后就不会再陪你玩了，请你算算，最优询问策略在最坏情况下，至少需要多少秒才能问出具体的模型数量。把这道题目抽象一下，会发现就是在引言中所讲的猜数问题原型上加上了几个限制条件。本题是说：有一个被猜数X，是1到N的范围内的整数，你每次可以给出一个整数Y。你会在你问下一个问题之后得到你这个问题的回答，即X与Y的大小关系。并且如果你得到了K次XY的回答，游戏就结束，你要避免这种情况的发生。经过抽象，本题事实上就是本文要讨论的猜数问题原型加上了粗体字部分的限制条件。但是由于限制条件的出现，实在这道题看起来非常难以下手。我们以往做这类题时，依靠找规律或经验来猜测结论，然后再加以验证，这种办法在绝大部分情况下是适用，但是现在，我们需要系统来分析这道题目，以求得解答，那么让我们先从最简单的猜数问题看起。二、从最简单的问题说起基本猜数问题：被猜数X是1到N范围内的整数，每次你可以询问一个整数Y和X的大小关系。给出N，请问在最坏情况下至少需要几次才能保证猜出X。通常能够想到的方法就是基于二分的询问，这是依据经验得来的。具体上说就是：如果已知X在[L,R]之内，那么令2RLMidY，如果YX则可以确定X在[Mid+1,R]之内，YX则可以确定X在[L,Mid-1]之内，若Y=X则表示已经猜出来了。上面算法的最优性是显然的，因为每次都将区间尽量均分，使得最坏情况下，下一次需要处理的区间的大小尽可能的小。具体证明这里就略过。2006年全国信息学冬令营讲座需要注意的是，问题要求的是次数。那么需要询问的次数是不是简单的1log2LR，显然不是的。因为对于每次询问的回答有三种可能，即还存在X=Y的关系。用数学的语言描述，设f(i)表示询问i次询问能够处理长度为f(i)的区间，下图分析了f(i)应该满足的关系。这样，我们就得到了相应的递推式：可以从递推式中看到，由于有了X=Y的情况，12)(iif。不过我们仍然可以利用递推的方法来得到我们的算法：已知1)1(f，根据1)1(2)(ifif依次计算f(2),f(3)…，直到某个)(ansf满足Nansf)(，则答案为Ans。这个算法的时间复杂度)(AnsO的，由于f函数的增长比指数函数略快。所以可以知道)(log)(2NOAnsO。也许有些人会问了，这个算法有什么实际价值呢？对于这个简单的问题，用最开始的二分方法，统计从开始询问直到问出X值，一共询问了多少次就可以1)1(21)1()1()(ifififif当回答XY之后还剩下i-1次提问机会。能够处理长度为f(i-1)的区间。当回答XY之后还剩下i-1次提问机会。能够处理长度为f(i-1)的区间。当回答X=Y时，可以马上确定X的值。当回答为XY时，X可能出现的区间。当回答为XY时，X可能出现的区间。LRY当进行完了一次询问之后，就只剩下i-1次询问了。绿色区间的长度和红色区间的长度不能超过i-1次询问能够处理的范围。也就是说绿色区间和红色区间的长度最大也就是f(i-1)。2006年全国信息学冬令营讲座了。时间复杂度同样为)(log2NO。似乎递推算法完全没有必要。对于本题也许是如此，但是递推法相比简单的二分方法的最大优势就是它是通过数学具体分析，而不是依据经验或猜想得出的算法。所以递推法的可推广性更强，当问题变得复杂一些的时候，仍能适用。三、基本猜数问题的两个加强现在要直接解决原题仍然比较困难，我们不妨先来看看和原问题相关的两个基本猜数问题的加强：加强1：被猜数X是1到N范围内的整数，每次你可以询问一个整数Y和X的大小关系。同时若你得到了K次以上（含K次）XY的回答，那么你就失败了，你要避免这种情况的发生。给出N、K，问在最坏情况下需要几次询问才能保证猜出被猜数X。由于引入了限制条件：同时若你得到了K次以上（含K次）XY的回答，那么你就失败了。所以没有办法再用简单的二分来解决，那么就来尝试用递推的思路解决这道题目，由于多了一个变量k，所以需要二维递推。设),(jif表示用i次询问，在得到了j次以上XY回答后游戏就会结束的情况下，最大能够处理的区间长度。类似的，我们可以作出如下分析：所以可以得到),(jif的递推式为：1)1,1(),1(),(jifjifjif类似的可以得到算法：已知0),0(jf，0)0,(if，依次按照递推式，递推求解f。直到某个),(kansf，满足nkansf),(，则答案为Ans。这个算法的时间复杂度为K)AnsO（。由于),(jif的增长速度比组合函数jiC更快，所以算法当回答为XY时，X可能出现的区间。这时询问次数减少了一次，所以这段区间的长度最长是),1(jif。当回答为XY时，X可能出现的区间。这时不仅询问次数减少一次，而且还得到了一次XY的回答，所以这段区间的长度最长为)1,1(jif。LRY由上面的图例可以看出，),1(jifLY2006年全国信息学冬令营讲座的时间复杂度是很低的。上面的例子中，在求递推式的时候，我们是通过确定三种情况分别需要处理的区间长度，从而确定),(jif的整个区间长度。在这里需要强调一点的是，当我们把所有f函数的值都求出来之后，对于每个状态),(jif我们所需要采取的决策，也就是询问的数Y也已经确定了！对于本题，上面的图例显示Y左边至多只能有),1(jif个数，右边至多有)1,1(jif个数，由于),(1jifLR那我们不妨就令),1(jifLY，这样就能在任何情况下均满足条件。可以看出这里2RLY，也就是说询问的时候并不一定将整个区间均分，二分在这里并不适用。可以看出，这道题可以看作是本文开篇提出的问题的一部分，下面再来看基础猜数问题的另一种加强。加强2：被猜数X是1到N范围内的整数，每次你可以询问一个整数Y和X的大小关系。不同于普通猜数问题，本次提问的回答你不会马上得到，而是会在你下一次提出问题后才告诉你。也就是你每问一个问题之后，得到的回答是你上一次提问的答案。给出N，请问在最坏情况下至少需要几次才能保证猜出X？由于提问的答案不能马上获得，所以思考起来有一定的难度。但是仔细分析的话，还是能够用递推来解决这道题目。如同上题一样，我们也根据回答的三种情况来求得递推式，但是问题就是：当我们询问了一个Y之后，不会得到关于Y的任何信息。要得到这些信息我们必须再询问一个数Y’。显然，在我们什么也不知道的情况下，只能凭空询问，要么把Y’问在小于Y的区间，要么问在大于Y的区间，且只有当询问完之后，才知道X与Y的关系，才知道关于Y’的询问是不是多余和浪费。由于这里没有其他的限制条件，我们可以认为，Y’问在小于Y的区域和问在大于Y的区域是等价的。不妨设Y’问在了小于Y的区域。设)(if表示询问i次询问能够处理的最长区间长度。很容易就得到了一个简单的递推公式：Y’Y当回答为XY时，X可能出现的区间。这时询问次数只减少了一次，因为关于Y’的询问没有浪费，所以这段区间的长度最长是)1(if。当回答为XY时，X可能出现的区间。这时由于关于Y’的询问被浪费了，所以询问次数减少了2次，这段区间的长度最长为)2(if。LR2006年全国信息学冬令营讲座1)2()1()(ififif同时根据上图，通过类似上一道题的分析，可以知道：)1(ifLY，)2(ifLY。而对于题目要求求出的最少询问次数，类似的可以得到算法：已知0)1(,0)0(ff，根据1)2()1()(ififif依次计算f值，直到出现某个f值nansf)(，则Ans为所求的最少询问次数。下面来分析算法的时间复杂度，同前几题一样，这个算法的时间复杂度也和Ans有关，就为：)(AnsO。由于f函数的增长比Fibonacci数列更快，所以可以认为)(log)(log)(2NONOAnsO。上面就是我们利用递推法，通过系统的分析，解决两道由基础猜数问题变化、加强而来的题目的全过程。有这些基础，我们现在可以回到原问题的研究了。四、原问题的研究现在让我们回到原问题。事实上，如果将上面两个问题的限制条件合并，就得到了原问题。我们已经把上面两个问题用递推法完整的解决，下面来研究合并了之后的原问题。综合解决上面两道题目的经验，我们仍然尝试使用递推法来求解：设),(jif表示用i次询问机会，在得到了j次以上XY回答后游戏就会结束的情况下，最大能够处理的区间长度。由于本题的回答也是有“延迟”的，所以在询问了Y之后，我们必须“盲目”的询问一个Y’，以求获得Y的回答。类似上面的几题，可以做出如下分析：根据这个分析，我们可以很轻松的得到递推式：Y’Y当回答为XY时，X可能出现的区间。这时询问次数只减少了一次，因为关于Y’的询问没有浪费。同时由于得到的并不是XY的回答，j值无需减少，所以这段区间的长度最长是),1(jif。当回答为XY时，X可能出现的区间。这时由于关于Y’的询问被浪费了，所以询问次数减少了2次，同时得到了一次XY的回答，并且由于XY，所以肯定有XY’。也就是在可以预见的将来，还会得到一次XY的回答，j值应该减少2。所以这段区间的长度最长为)2,2(jif。LR2006年全国信息学冬令营讲座1)2,2(),1(),(jifjifjif这道题是不是就这样解决了呢？严谨的读者可能