前言
- 在计算机面试中，逻辑类题目是规模以上互联网公司的必考题。由于题目花样百出，准备难度较大，题海战术可能不是推荐的做法。
- 在这个系列里，我将精选十道非常经典的逻辑题，希望能帮助你找到解题思路 / 技巧。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。
系列文章
【持续更新】
1. 天黑请闭眼
1.1 题目描述
一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其它人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。
问有多少人戴着黑帽子？（假设每个人都足够聪明）
1.2 解题关键
- 1、缩小问题规模：每个人看到的是一个小规模问题
每个人都看不到自己的帽子，即：只能看到一个规模减一的问题。举个例子，有 10 个人和 5 顶帽子，那么头戴白色帽子的人相当于站在主持人视角，看到的是一个 “9 人 5 黑帽” 的问题；而头戴黑色帽子的人，看到的是一个 “9 人 4 黑帽”的问题。
1.3 题解
- 定义问题
设函数，函数表示有 x 顶黑帽时，会在第 y 天打脸。而我们的问题就是思考：当 y = 3 时，x 的值，即第 3 天打脸时，有几顶黑帽。
- 缩小问题规模
首先，我们随便取一个人为第一视角，则在这个人眼中，看到的是一个的问题。
提示： 在主持人的视角里，这个问题可能是
或者
。
此时，我们尝试缩小问题规模。对于 A 来说，无非是黑帽或者白帽，则在其他人的视野里有两种情况 / 假设：
可以观察到，如果假设 A 是白帽，则问题规模将缩小 1。那么我们不妨假设 A 是白帽，则在 B 的视角里，看到的是一个 问题。
- 递归
继续递归这个 “白帽假设” 的过程，最终会出现一个人眼前都是白帽的情况，问题规模无法缩小：
由于至少有一顶黑帽，所以这个人（E） 会在第一天打脸，在别人眼里，会看到问题。
- 回溯
如果 E 没有在第 1 天打脸，那么 E 眼前一定存在黑帽，说明上一层假设不成立，回溯。换句话说，就是 D 看到眼前只有 E 一个人戴黑帽，但是他第一天却没有打脸。只有一种可能，D 头顶也是黑帽。
此时，第二天 D 和 E 都会打脸，在别人眼里，会看到问题。
如果 D、E 没有在第 2 天打脸，那么 D、E 眼前一定存在至少 2 顶黑帽，说明上一层假设不成立，回溯。此时，第三天会有 3 个人打脸，即问题。
以此类推，如果有 x 顶黑帽，则第 x 天会有 x 人打脸，即。
论毕。
创作不易，你的「三连」是丑丑最大的动力，我们下次见！
网友评论