珍珠湾ART

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

作者: 水母的智商 时间: 2007-3-14 08:27
标题: 你朋友知道一个电话号码8位数，只会回答是或者不是。你要问最少多少个问题才能保证把这电话号码问出？

纯数学角度

作者: yinyin 时间: 2007-3-14 08:31
标题: 回复：你朋友知道一个电话号码8位数，只会回答是或者不是。你要问最少多少个问题才能保证把这电话号码问出

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

作者: 新用户 时间: 2007-3-14 20:17
标题: 能否给出解题过程？

能否给出解题过程？

作者: yunqili 时间: 2007-3-15 01:08
标题: My solution.

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

作者: 新用户 时间: 2007-3-15 02:03
标题: 回复：My solution.

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

凭感觉应该有更好的方法

作者: yunqili 时间: 2007-3-15 02:45
标题: No difference for this one.

No difference for this one.

作者: yinyin 时间: 2007-3-15 05:13
标题: 回复：能否给出解题过程？

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

作者: 水母的智商 时间: 2007-3-15 10:44
标题: 是否可以从数字间的关系入手以减少次数？

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

作者: yinyin 时间: 2007-3-15 10:56
标题: 回复：是否可以从数字间的关系入手以减少次数？

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

作者: 新用户 时间: 2007-3-15 20:32
标题: 谢谢yinyin，yunqili的指教

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

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

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
标题: 回复：你朋友知道一个电话号码8位数，只会回答是或者不是。你要问最少多少个问题才能保证把这电话号码问出

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

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

作者: yinyin 时间: 2007-3-15 21:23
标题: 回复：回复：你朋友知道一个电话号码8位数，只会回答是或者不是。你要问最少多少个问题才能保证把这电话号

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

作者: salmonfish 时间: 2007-3-15 21:30
标题: 如无任何条件限制呢？

如无任何条件限制呢？

作者: yinyin 时间: 2007-3-15 21:40
标题: 回复：如无任何条件限制呢？

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

作者: salmonfish 时间: 2007-3-15 21:47
标题: “瞎子爬山法”？“黄金分割法”？etc? 吓猜罢了。

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

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

作者: yinyin 时间: 2007-3-15 22:36
标题: 回复：“瞎子爬山法”？“黄金分割法”？etc? 吓猜罢了。

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

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

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

作者: yunqili 时间: 2007-3-16 00:11
标题: 回复：谢谢yinyin，yunqili的指教

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
标题: 回复：回复：谢谢yinyin，yunqili的指教

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

作者: yinyin 时间: 2007-3-16 01:35
标题: 没用！[:((]

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

作者: yunqili 时间: 2007-3-16 02:34
标题: 回复：回复：回复：谢谢yinyin，yunqili的指教

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
标题: 回复：回复：回复：回复：谢谢yinyin，yunqili的指教[:-Q]

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

。You are right!

作者: yinyin 时间: 2007-3-16 03:30
标题: 回复：回复：回复：谢谢yinyin，yunqili的指教

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

作者: 开开心心 时间: 2007-3-16 04:17
标题: 可以用手枪顶着他脑袋的话，问一次还觧决不到问题只懂得哭就大笨蛋啦[:-K]

问题如下:

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

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

作者: yunqili 时间: 2007-3-16 04:20
标题: 回复：回复：回复：回复：谢谢yinyin，yunqili的指教

That's right.

作者: yunqili 时间: 2007-3-16 04:26
标题: 回复：可以用手枪顶着他脑袋的话，问一次还觧决不到问题只懂得哭就大笨蛋啦[:-K]

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

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

作者: 水母的智商 时间: 2007-3-16 08:06
标题: 二进制解法我也是有的，不知道能不能用不定方程

4个问题能问出一个数字

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

作者: 开开心心 时间: 2007-3-16 20:31
标题: 真的可以用手枪顶着他脑袋的话，还用计数觧决问题，两位y，y数痴[:-K]

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

欢迎光临珍珠湾ART (http://zzwav.com/)