数学爱好者 (返回首页) 数学问答 麦穗理论(wiki) 更新


麦穗理论 (0.0.1)

取自 数学百科

跳转到: 导航, 搜索

[编辑] 故事

有一天,柏拉图问老师苏个拉底什么是爱情? 老师就让他先到麦田里去,摘一颗全麦田里最大最金黄的麦穗来。期间只能摘一次,并且期间只能向前走,不能回头。

柏拉图于是按照老师说的去做了,结果他两手空空的走出了田地。老师问他为什么摘不到?

他说:“因为只能摘一次,又不能走回头路,期间即使见到最大最金黄的,因为不知前面是否有更好的,所以没有摘。走到前面时,又发觉总不及之前见到的好,原来最大最金黄的麦穗早已错过了。于是我什么也没有摘!”

老师说:这就是“爱情”


之后有一天柏拉图问他的老师什么是婚姻?老师就叫他先到树林里,砍下一颗全树林里最大最茂盛的,最适合放在家做圣诞树的树。期间同样只能砍一次,以及同样只能向前走,不能回头。

于是柏拉图又照着老师的话去做。今次,他带了一颗普普通通,不是很茂盛,也不算太差的树回来。老师问他:怎么带这颗这么普通的树回来?他说:“有了上一次的经验,当我走到大半路程还两手空空时,看到这颗树也不太差,便砍了下来,免得错过了后,最后有什么也带不回来。”


老师说:“这就是婚姻!”

[编辑] 数学解

现在我们用数学的角度来讨论这个问题。

假设我们碰到的麦穗有n个,我们用这样的策略来选麦穗,前k个,记住一个最大的麦穗记为d(可能是重量,也可能是体积),然后k+1个开始,只要大于d的,就选择,否则就不选择。


对于某个固定的 k,如果最大的麦穗出现在了第 i 个位置(k < i ≤ n),要想让他有幸正好被 选中,就必须得满足前 i-1 个麦穗中的最好的麦穗在前 k 个麦穗里,这有 k/(i-1) 的可能。考虑所有可能的 i,我们便得到了前 k 个麦穗作为参考,能选中最大麦穗的总概率 P(k):

设 k/n=x ,并且假设 n 充分大,则上述公式可以改为:

对 -x · ln x 求导,并令这个导数为 0,可以解出 x 的最优值,它就是欧拉研究的神秘常数的倒数—— 1/e !

所以 k=n/e.

如果你想摘取最大的麦穗,假设有 n 个麦穗,你应该先将前 n/e 个麦穗作为参考,然后再k+1个麦穗开始选择比前面k个最大的麦穗即可。

取自"http://wiki.mathfan.com/index.php/%E9%BA%A6%E7%A9%97%E7%90%86%E8%AE%BA"