传说古希腊哲学大师苏格拉底的3个弟子曾求教老师,怎样才能找到理想的伴侣。于是苏格拉底带领弟子们来到一片麦田,让他们每人在麦田中选摘一支最大的麦穗——不能走回头路,且只能摘一支。第一个弟子刚刚走了几步便迫不及待地摘了一支自认为是最大的麦穗,结果发现后面的大麦穗多的是;第二位一直左顾右盼,东瞧西望,直到终点才发现,前面最大的麦穗已经错过了;第三位把麦田分为三份,走第一个1/3时,只看不摘,分出大、中、小三类麦穗,在第二个1/3里验证是否正确,在第三个1/3里选择了麦穗中最大最美丽的一支。
摘自百度百科。
K 随着苏格拉底来到了一片麦田,麦田中有 颗麦穗。K 想要不走回头路地找到尽可能大的麦穗。即从第 颗麦穗开始观察,每次观察后有两种选择:
- 放弃这颗麦穗,继续观察下一颗。
- 取走这颗麦穗,停止观察。
在观察一颗麦穗之前,是不知道它的具体高度的。但是 K 通过无人机大致确定了每颗麦穗的高度范围,可以认为,第 颗麦穗的高度是在 之间的一个随机实数。
现在 K 想知道,如果使用最优的观察策略,取走的麦穗的高度期望是多少。
样例 1 的解释:如果第一个麦穗的高度小于 小就取走下一个,否则取走第一个,答案的期望为 。