下载文档原格式
猜数问题的研究上海市复旦附中高二(8) 张宁摘要：在逻辑推理中有一类比较特殊的问题——“思维嵌套”问题，即在C的脑海中要考虑B是如何思考A的想法。
对于这种问题通常非常抽象，考虑情况又十分繁多，思想极其复杂，用一般方法分析效果极差。
本文以一个典型的“思维嵌套”问题——猜数问题为出发点，用一种新的方法从问题本质入手分析，很好的解决了问题，并阐述了新思路的优越性。
由本质入手分析，避免了表面上的“思维嵌套”，且总结出了许多结论，使得解决问题的效率大幅度上升。
在新思路的指引下将原问题向更普遍的情形推广，虽然问题变得更为繁琐复杂，但是由于把握住问题的命脉，有效地解决了问题。
关键字：推理，思维嵌套，终结情形，一类情形，二类情形，分组正文：一、问题原形问题描述：一位逻辑学教授有三名非常善于推理且精于心算的学生A，B和C。
有一天,教授给他们三人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个大于0的整数，且某两个数的和等于第三个。
于是，每个学生都能看见贴在另外两个同学头上的整数，但却看不见自己的数。
教授轮流向A，B和C发问：是否能够猜出自己头上的数。
经过若干次的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误的报了出来。
我们的问题就是：证明是否一定有人能够猜出自己头上的数，若有人能够猜出，则计算最早在第几次提问时有人先猜出头上的数，分析整个推理的过程，并总结出结论。
我们先分析一个简单的例子，观察每个人是如何进行推理的。
假设A，B和C三人，头上的数分别是1，2和3。
1)先问A这时，A能看见B，C两人头上的数分别是2，3。
A会发现自己头上只可能为3+2=5，或者3-2=1。
可到底是1还是5，A无法判断，所以只能回答“不能”。
2)再问BB会发现自己头上只可能为3+1=4，或者3-1=2。
可到底是2还是4，B只能从A的回答中入手分析：（以下为B脑中的分析）1.如果自己头上是2。
Python常见猜数字之类的OJ题目近年来，随着人工智能和编程技术的飞速发展，越来越多的人开始学习编程语言Python。
作为一门简洁、易学并且功能强大的语言，Python在各个领域得到了广泛的应用，尤其是在算法和编程竞赛中。
猜数字是一类经典的编程题目，常出现在各种在线编程竞赛（OJ）中。
在这篇文章中，我们将深入探讨Python常见的猜数字之类的OJ题目，从简单到复杂，由浅入深地分析解决方案，并结合个人观点和理解进行总结。
1. 简单题目：猜数字游戏让我们从一个简单的猜数字游戏开始。
在这个游戏中，计算机会随机生成一个1到100之间的整数，然后要求玩家通过输入不同的数字来猜测这个随机数。
如果玩家猜对了，游戏结束并显示“恭喜你，猜对了！”；如果猜错了，计算机会提示玩家猜的数字是偏大还是偏小，并让玩家继续猜测，直到猜对为止。
在Python中，我们可以使用random模块来生成随机数，再结合条件判断和循环语句来完成这个游戏。
我们需要导入random模块：```pythonimport random```我们可以使用random.randint(a, b)函数来生成a和b之间的随机整数。
我们可以使用while循环来反复询问玩家猜测的数字，并通过if-else语句来判断玩家的输入是否与随机数相等。
```pythonnumber = random.randint(1, 100)guess = int(input("请输入你猜的数字："))while guess != number:if guess > number:print("猜的数字偏大了！")else:print("猜的数字偏小了！")guess = int(input("请再次输入你猜的数字："))print("恭喜你，猜对了！")```通过以上代码，我们实现了一个基本的猜数字游戏。
一类猜数游戏的设计有这样一则巧算年龄的趣味数学题.今年67岁的已经退休的陈老师对小王说:”你将你的岁数与我的岁数相乘,告诉我积的末两位数,我就可以立即猜出你的年龄.”小王告诉陈老师这末两位数是38,陈老师笑着说:”你今年14岁了.”正好猜对.陈老师的方法是将小王告诉的数38 (]⨯)乘以3,再取末两1467=[938位数14(]⨯)即可报出小王的年龄数.38=[1143以上问题实际上即猜数游戏.因201⨯,而数201与任何两位数67=3m的乘积,即m67,其末两位数恰恰是数m本身.若改变计算次序, ⨯3⨯⨯⨯m此数的末两位数,即m,只与m67的末两位数有关,而与其余各67⨯3位数无关。
比如,题中小王14岁, 11467=14⨯⨯⨯,两938==383,28149383.种算法的末两位数都是14----小王的岁数.一般地,若两数之积的末两位数是01,就可由此设计出一种猜两位数的游戏,比如67=3201⨯=⨯,...⨯=7301,.......43,....3501167以第三个式子为例,游戏人故弄玄虚当众宣布:无论任何人,你心里任意默记一个数,不要说出来,你只要告诉我这个数与43的乘积的末两位数,我就可以立即猜出你心想的这个数是几!万无一失,游戏人只需将对方告诉的数乘以7, 报出积的末两位数就是对方心记的那个数.比如某人心想的数是32,运算过程为[1343对方告诉763276-⨯,]--=[5776游戏人报出3232---==⨯]若两数之积的末三位数是001,比如,.....143=⨯=⨯即可用来设计猜三位数的数710012001,3667学游戏,以第一式为例, 无论任何人,你心里任意默记一个三位数,然后说出这个数与143的乘积的末三位数,我就可以立即猜出那想的数,比如那心里默记的数是879,你立即计算]143=879⨯,告诉我末三位数(框出125697[者)是679,我计算,]⨯报出框出的数是879,就是你想的数.679=8797[4请同学们详细说出这种游戏的数学原理,以下问题供同学们思考,由1⨯能否设计出一种猜两位400=3133-数的数学游戏?答案:让对方默记的数乘以133,告诉得数得末两位数,游戏人把这个数乘以3,取积数的末两位数的补数,(一个两位数的补数等于100减去该数所得的差)比如你心里默记的数是89,作运算:3[111,]37=⨯报出=-89[37]100118133=11⨯----对方告诉37,89 89,就是你心里记的数.本文发表在<中学生学习报(初中版)> 1995年7月3日第3版。
数学的推理游戏根据已知信息推断未知数字数学是一门精确而有趣的学科，其中推理是数学的重要组成部分。
数学的推理游戏旨在通过已知信息来推断未知数字，训练学生的逻辑思维和解决问题的能力。
在这篇文章中，我们将探讨数学的推理游戏，并介绍一些常见的例子。
一、猜数字游戏猜数字游戏是数学推理游戏中最常见的一种。
该游戏的玩法简单，一个人选择一个未知的数字，其他人通过猜测的方式逐步缩小范围，并根据已知信息来推断出这个未知数字。
例如，假设一个人选择了一个介于1到100之间的数字，其他人可以问一些问题，如“这个数字是偶数吗？”、“这个数字是大于50的吗？”等等，通过迭代的过程最终找到这个未知数字。
二、数独游戏数独是一种常见的推理游戏，通过逻辑推理填充9x9的网格，其中每一行、每一列以及每个小的3x3的方格内都包含了1到9的数字。
数独的难点在于玩家需要通过已知数字来推断出其他未知数字的位置。
数独游戏不仅能够锻炼思维能力，还能培养耐心和坚持不懈的品质。
三、逻辑推理题逻辑推理题是数学推理游戏中的经典题型。
这些题目通常描述一些情况或者条件，玩家需要通过已知信息来推断出结论。
例如，有一道经典的逻辑推理题：“在一排连续的五个整数中，如果第一个数字是2，最后一个数字是10，且每个数字与相邻数字的差为2，那么这五个整数分别是多少？”玩家通过逻辑推理可以解得这五个整数分别为2、4、6、8和10。
四、解方程解方程是数学推理游戏中的关键步骤之一。
通过给定的方程式，玩家需要通过代数推理来找到未知数的值。
例如，对于方程式“2x + 5 = 15”，玩家需要通过逆向运算得出x的值为5。
通过数学的推理游戏，不仅可以提高学生的数学能力，还能够培养他们的逻辑思维和解决问题的能力。
这些游戏不仅是学习数学的工具，也是一种有趣和富有挑战性的娱乐方式。
总结：数学的推理游戏是一种锻炼逻辑思维和解决问题能力的有趣方式。
通过猜数字游戏、数独、逻辑推理题以及解方程等活动，学生可以培养自己的数学思维能力，并且加深对数学的理解和兴趣。
一类猜数问题的研究长沙市雅礼中学龙凡【摘要】猜数问题是信息学竞赛中一种常见的类似博弈的问题。
其中部分的问题是给出猜的数与被猜数之间的大小关系作为回答信息。
作为信息学竞赛中一类经常出现的问题，很有研究的意义与价值。
本文重点对这类问题的不同形式的解法进行讨论与研究。
本文先提出了一个看似复杂、棘手的问题，然后慢慢通过分析剖析其本质，提出一个行之有效的解法，并在此基础上对其他相关的问题展开讨论。
【关键字】二分法、递推法、数学模型、动态规划【引言】信息学竞赛中常常看到诸如此类的问题：现在有一个数X，是1~N之内的。
你每次可以猜一个数Y，然后会根据你提供的Y与X的大小关系，给出X<Y，X=Y，X>Y三种回答。
你要用尽量少的询问次数把X猜出来，也就是得到X=Y 的回答。
那么在最坏情况下至少需要多少次呢？有很多问题都是在这个基础上进行了扩充和加强，从而变成了棘手的问题，但是它们的本质是相同的。
所以对这类问题的研究，并进行一定的整理和归纳还是很有必要的。
【正文】一、问题的提出引言中已经对本文要讨论的问题类型作了基本定义，下面就来看一道如上文所说被“扩充和加强了的”猜数问题。
模型王子：TL家有无数个高达机器人的模型，这已经不是一个秘密。
终于有一天，你忍不住了，问TL：你家到底有多少个模型呢？TL：就是不告诉你 。
You：说吧说吧，别保密了咯，我不会让老师知道的。
TL：这样吧，我让你猜，你每次猜一个数，我会告诉你比这个数大还是小。
你快点猜出来，我马上就要去奶奶家吃饭去了。
你以你的打字速度每1s可以提一个问题，但是由于该遭天杀的网络延迟。
TL的回答要在1s之后才会传到你这里来。
也就是说，只有当你提出了下一个问题之后，这个问题的答案才会告诉你。
同时，由于TL心高气傲。
如果你低估他拥有的模型数量，他就会生气。
如果你低估了他K（1<=K<=100）次，他就不再陪你玩了。
你最开始已经知道，TL 的模型数量至少有1个，至多不超过N（1<=N<=105）个。
数字之谜破解挑战赛探索算式中隐藏的规律算式，是数学领域中最基础的表达形式之一。
当我们面对一串数字和运算符号时，总是想要探索其中的规律，从而揭开数字之谜。
在这篇文章中，我们将探索算式中隐藏的规律，挑战破解数字之谜。
数字，是数学的基本单位。
它们以特定的形式组成了算式，我们需要通过观察和推理，找出其中的规律。
让我们进行一次数字之谜的挑战吧！以下是一组算式：1 + 1 = 22 + 2 = 43 + 3 = 64 + 4 = 8通过观察这组算式，我们很容易发现每个算式中，两个相同的数字相加的结果是什么：1 + 1 = 2，2 + 2 = 4，3 + 3 = 6，4 + 4 = 8。
看起来，这是一个很简单的规律。
然而，不同的算式中，隐藏了不同的规律。
让我们继续挑战！5 + 5 = ?6 + 6 = ?7 + 7 = ?8 + 8 = ?对于这组算式，我们需要找出两个相同数字相加的结果，并填入问号中。
通过观察，我们可以发现每个算式中的两个数字相等，那么答案就是这个相同的数字的两倍。
因此，5 + 5 = 10，6 + 6 = 12，7 + 7 = 14，8 + 8 = 16。
现在，让我们进一步挑战数字之谜！9 + 9 = ?10 + 10 = ?11 + 11 = ?12 + 12 = ?这组算式中，数字的范围扩大了，我们需要找出规律，填入问号中。
通过观察，我们可以发现每个算式中的两个数字，是递增的并且相等。
那么答案就是递增数字的两倍。
因此，9 + 9 = 18，10 + 10 = 20，11 + 11 = 22，12 + 12 = 24。
通过以上的例子，我们可以看出，算式中隐藏的规律可能千变万化，我们需要观察和推理，才能破解数字之谜。
下面，让我们尝试一些更具挑战性的算式。
20 + 5 = ?30 + 8 = ?40 + 11 = ?50 + 14 = ?这组算式中，我们需要找到两个数字之间的规律，继续挑战数字之谜。
数字的猜测与推理数学问题的解决方法数字的猜测与推理：数学问题的解决方法在数学领域中，数字的猜测与推理是非常重要的。
通过对数字的推断和推理，我们能够解决各种数学问题。
本文将介绍一些在解决数学问题时常用的猜测和推理方法。
一、数列推理数列是数学中常见的一类问题，通过观察数列中数字的规律，我们可以猜测和推理出下一个数字。
其中一种常见的数列是等差数列，每个数字与它前面的数字之间的差值都是相等的。
我们可以通过计算前几个数字的差值，来得出下一个数字。
例如，给定等差数列1, 4, 7, 10, 13，我们可以观察到每个数字之间的差值都是3。
因此，我们可以推断下一个数字是16，因为13 + 3 = 16。
除了等差数列，还有等比数列等其他类型的数列，它们都有自己特定的规律和推理方法。
通过观察和分析数列中的数字，我们能够猜测出数列的规律，从而推理出下一个数字。
二、代数推理在代数中，我们常常需要通过猜测和推理来求解方程。
通过将方程中的未知数代入，我们可以逐步推导出正确的答案。
例如，给定方程3x + 5 = 20，我们可以通过猜测并代入不同的x值来解方程。
当我们将x赋值为5时，3x + 5 = 3 * 5 + 5 = 20满足方程。
因此，我们可以得出x = 5。
代数推理也经常用于解决更加复杂的方程和问题。
通过仔细观察和推理，我们能够找到合适的策略和方法来解决数学难题。
三、概率推理概率是数学中的一个重要概念，通过对事件的概率进行猜测和推理，我们可以解决各种概率问题。
例如，假设一个袋子里有3个红球和2个蓝球，我们从中随机取出一个球。
我们可以猜测和推理袋子中取出红球的概率。
由于袋子中总共有5个球，其中3个红球，所以红球的概率为3/5。
概率推理在解决实际问题时也非常有用。
通过对问题的分析和推理，我们可以得出合理的概率猜测，从而解决复杂的概率问题。
四、逻辑推理逻辑推理是一种通过分析和推理形式、结构和关系来解决问题的方法。
逻辑推理在数学中起着至关重要的作用，尤其在解决证明问题时。
一类猜数问题的研究长沙市雅礼中学龙凡【摘要】猜数问题是信息学竞赛中一种常见的类似博弈的问题。
其中部分的问题是给出猜的数与被猜数之间的大小关系作为回答信息。
作为信息学竞赛中一类经常出现的问题，很有研究的意义与价值。
本文重点对这类问题的不同形式的解法进行讨论与研究。
本文先提出了一个看似复杂、棘手的问题，然后慢慢通过分析剖析其本质，提出一个行之有效的解法，并在此基础上对其他相关的问题展开讨论。
【关键字】二分法、递推法、数学模型、动态规划【引言】信息学竞赛中常常看到诸如此类的问题：现在有一个数X，是1~N之内的。
你每次可以猜一个数Y，然后会根据你提供的Y与X的大小关系，给出X<Y，X=Y，X>Y三种回答。
你要用尽量少的询问次数把X猜出来，也就是得到X=Y 的回答。
那么在最坏情况下至少需要多少次呢？有很多问题都是在这个基础上进行了扩充和加强，从而变成了棘手的问题，但是它们的本质是相同的。
所以对这类问题的研究，并进行一定的整理和归纳还是很有必要的。
【正文】一、问题的提出引言中已经对本文要讨论的问题类型作了基本定义，下面就来看一道如上文所说被“扩充和加强了的”猜数问题。
模型王子：TL家有无数个高达机器人的模型，这已经不是一个秘密。
终于有一天，你忍不住了，问TL：你家到底有多少个模型呢？TL：就是不告诉你 。
You：说吧说吧，别保密了咯，我不会让老师知道的。
TL：这样吧，我让你猜，你每次猜一个数，我会告诉你比这个数大还是小。
你快点猜出来，我马上就要去奶奶家吃饭去了。
你以你的打字速度每1s可以提一个问题，但是由于该遭天杀的网络延迟。
TL的回答要在1s之后才会传到你这里来。
也就是说，只有当你提出了下一个问题之后，这个问题的答案才会告诉你。
同时，由于TL心高气傲。
如果你低估他拥有的模型数量，他就会生气。
如果你低估了他K（1<=K<=100）次，他就不再陪你玩了。
你最开始已经知道，TL 的模型数量至少有1个，至多不超过N（1<=N<=105）个。
下面是一个N=6时的可在线代理|网页代理|代理网页|在线代理|网页代理|代理网页| 能的询问过程：事件时间 You ：你有3个模型吧？1s TL ：网络延迟，没反应……1s You ：你有5个吧？2s TL ：你怕我像你一样，只有3个模型！！！（生气）2s You ：哦哦哦哦哦，那你有6个？3s TL ：显然没有5个那么多。
哪个像你那么有钱 。
3s You ：你有4个模型吧。
4s TL ：都说了没有5个，你还问有没有6个。
4s You ：你肯定是有4个模型咯。
5s TL ：对对对，我有4个模型。
傻瓜，猜这么久。
5s你现在已经知道TL 的模型数量不少于1个，不超过N 个。
并且知道TL 生气K 次之后就不会再陪你玩了，请你算算，最优询问策略在最坏情况下，至少需要多少秒才能问出具体的模型数量。
把这道题目抽象一下，会发现就是在引言中所讲的猜数问题原型上加上了几个限制条件。
本题是说：有一个被猜数X ，是1到N 的范围内的整数，你每次可以给出一个整数Y 。
你会在你问下一个问题之后得到你这个问题的回答，即X 与Y 的大小关系。
并且如果你得到了K 次X<Y 的回答，游戏就结束，你要避免这种情况的发生。
经过抽象，本题事实上就是本文要讨论的猜数问题原型加上了粗体字部分的限制条件。
但是由于限制条件的出现，实在这道题看起来非常难以下手。
我们以往做这类题时，依靠找规律或经验来猜测结论，然后再加以验证，这种办法在绝大部分情况下是适用，但是现在，我们需要系统来分析这道题目，以求得解答，那么让我们先从最简单的猜数问题看起。
二、 从最简单的问题说起基本猜数问题：被猜数X 是1到N 范围内的整数，每次你可以询问一个整数Y 和X 的大小关系。
给出N ，请问在最坏情况下至少需要几次才能保证猜出X 。
通常能够想到的方法就是基于二分的询问，这是依据经验得来的。
具体上说就是：如果已知X 在[L,R]之内，那么令⎥⎦⎥⎢⎣⎢+==2R L Mid Y ，如果Y<X 则可以确定X 在[Mid+1,R]之内，Y>X 则可以确定X 在[L,Mid-1]之内，若Y=X 则表示已经猜出来了。
在线代理|网页代理|代理网页| 上面算法的最优性是显然的，因为每次都将区间尽量均分，使得最坏情况下，下一次需要处理的区间的大小尽可能的小。
具体证明这里就略过。
需要注意的是，问题要求的是次数。
那么需要询问的次数是不是简单的()⎡⎤1log 2+-L R ，显然不是的。
因为对于每次询问的回答有三种可能，即还存在X=Y 的关系。
用数学的语言描述，设f(i)表示询问i 次询问能够处理长度为f(i)的区间，下图分析了f(i)应该满足的关系。
这样，我们就得到了相应的递推式：可以从递推式中看到，由于有了X=Y 的情况，12)(-≠i i f 。
不过我们仍然可以利用递推的方法来得到我们的算法：已知1)1(=f ，根据1)1(2)(+-=i f i f 依次计算f(2),f(3)…，直到某个)(ans f 满足N ans f ≥)(，则答案为Ans 。
这个算法的时间复杂度)(Ans O 的，由于f 函数的增长比指数函数略快。
所以可以知道)(log )(2N O Ans O =。
1)1(21)1()1()(+-=+-+-=i f i f i f i f当回答X>Y 之后还剩下i-1次提问机会。
能够处理长度为f(i-1)的区间。
当回答X<Y之后还剩下i-1次提问机会。
能够处理长度为f(i-1)的区间。
当回答X=Y 时，可以马上确定X 的值。
当回答为X<Y 时，X 可能出现的区间。
当回答为X>Y 时，X 可能出现的区间。
L RY 当进行完了一次询问之后，就只剩下i-1次询问了。
绿色区间的长度和红色区间的长度不能超过i-1次询问能够处理的范围。
也就是说绿色区间和红色区间的长度最大也就是f(i-1)。
在线代理|网页代理|代理网页| 也许有些人会问了，这个算法有什么实际价值呢？对于这个简单的问题，用最开始的二分方法，统计从开始询问直到问出X 值，一共询问了多少次就可以了。
时间复杂度同样为)(log 2N O 。
似乎递推算法完全没有必要。
对于本题也许是如此，但是递推法相比简单的二分方法的最大优势就是它是通过数学具体分析，而不是依据经验或猜想得出的算法。
所以递推法的可推广性更强，当问题变得复杂一些的时候，仍能适用。
三、 基本猜数问题的两个加强现在要直接解决原题仍然比较困难，我们不妨先来看看和原问题相关的两个基本猜数问题的加强：加强1：被猜数X 是1到N 范围内的整数，每次你可以询问一个整数Y 和X 的大小关系。
同时若你得到了K 次以上（含K 次）X>Y 的回答，那么你就失败了，你要避免这种情况的发生。
给出N 、K ，问在最坏情况下需要几次询问才能保证猜出被猜数X 。
由于引入了限制条件：同时若你得到了K 次以上（含K 次）X>Y 的回答，那么你就失败了。
所以没有办法再用简单的二分来解决，那么就来尝试用递推的思路解决这道题目，由于多了一个变量k ，所以需要二维递推。
设),(j i f 表示用i 次询问，在得到了j 次以上X>Y 回答后游戏就会结束的情况下，最大能够处理的区间长度。
类似的，我们可以作出如下分析：所以可以得到),(j i f 的递推式为：1)1,1(),1(),(+--+-=j i f j i f j i f类似的可以得到算法：已知0),0(=j f ，0)0,(=i f，依次按照递推式，递推当回答为X<Y 时，X 可能出现的区间。
这时询问次数减少了一次，所以这段区间的长度最长是),1(j i f -。
当回答为X>Y 时，X 可能出现的区间。
这时不仅询问次数减少一次，而且还得到了一次X>Y 的回答，所以这段区间的长度最长为)1,1(--j i f 。
L R Y 由上面的图例可以看出，),1(j i f L Y -+=在线代理|网页代理|代理网页| 求解f 。
直到某个),(k ans f ，满足n k ans f ≥),(，则答案为Ans 。
这个算法的时间复杂度为K)Ans O ⨯（。
由于),(j i f 的增长速度比组合函数j i C 更快，所以算法的时间复杂度是很低的。
上面的例子中，在求递推式的时候，我们是通过确定三种情况分别需要处理的区间长度，从而确定),(j i f 的整个区间长度。
在这里需要强调一点的是，当我们把所有f 函数的值都求出来之后，对于每个状态),(j i f 我们所需要采取的决策，也就是询问的数Y 也已经确定了！对于本题，上面的图例显示Y 左边至多只能有),1(j i f -个数，右边至多有)1,1(--j i f 个数，由于),(1j i f L R ≤+-那我们不妨就令),1(j i f L Y -+=，这样就能在任何情况下均满足条件。
可以看出这里⎥⎦⎥⎢⎣⎢+≠2R L Y ，也就是说询问的时候并不一定将整个区间均分，二分在这里并不适用。
可以看出，这道题可以看作是本文开篇提出的问题的一部分，下面再来看基础猜数问题的另一种加强。
加强2：被猜数X 是1到N 范围内的整数，每次你可以询问一个整数Y 和X 的大小关系。
不同于普通猜数问题，本次提问的回答你不会马上得到，而是会在你下一次提出问题后才告诉你。
也就是你每问一个问题之后，得到的回答是你上一次提问的答案。
给出N ，请问在最坏情况下至少需要几次才能保证猜出X ？由于提问的答案不能马上获得，所以思考起来有一定的难度。
但是仔细分析的话，还是能够用递推来解决这道题目。
如同上题一样，我们也根据回答的三种情况来求得递推式，但是问题就是：当我们询问了一个Y 之后，不会得到关于Y 的任何信息。
要得到这些信息我们必须再询问一个数Y ’。
显然，在我们什么也不知道的情况下，只能凭空询问，要么把Y ’问在小于Y 的区间，要么问在大于Y 的区间，且只有当询问完之后，才知道X 与Y 的关系，才知道关于Y ’的询问是不是多余和浪费。
由于这里没有其他的限制条件，我们可以认为，Y ’问在小于Y 的区域和问在大于Y 的区域是等价的。
不妨设Y ’问在了小于Y 的区域。
设)(i f 表示询问i 次询问能够处理的最长区间长度。
在线代理|网页代理|代理网页|很容易就得到了一个简单的递推公式：1)2()1()(+-+-=i f i f i f同时根据上图，通过类似上一道题的分析，可以知道：)1(-+=i f L Y ，)2(-+='i f L Y 。
而对于题目要求求出的最少询问次数，类似的可以得到算法：已知0)1(,0)0(==f f ，根据1)2()1()(+-+-=i f i f i f 依次计算f 值，直到出现某个f 值n ans f ≥)(，则Ans 为所求的最少询问次数。
