「数理逻辑」| 天黑请闭眼!

「数理逻辑」| 天黑请闭眼!

Android小彩虹2021-08-20 8:05:43290A+A-

点赞关注,不再迷路,你的支持对我意义重大!

Hi,我是丑丑。这里有 Android 进阶成长路线笔记 & 博客,欢迎跟着彭丑丑一起成长。(联系方式在 GitHub)

前言

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

系列文章

【持续更新】


1. 天黑请闭眼

1.1 题目描述

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

问有多少人戴着黑帽子?(假设每个人都足够聪明)

1.2 解题关键

  • 1、缩小问题规模:每个人看到的是一个小规模问题

每个人都看不到自己的帽子,即:只能看到一个规模减一的问题。举个例子,有 10 个人和 5 顶帽子,那么头戴白色帽子的人相当于站在主持人视角,看到的是一个 “9 人 5 黑帽” 的问题;而头戴黑色帽子的人,看到的是一个 “9 人 4 黑帽”的问题。

1.3 题解

  • 定义问题

设函数 y = F ( x ) y=F(x) ,函数表示有 x 顶黑帽时,会在第 y 天打脸。而我们的问题就是思考:当 y = 3 时,x 的值,即第 3 天打脸时,有几顶黑帽。

  • 缩小问题规模

首先,我们随便取一个人为第一视角,则在这个人眼中,看到的是一个 F ( X ) F(X) 的问题。

提示: 在主持人的视角里,这个问题可能是 F ( X ) F(X) 或者 F ( X + 1 ) F(X+1)

此时,我们尝试缩小问题规模。对于 A 来说,无非是黑帽或者白帽,则在其他人的视野里有两种情况 / 假设:

可以观察到,如果假设 A 是白帽,则问题规模将缩小 1。那么我们不妨假设 A 是白帽,则在 B 的视角里,看到的是一个 F ( X 1 ) F(X-1) 问题。

  • 递归

继续递归这个 “白帽假设” 的过程,最终会出现一个人眼前都是白帽的情况,问题规模无法缩小:

由于至少有一顶黑帽,所以这个人(E) 会在第一天打脸,在别人眼里,会看到问题 F ( 1 ) = 1 F(1) = 1

  • 回溯

如果 E 没有在第 1 天打脸,那么 E 眼前一定存在黑帽,说明上一层假设不成立,回溯。换句话说,就是 D 看到眼前只有 E 一个人戴黑帽,但是他第一天却没有打脸。只有一种可能,D 头顶也是黑帽。

此时,第二天 D 和 E 都会打脸,在别人眼里,会看到问题 F ( 2 ) = 2 F(2) = 2

如果 D、E 没有在第 2 天打脸,那么 D、E 眼前一定存在至少 2 顶黑帽,说明上一层假设不成立,回溯。此时,第三天会有 3 个人打脸,即问题 F ( 3 ) = 3 F(3)=3

以此类推,如果有 x 顶黑帽,则第 x 天会有 x 人打脸,即 F ( x ) = x F(x)=x

论毕。


创作不易,你的「三连」是丑丑最大的动力,我们下次见!

点击这里复制本文地址 以上内容由权冠洲的博客整理呈现,请务必在转载分享时注明本文地址!如对内容有疑问,请联系我们,谢谢!

支持Ctrl+Enter提交

联系我们| 本站介绍| 留言建议 | 交换友链 | 域名展示
本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除

权冠洲的博客 © All Rights Reserved.  Copyright quanguanzhou.top All Rights Reserved
苏公网安备 32030302000848号   苏ICP备20033101号-1
本网站由 提供CDN/云存储服务

联系我们