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

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

1、一类猜数问题的研究长沙市雅礼中学龙凡猜数问题猜数问题是信息学竞赛中一种常见的类似博弈的问题。基本形式：存在一个被猜数X。每次可以猜一个数Y，之后会返回X和Y的关系，你要利用返回的信息来猜出X。本文着重讨论的一类猜数问题是：返回的信息是X和Y的大小关系。基本的猜数问题下面就是一个本文讨论范畴内的最基本的猜数问题：被猜数X是1到N范围内的整数，每次你可以询问一个整数Y和X的大小关系。给出N，请问在最坏情况下至少需要几次才能保证猜出X。上题应用大家熟悉的二分的思想可以轻松解决。上面我们总共耗费了3次询问。这只是作为一个二分询问的例子。对于此题，应用二分法，作适当

2、的数学分析，就可以得到最少的询问次数为：基本的猜数问题设N=7,X=5。应用二分的思想询问：12345671.询问Y=42.得到X>Y3.询问Y=64.得到X

3、络有延迟的，所以你问的问题不能马上得到回答，而是要经过1s之后才会得到回答。同时你和同学约定，你要尽量避免得到X>Y的回答。（你可以认为，X是他的考试成绩之类的）当你累计得到第K次X>Y的回答的时候，你就输了。已知X是1到N之间的整数。现在给出N、K，请问最少要多少秒才能保证猜出X。问题的提出下面是一个N=6,K=3时的实例：询问回答时间1s2s3s4s5s上面的询问，总共用了5s。期间得到了一次X>Y的回答。K=3没有超过限制。Y=3Y=5Y=4Y=4Y=6X<6X<5X=4X>3…初步分析我们现在的问题并不是如何猜，而是在最坏的情况下至少要多少秒才能

4、猜出X来。本题沿用二分的老思路是行不通的。可以看出，虽然仅仅是在基本猜数问题上进行了些许加强，就成了一个非常棘手的问题。为了解决这个问题，让我们重新从最原始的猜数问题开始分析。123当N=3，K=1并且X=3时。询问Y=2，必然得到X>Y回答。不可以二分！前面我们是通过二分的方法来解决此题的。至于“二分”这个思路的来源，更多的是源自猜测、及平时做题的经验。下面就来系统的分析为什么“二分”是正确的。通过分析，希望能找到一个更具有普遍性的方法解决前面的题目。让我们尝试用递推的方法来分析问题。被猜数X是1到N范围内的整数，每次你可以询问一个整数Y和X的大小关系。

5、给出N，请问在最坏情况下至少需要几次才能保证猜出X。再看基本猜数问题再看基本猜数问题设f(i)表示i次询问最大能够处理的区间长度。即若N=f(i)，则只需要i次就可以猜出X。根据上面定义，若f(j)≥N。且f(j-1)Y时，为了要在剩下的I-1次询问中得到答案，大于Y的区域长度不能超过f(i-1)。X

6、域1f(i-1)f(i-1)再看基本猜数问题上面分析直观的说明了二分的正确性。f(i)=2f(i-1)+1=>f(i)=2i-1应用递推的方法间接的证明了前面的结论，即最少询问的次数为：更重要的是：对于这类试题来说，上面这种应用递推的分析问题的方法具有很强的推广性。二次分析通过上面的分析，基本的猜数问题已经完整的解决了。现在回到原题的研究。现在直接分析原题仍然有点困难，注意到原题相比基本猜数问题有两个加强：不妨先把这道题目拆开，分部解决。1.累计获得K次X>Y的答案就游戏结束。2.本次的回答要在下一个提问之后获得。猜数问题的加强被猜数X是1到N范围内的整数

7、，每次你可以询问一个整数Y和X的大小关系。附加上条件：累计获得K次X>Y的答案就游戏结束。给出N、K，请问在最坏的情况下至少需要几次询问才能保证猜出X。对于这个问题，可以借鉴前面的经验，应用递推的方法来求解。被猜数X是1到N范围内的整数，每次你可以询问一个整数Y和X的大小关系。你要尽量避免询问比X小的Y值，因为累计获得K次X>Y的答案就游戏结束。给出N、K，问在最坏情况下至少需要询问几次才能保证猜出X。猜数问题的加强类似的，我们设f(i,j)表示用i次询问，在累计j次X>Y的回答就游戏结束的情况下，最大能处理的区间长度。如果我们能够快速求出f，问题也就容易

8、解决了。找到最小的数Ans，满足f(Ans,k)≥N，f(Ans-