Question

最近看到一个面试题目，觉得很有意思。就自己推导了下，不知道是否正确。

面试题目是：在1到1000的数字中，有一个数值是正确的。你可以任意猜测数值，我会告诉你是大了还是小了，问至少要猜多少次。
答案肯定是至少要猜1次。

现在新问题就是，理论最多要猜多少次，实际最多要猜多少次，平均要猜多少次?

我自己的推导方法和答案等有心人回答好了后，再放出。

Answer 1

这个可以采用简单的“对分法”原理。
设实际数值是a，从1-1000中猜。
1、首先猜a=500，如果大了，证明1<a<500，反之1000>a>500
2、如果a<500，就猜a=250，如果大了，证明1<a<250，如果小了，证明250<a<500
3、按照上面方法，每次都猜范围的一半，每次都将范围缩小一半。
这是数学里的一种常用解题方法（如：一元n次方程的解题方法）。
在这个计算里，你可以这样理解。
第一次猜，去掉500个数据；
第二次猜，去掉250个数据；
第三次猜，去掉125个数据；
第四次猜，去掉62（63）个数据；
第五次猜，去掉31（32）个数据；
第六次猜，去掉15（16）个数据；
第七次猜，去掉7（8）个数据；
第八次猜，去掉3（4）个数据；
第九次猜，去掉1（2）个数据；
第十次就猜到了。

追问

正确的算法。虽然数值没办法精确下来，但是已经比较接近了。
这个问题的解决方法我并不是用公式去套用，而是采用写程序的方法去统计计算。
目前程序计算了22550次，最小值1次，最大值33次，平均值为14（小数位误差为0.01）。很有意思，不知道一直算下去，最大值是否可以突破33次，超过50次。

Answer 2

实际用二分法，每猜一次可将范围缩小一半，2^10>1000，因此最多10次可以猜出来。
1次猜出的可能性为1/1000
2次猜出的可能性为(999/1000)(1/500)
3次猜出的可能性为(999/1000)(499/500)(1/250)
4次猜出的可能性为(999/1000)(499/500)(249/250)(1/125)
5次猜出的可能性为(999/1000)(499/500)(249/250)(124/125)(1/62)
6次猜出的可能性为(999/1000)(499/500)(249/250)(124/125)(61/62)(1/31)
7次猜出的可能性为(999/1000)(499/500)(249/250)(124/125)(61/62)(30/31)(1/15)
8次猜出的可能性为(999/1000)(499/500)(249/250)(124/125)(61/62)(30/31)(14/15)(1/7)
9次猜出的可能性为(999/1000)(499/500)(249/250)(124/125)(61/62)(30/31)(14/15)(6/7)(1/3)
10次猜出的可能性为(999/1000)(499/500)(249/250)(124/125)(61/62)(30/31)(14/15)(6/7)(2/3)

平均猜的次数求一下上面的期望值：
[1*(1/1000)+2*(999/1000)(1/500)+...]
=10*0.5+9*0.25+8*0.125+7*0.0625+6*0.03126+5*0.0159+4*0.0079+3*0.00399+2*0.00199+1*0.001
=9.003
平均大概9次可猜出。

Answer 3

这是数学中的关于求方程近似根的问题，一般采取二分法，理论上是猜10次（2的10次方=1024）
实际上因为没时间考虑这么清楚，肯定要多于10次，平均猜（这个这么算啊）？

Answer 4

最多猜1000次，假设这个数是1，你猜1000，他说大了，你猜999，他说大了，你猜998，他还说大了，这样猜下去就要猜1000次，实际最多要猜11次，用数学上的二分法算，第一次猜1000，第二次猜500，第三次猜250，第四次猜125，第五次猜63，第六次猜32，第七次猜16，第八次猜8，第九次猜4，第十次猜2，第十一次猜1，最多11次，用数学上的二分法，平均要猜多少次，要看一共有多少种猜法，猜法太多了不好算。

Answer 5

理论上要猜1000次
实际跟平均是得不出具体的答案的