算法合集之《一类猜数问题的研究》

一类猜数问题的研究长沙市雅礼中学龙凡猜数问题猜数问题是信息学竞赛中一种常见的类似博弈的问题。基本形式：存在一个被猜数X。每次可以猜一个数Y，之后会返回X和Y的关系，你要利用返回的信息来猜出X。本文着重讨论的一类猜数问题是：返回的信息是X和Y的大小关系。基本的猜数问题下面就是一个本文讨论范畴内的最基本的猜数问题：被猜数X是1到N范围内的整数，每次你可以询问一个整数Y和X的大小关系。给出N，请问在最坏情况下至少需要几次才能保证猜出X。上题应用大家熟悉的二分的思想可以轻松解决。上面我们总共耗费了3次询问。这只是作为一个二分询问的例子。对于此题，应用二分法，作适当的数学分析，就可以得到最少的询问次数为：基本的猜数问题设N=7,X=5。应用二分的思想询问：12345671.询问Y=42.得到XY3.询问Y=64.得到XY5.询问Y=56.得到X=Y)1(log2n问题的提出作为一类猜数问题中最基本的形式，固然是非常简单的。但很多其他的问题在这个“基本形式”上进行了一些扩充和加强，就变成了非常棘手的问题。下面就让我们来实际的看一看这类型的例子：问题的提出你和你的同学在网上进行猜数游戏，基本规则和普通的猜数游戏一样。你猜一个数Y，他告诉你，Y和他心中所想的数X的大小关系。你打字速度很快，每1s钟就可以问一个问题。由于网络有延迟的，所以你问的问题不能马上得到回答，而是要经过1s之后才会得到回答。同时你和同学约定，你要尽量避免得到XY的回答。（你可以认为，X是他的考试成绩之类的）当你累计得到第K次XY的回答的时候，你就输了。已知X是1到N之间的整数。现在给出N、K，请问最少要多少秒才能保证猜出X。问题的提出下面是一个N=6,K=3时的实例：询问回答时间1s2s3s4s5s上面的询问，总共用了5s。期间得到了一次XY的回答。K=3没有超过限制。Y=3Y=5Y=4Y=4Y=6X6X5X=4X3…初步分析我们现在的问题并不是如何猜，而是在最坏的情况下至少要多少秒才能猜出X来。本题沿用二分的老思路是行不通的。可以看出，虽然仅仅是在基本猜数问题上进行了些许加强，就成了一个非常棘手的问题。为了解决这个问题，让我们重新从最原始的猜数问题开始分析。123当N=3，K=1并且X=3时。询问Y=2，必然得到XY回答。前面我们是通过二分的方法来解决此题的。至于“二分”这个思路的来源，更多的是源自猜测、及平时做题的经验。下面就来系统的分析为什么“二分”是正确的。通过分析，希望能找到一个更具有普遍性的方法解决前面的题目。让我们尝试用递推的方法来分析问题。被猜数X是1到N范围内的整数，每次你可以询问一个整数Y和X的大小关系。给出N，请问在最坏情况下至少需要几次才能保证猜出X。再看基本猜数问题再看基本猜数问题设f(i)表示i次询问最大能够处理的区间长度。即若N=f(i)，则只需要i次就可以猜出X。根据上面定义，若f(j)≥N。且f(j-1)N则可以知道j即为题目所求的至少询问次数。每询问一个Y，只可能得到三种不同的回答，我们就从这三种不同的回答入手来分析问题。再看基本猜数问题询问一个值Y。若回答是X=Y，即游戏马上中止。XY时，为了要在剩下的I-1次询问中得到答案，大于Y的区域长度不能超过f(i-1)。XY时，小于Y的区域长度不能超过f(i-1)。Y小于Y的区域大于Y的区域1f(i-1)f(i-1)1)1(2)(ifif再看基本猜数问题上面分析直观的说明了二分的正确性。f(i)=2f(i-1)+1=f(i)=2i-1应用递推的方法间接的证明了前面的结论，即最少询问的次数为：更重要的是：对于这类试题来说，上面这种应用递推的分析问题的方法具有很强的推广性。)1(log2n二次分析通过上面的分析，基本的猜数问题已经完整的解决了。现在回到原题的研究。现在直接分析原题仍然有点困难，注意到原题相比基本猜数问题有两个加强：不妨先把这道题目拆开，分部解决。1.累计获得K次XY的答案就游戏结束。2.本次的回答要在下一个提问之后获得。猜数问题的加强被猜数X是1到N范围内的整数，每次你可以询问一个整数Y和X的大小关系。附加上条件：累计获得K次XY的答案就游戏结束。给出N、K，请问在最坏的情况下至少需要几次询问才能保证猜出X。对于这个问题，可以借鉴前面的经验，应用递推的方法来求解。被猜数X是1到N范围内的整数，每次你可以询问一个整数Y和X的大小关系。你要尽量避免询问比X小的Y值，因为累计获得K次XY的答案就游戏结束。给出N、K，问在最坏情况下至少需要询问几次才能保证猜出X。猜数问题的加强类似的，我们设f(i,j)表示用i次询问，在累计j次XY的回答就游戏结束的情况下，最大能处理的区间长度。如果我们能够快速求出f，问题也就容易解决了。找到最小的数Ans，满足f(Ans,k)≥N，f(Ans-1,K)N。则答案就为Ans。和上一题类似，可以根据三种不同的回答，即：X=Y，XY，XY分别进行讨论来构造递推公式。1)1,1(),1(),(jifjifjif猜数问题的加强X=Y的情况最简单,长度为1。回答为XY，还剩下i-1次机会询问，所以小于Y的区域长度最多为f(i-1,j)。回答为XY，还剩下i-1次机会询问，并且我们得到了一次“XY”的回答，所以j值减少1，大于Y的区域长度最多为f(i-1,j-1)。Y小于Y的区域大于Y的区域f(i-1,j)f(i-1,j-1)1猜数问题的加强根据这个递推式，依次将f全部计算出来，直到存在一个f(Ans,k)≥N，就结束。所以总时间复杂度为O(AnsK)。这样此题就被我们解决了。但是如果我们不是要求询问次数，而是希望得到每一步询问的策略，该怎么办呢？为了让大家深入理解递推算法，我们在这里做进一步分析。猜数问题的加强仔细看上图。事实上询问的值Y已经提示出来了，Y是第f(i-1,j)+1个可能值。在还剩下i次询问，并累计j次XY回答就游戏结束的情况下，若X可能的出现区间是[L,R]，则Y=L+f(i-1,j)。下面是一个简单的例子：Y小于Y的区域大于Y的区域f(i-1,j)f(i-1,j-1)15≤f(3,2)7≤f(3,3)2≤f(2,1)3≤f(2,2)48例子上表是已经计算好的f值。若N=6，K=2，查上表可以得出需要3次询问才能保证猜出X。第一次询问Y=4。若N=13,K=3，查上表可以得出需要4次询问才能保证猜出X。第一次询问Y=8。f(i,j)i=1i=2i=3i=4…………13216133741410j=3j=2j=1无论得到什么回答，都能解决！被猜数X是1到N范围内的整数，你可以询问一个整数Y和X的大小关系。与普通猜数问题不同，提问的回答要在下一次提问之后才能获得。给出N，问最坏情况下需要多少次询问才能猜出X。由基本的猜数问题。附加上条件：本次的回答要在下一个提问之后获得。本题最大的难点是：当询问了一个值Y之后，下一次询问之前我们得不到任何的讯息，必须盲目的再询问一个值Y’。其实本题仍然可以用递推的思想解决。猜数问题的加强2Y小于Y的区域大于Y的区域猜数问题的加强2我们设f(i)表示i次询问能够处理的区间最大的长度。则可以知道若f(ans)≥N，f(ans-1)N则可知Ans即为所求的最少的询问次数。由于没有其他条件的限制，大于Y和小于Y两个区域是等价的。不妨设我们将Y’询问在了小于Y的区域：猜数问题的加强2我们先询问Y，然后再询问Y’。这时才能得到关于Y的回答。若XY，则关于Y’的询问被浪费了。还剩下i-2次询问机会。大于Y的区域的最大为f(i-2)。若XY，则Y’的询问没有被浪费，还剩下i-1次询问机会。小于Y的区域最大为f(i-1)。)1(ifY小于Y的区域小于Y的区域Y’大于Y的区域)2(if1)2()1()(ififif原问题的解决上题的时间复杂度是O(Ans)。至此两个加强问题，已经被分别解决。有了解决这两个基础问题的过程，再回来看原问题就比较容易了。被猜数X是1到N范围内的整数，你可以询问一个整数Y和X的大小关系。与普通猜数问题不同，提问的回答要在下一次提问之后才能获得。你要尽量避免询问比X小的Y值，因为累计获得K次XY的答案就游戏结束。给出N、K，问在最坏情况下至少需要询问几次才能保证猜出X。原问题的解决设f(i,j)表示用i次询问，在累计j次获得XY的回答就游戏结束的情况下，最大能处理的区间长度。先询问Y，再Y’。将Y’询问在小于Y的区域。若XY，则Y’的询问浪费了，询问次数减二，且会获得两次XY的回答，j值减二，所以大于Y的区域最长为f(i-2,j-2)。若XY，询问次数减一。不会得到XY的回答，所以j不变。小于Y的区域最长为f(i-1,j)。),1(jifY小于Y的区域小于Y的区域Y’大于Y的区域)2,2(jif原问题的解决做上面的分析之后是不是就足够了呢？注意到由于有了另一个限制条件，使得小于Y的区域和大于Y的区域不再等价，我们必须讨论Y’询问在大于Y的区域时的情况。将Y’询问在大于Y的区域。若XY，Y’的询问被浪费了，询问次数减少二。且不会获得XY的回答，j值不变。小于Y的区域最长长度为f(i-2,j)。若XY，询问次数减少1。得到了XY的回答，j减少1。大于Y的区域最长为f(i-1,j-1)。)1,1(jifY大于Y的区域大于Y的区域Y’小于Y的区域),2(jif原问题的解决综合上面，可以得出动态规划公式：边界条件为：1),2()1,1(1)2,2(),1(max),(jifjifjifjifjif0),1(0),0(0)0,(jfjfif原问题的解决算法的框架就是利用得出的动态规划转移公式，依次计算f值。直到有一个Ans满足f(ans,k)≥N,f(ans-1,k)N。则所求的最少次数为Ans。这个算法的总时间复杂度为O(AnsK)，由于f函数的增长非常快，所以实际运行效果很理想。至此我们完整的解决了文初的问题。总结同类的试题还有很多，这里只是列举了其中的典型。在本文里主要介绍的是如何使用递推、动态规划的方法来解决同类猜数问题。这些算法应用在猜数问题上，能够更加深入的、系统的分析问题。不仅仅局限于同类问题，只要我们学会如何抛开繁杂的题目描述，从数学模型的角度系统的来分析问题。任何难题都能迎刃而解。