你朋友知道一个电话号码8位数，只会回答是或者不是。你要问最少多少个问题才能保证把这电话号码问出？

水母的智商 · 发表于 2007-3-14 08:27:37

纯数学角度

yinyin · 发表于 2007-3-14 08:31:42

27

本贴由[yinyin]最后编辑于：2007-3-14 0:33:17

新用户 · 发表于 2007-3-14 20:17:41

能否给出解题过程？

yunqili · 发表于 2007-3-15 01:08:26

27 Just like sorting. 2^27 > 99999999 > 2^26

新用户 · 发表于 2007-3-15 02:03:49

第一位数字应该有条件，也就是一定不为0。不知道是不是还是27次？

凭感觉应该有更好的方法

yunqili · 发表于 2007-3-15 02:45:06

No difference for this one.

yinyin · 发表于 2007-3-15 05:13:34

每一回答能给出 "二中择一" 的信息。现要从10⁸或9x10⁷（首位非０）中确定一个，故所需问题个数为最小的整数n使得10⁸或9x10⁷<=2ⁿ。yunqili的解释是正确的。

水母的智商 · 发表于 2007-3-15 10:44:19

是否可以从数字间的关系入手以减少次数？

yinyin · 发表于 2007-3-15 10:56:07

"数字间的关系" 是指什么?

新用户 · 发表于 2007-3-15 20:32:58

看来两位的解释，我明白了解法。这道题目我特别喜欢，而且也很实用。

其实，水母的问题也就是我的问题，这里我解释一下。

8为电话号码，最大为 99999999，最小为 10000000

用2进制表示就是

99999999：101111101011110000011111111

10000000： 100110001001011010000000

很显然，二进制只能为1或者0，二进制有多少位就是需要问多少次，这跟yinyin解释的 2ⁿ 本质相同。

99999999的二进制有27位，10000000的二进制有24位。我们需要选最坏情况也就是27次。

现在的问题是，我们能不能根据每一位数据之间的关系来排除一些可能性，从而降低询问次数？

比如说，

当我知道最高为为1的时候，那么我就肯定，第二高位一定为0，不可能为1；

当我知道前3位为000的时候，我知道下一位不可能为0，一定为1

我想了半天，知识有限，实在想不出，只是感觉有可能可以减少次数。

salmonfish · 发表于 2007-3-15 20:37:03

从纯数学角度出发，可以理解了。

但是，从实际的应用考虑，怎么才能最快找到那个最佳方案？

yinyin · 发表于 2007-3-15 21:23:06

这就应地而异了，要看当地电话局是怎样分割安排（包括预留空号等）这些号码的。

salmonfish · 发表于 2007-3-15 21:30:52

如无任何条件限制呢？

yinyin · 发表于 2007-3-15 21:40:11

就没有什么"数字间的关系" 了, 也就无捷径可循。

salmonfish · 发表于 2007-3-15 21:47:20

“瞎子爬山法”？“黄金分割法”？etc? 吓猜罢了。

本贴由[salmonfish]最后编辑于：2007-3-15 13:50:51

yinyin · 发表于 2007-3-15 22:36:14

“瞎子爬山法”是用于寻找多元可微函数的极值的近似数值计算方法，“黄金分割法”是用于寻找一元单峰函数的极值的近似数值计算方法。它们都不能用来降低确定电话号码问题的complexity。

本贴由[yinyin]最后编辑于：2007-3-15 15:3:19

本贴由[yinyin]最后编辑于：2007-3-15 15:28:33

yunqili · 发表于 2007-3-16 00:11:52

We are talking about the worst case (minimum number of questions) here, not the average. Otherwise, golden ratio is better than divide-by-2.

yinyin · 发表于 2007-3-16 00:34:22

混淆了不同类型的问题。golden ratio 法（黄金分割法）不能用于此电话号码问题。黄金分割法是一种节省的优化（optimization)方法。它需要有一个单峰的双边严格单调的目标函数。然而，对于电话号码问题，无法合理定义这样一个目标函数。

