经典老智力题

来源: 2010-01-30 21:37:47 [旧帖] [给我悄悄话] 本文已被阅读:
第一次听时欧还在中学的说。。。。

国王生日,准备大赦100名囚犯。

把100名囚犯从高到矮排队,高个子的人,可以看到比自己矮的所有人(中学生排队一样的),但是矮的人,看不到比自己高的人。


现在给每个人戴上一顶帽子,颜色或者是黑色,或者是白色。每个人不知道自己帽子的颜色,但是可以看到站在前面的人的帽子颜色。

一个侩子手,拿着一把刀,从个子最高的那个人问起,他帽子的颜色,如果答错,立即砍头,如果答对,就自由了。


每个人只能答一个子:黑或者白


他说的每一个字,所有的人都能听到。


国王允许他们,在侩子手问问题之前,这100个人可以聚集在一起(当然,这个时候,还没有戴帽子),商量一个算法,

就是如何通过听后面人(个子高的)答案,确定自己帽子的颜色。


问题:什么样的算法,可以让被砍头的人最少? what's the expected % of survivals?