本文主要是介绍舞会上有多少顶黑帽?,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1. 题目描述
一群人开舞会,每人头上都戴着一顶帽子。帽子只有黑白两种,黑的至少有一顶。每个人都能看到其它人帽子的颜色,却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子,然后关灯,如果有人认为自己戴的是黑帽子,就打自己一个耳光。第一次关灯,没有声音。于是再开灯,大家再看一遍,关灯时仍然鸦雀无声。一直到第三次关灯,才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子?(假设每个人都足够聪明)
2.解题关键
- 定义问题: 假设问题为 y=F(n)y=F(n)y=F(n),表示当有 nnn 顶黑帽时,会在第 yyy 天打脸;
- 每个人都看不到自己的帽子,只能通过观察别人的帽子的表现猜测自己的帽子;
- 终止条件: 当一个人眼前都是白帽时,由于至少有一个黑帽,则说明他自己是黑帽。
3. 题解
- F(1)F(1)F(1):由于只且仅有 1 顶黑帽,那么黑帽 A 眼前全是白帽,他很清楚自己是黑帽,因此一定会在第 1 天打脸。即 F(1)=1F(1) = 1F(1)=1;
- F(2)F(2)F(2):由于只有 2 顶黑帽,大多数人眼前有 2 顶黑帽,而其中黑帽 A 和 B 最为特殊,他们眼前只有 1 顶黑帽。聪明的 A 知道 B 眼前只有两种情况:全是白帽 or 只有 A 头上的黑帽。聪明的 B 也知道 A 眼前只有两种情况:全是白帽 or 只有 B 头上的黑帽。因为 F(2)F(2)F(2) 没有人眼前全是白色,所以第 1 天不会有人打脸。那么 A 和 B 观察到对方没有在第 1 天打脸,分别都知道自己是黑帽,因此会在第 2 天打脸。即 F(2)=2F(2) = 2F(2)=2;
- F(3)F(3)F(3):由于只有 2 顶黑帽,大多数人眼前有 3 顶黑帽,特殊的黑帽 A、B 和 C 眼前只有 2 顶。它们分别观察到其他两个人均没有在第 2 天打脸,同理,就确信自己是黑帽。即 F(3)=3F(3)=3F(3)=3。
- 一次类推,有 F(x)=xF(x) = xF(x)=x,有几顶黑帽,就会在第几天打脸。
这篇关于舞会上有多少顶黑帽?的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!