舞会上有多少顶黑帽？

请点赞关注，你的支持对我意义重大。 ? Hi，我是小彭。本文已收录到 GitHub · AndroidFamily[1] 中。

前言

大家好，我是小彭。

在计算机面试中，逻辑类题目是规模以上互联网公司的必考题。由于题目花样百出，准备难度较大，题海战术可能不是推荐的做法。在这个系列里，我将精选十道非常经典的逻辑题，希望能帮助你找到解题思路 / 技巧。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。

系列文章：

• 我知道你不知道，我到底知不知道[2]
• 至少要几个砝码，可以称出 1g ~ 40g 重量[3]
• 舞会上有多少顶黑帽？[4]
• 25 匹马 5 条赛道，最快需要几轮求出前 3 名？[5]

1. 题目描述

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

2.解题关键

• 定义问题：假设问题为 y=F(n) ，表示当有 n 顶黑帽时，会在第 y 天打脸；
• 每个人都看不到自己的帽子，只能通过观察别人的帽子的表现猜测自己的帽子；
• 终止条件：当一个人眼前都是白帽时，由于至少有一个黑帽，则说明他自己是黑帽。

3. 题解

我是小彭，带你构建 Android 知识体系。

参考资料

[1]

GitHub · AndroidFamily: https://github.com/pengxurui/AndroidFamily

[2]

我知道你不知道，我到底知不知道: https://juejin.cn/post/6902829580013436942

[3]

至少要几个砝码，可以称出 1g ~ 40g 重量: https://juejin.cn/post/6903460612886495245

[4]

舞会上有多少顶黑帽？: https://juejin.cn/post/6903524335193948167/

[5]

25 匹马 5 条赛道，最快需要几轮求出前 3 名？: https://juejin.cn/post/6903861591188783112/