yinyin · 发表于 2007-3-16 01:35:51

没用！回答只能是 "是" 或 "不是" 。

yunqili · 发表于 2007-3-16 02:34:38

Randomly pick a number (each number has same chance), mathematical expectation is smaller for golden ratio than divide-by-2. To guess a particular number, golden ratio is not the optimization.

yinyin · 发表于 2007-3-16 03:19:06

Sorry, 我没有正确理解您先前的帖子

。You are right!

yinyin · 发表于 2007-3-16 03:30:24

"然而，对于电话号码问题，无法合理定义这样一个目标函数" 的说法欠妥。仔细想想，还是可以的，从而把确定电话号码问题转化为优化问题。

开开心心 · 发表于 2007-3-16 04:17:01

问题如下:

不要说话，听清楚问题，只说一次。由现在起，我由1数到99999999，当我说到正确号码，你就回应一声是。

回应错的话，我就一枪打爆你个头。现在开始，1、2、3........

yunqili · 发表于 2007-3-16 04:20:48

That's right.

yunqili · 发表于 2007-3-16 04:26:29

If the correct one is 99999999 and even if you can ask 10 number per second, it takes 116 days. How patient you are!

yinyin · 发表于 2007-3-16 05:06:32

无独有偶，跟一周多前脑坛上 "列素数" 那样，......

水母的智商 · 发表于 2007-3-16 08:06:43

4个问题能问出一个数字

我在想能不能用8个问题问出这个8位数分别除以某两个数的余数从而有得到一个一定能推导到原数字方法

开开心心 · 发表于 2007-3-16 20:31:08

给你3秒，将正确答案写出来，举起来，说声是。写得不对，就一枪打爆你个头。

		自动登录	找回密码
密码			立即注册

动态微博

你朋友知道一个电话号码8位数，只会回答是或者不是。你要问最少多少个问题才能保证把这电话号码问出？

回复：你朋友知道一个电话号码8位数，只会回答是或者不是。你要问最少多少个问题才能保证把这电话号码问出

能否给出解题过程？

My solution.

回复：My solution.

No difference for this one.

回复：能否给出解题过程？

是否可以从数字间的关系入手以减少次数？

回复：是否可以从数字间的关系入手以减少次数？

谢谢yinyin，yunqili的指教

回复：你朋友知道一个电话号码8位数，只会回答是或者不是。你要问最少多少个问题才能保证把这电话号码问出

回复：回复：你朋友知道一个电话号码8位数，只会回答是或者不是。你要问最少多少个问题才能保证把这电话号

如无任何条件限制呢？

回复：如无任何条件限制呢？

“瞎子爬山法”？“黄金分割法”？etc? 吓猜罢了。

回复：“瞎子爬山法”？“黄金分割法”？etc? 吓猜罢了。

回复：谢谢yinyin，yunqili的指教

回复：回复：谢谢yinyin，yunqili的指教

没用！[:((]

回复：回复：回复：谢谢yinyin，yunqili的指教

回复：回复：回复：回复：谢谢yinyin，yunqili的指教[:-Q]

回复：回复：回复：谢谢yinyin，yunqili的指教

可以用手枪顶着他脑袋的话，问一次还觧决不到问题只懂得哭就大笨蛋啦[:-K]

回复：回复：回复：回复：谢谢yinyin，yunqili的指教

回复：可以用手枪顶着他脑袋的话，问一次还觧决不到问题只懂得哭就大笨蛋啦[:-K]

回复：可以用手枪顶着他脑袋的话，问一次还觧决不到问题只懂得哭就大笨蛋啦[:-K]

二进制解法我也是有的，不知道能不能用不定方程

真的可以用手枪顶着他脑袋的话，还用计数觧决问题，两位y，y数痴[:-K]