舞会

来自计算思维百科
跳转至: 导航搜索
舞会.png

一群人开舞会,每人头上都戴着一顶帽子。帽子只有黑白两种,黑的至少有一顶。每个人都能看到其他人帽子的颜色,却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子,然后关灯,如果有人认为自己戴的是黑帽子,就打自己一个耳光。第一次关灯,没有声音。于是再开灯,大家再看一遍,关灯时仍然鸦雀无声。一直到第三次关灯,才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子?

解决方案-逆推法

第一次关灯后,没有人打自己耳光,说明每个人都看到了有其他人戴着黑帽子,但是不能确定自己戴的是白帽子还是黑帽子。我们也无法通过第一次关灯确定到底有几顶黑帽子。

第二次关灯后,还是没有人打自己耳光,因此与第一次情况一样。

第三次关灯后,就有打耳光的声音响起,说明有人知道自己戴的是黑帽子,但是我们无法确定到底有多少人是戴着黑帽子。

因此,按照顺序推理是无法找出答案的。下面我们试着逆向推理:

因为至少有一个人是戴着黑帽子,假如只有一个人戴黑帽子,那他看到所有人都戴白帽,在第一次关灯时就应自打耳光。而第一次关灯后没有人打耳光,所以不止一个人戴黑帽子;如果有两顶黑帽子,第一次两人都只看到对方头上的黑帽子,不敢确定自己的颜色,但到第二次关灯,这两人应该明白,如果自己戴着白帽,那对方早在上一次就应打耳光了,因此自己戴的也是黑帽子,于是第二次会有耳光声响起;可事实是第三次才响起了耳光声,说明全场不止两顶黑帽,依此类推,应该是关了几次灯,有几顶黑帽。所以一共有三顶黑帽。

运用的计算思维

通过对题目的逻辑分析,得出关了几次灯才想起耳生光就有几顶黑帽的规律,体现了启发式的计算思维。

参考文献

http://www.nowcoder.com/questionTerminal/8b91f50dc6ae46ed8092ec0551fdd5d0