用数学思考01-国王与毒酒(2)

上回说到“国王与毒酒”问题的变种版本,机智如你肯定已经搜索了一番知晓了答案,或者更知晓了这篇要讲什么。毕竟,tag 已经说明了一切嘛。

1. 500桶的解

所给出的2人解答里是这么说的:

将500桶酒分作23行23列,囚犯A每隔一小时喝一行,囚犯B每隔一小时喝一列。最后分别根据A、B死亡的时间点即可反查出毒酒所在的行和列,行列交叉处就是毒酒所在。

2. 50桶和500桶的区别

补充回忆,再次分别贴一遍500桶版本的问题:

50桶酒,其中有1桶有毒,人喝下去1小时后见效。而国王可以随意命令士兵/死囚去试毒,求最少多少人且最快多久分辨出有毒的酒

500桶酒,其中1桶是毒酒;48小时后要举行酒会;毒酒喝下去会在之后的第23-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪一桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

仔细观察,不难发现其区别有:

  1. 酒桶从50增加到了500
  2. 毒酒见效时间从1小时增加到了23-24小时
  3. 可接受时间从1倍见效时间增加到了2倍见效时间
  4. 只问了最少要多少囚犯,并未附加“同时最快”的约束条件

让我们来分析下:

首先,第4条非常关键,否则这只是50桶版本问题的简单推广而已。答题一定要看清题对不对?

然后,结合第3条似乎一下子多了非常多了可选策略,比如后面会详细说明的“作妖策略”。

最后,也是最有趣的第2条。粗看似乎只是告诉你生效时间变长了,但仔细一看,它既明确告诉了你“在48小时内一个囚犯保证可以尝试很多次”,又隐藏了“每次尝试最小间隔1小时”这个约束。

答案里说每1小时喝一次,其原因也是因为毒酒的见效时间是个23~24小时之间的未知值,如果间隔时间小于1小时将无法区分两次验毒行为

这个非常容易想明白,让我举个例子好了:

想象一下,你打开手电正对着一堵墙照过去,出现直径1米的圆形光斑,从光斑到你的手电是一个直径1米高度未知的圆锥,顶点是你。

那么在旁边再紧挨着摆下一个同样的圆锥,使得两个光斑外切。
两个圆锥顶点之间的距离不就刚好是半径乘以2么?

如果出现光斑重叠,那就无法分辨“这一块到底是谁的手电照亮的”,在题目里也就是无法分清“这次死亡到底是喝哪一行/列造成的”。

题目里的23~24小时,前后相差1小时,即 $\Delta t = 1h$ ,就等效于上面例子里的这种1米大光斑。

那么这个时候我就可以发散一下了,假设使用的是光斑大小近乎为零的激光手电呢?那么发射这边是不是可以互相之间站得无限接近?会有什么神奇效果?

3. 疯狂的试酒者

简化思考,以50桶版本为例来进行思考实验,我们只需要一个试酒者就能搞定问题:

  1. 令毒酒非常精确地在1小时后生效,计时手段也非常精确;
  2. 令试酒者有超人般的能力,能无限快地喝酒;
  3. 令其他我还没想到的干扰都不复存在;

设酒桶编号是从0开始到49结束。

令试酒者按酒桶编号每隔 $\Delta t$ 时间就喝一次酒,从 $0$ 时刻点开始喝,喝满50次。其实按前面的经验解,49次就行了

那么当 $ 1h + \Delta t \times n $ 时刻试酒者死亡,即可判断编号为 $n$ 的酒有毒。

这种策略仅需要1人,消耗的时间是 $\ T_{cost} \in [1h, 1h + 49 \Delta t] $

当 $\Delta t$ 足够小,无限趋近于0,我们甚至可以宣称只要1人1小时就解决了问题!

那么,是不是我们其他的求解策略都可以用类似的“作妖”来替换呢?

当然可以!

等等,再想想,这些是不是说明有什么通用的规律呢?

答案是:

问题的统一

在此之前,回过头去看下前面所有的策略、解答。

1. 50桶几队几人

在50桶版本的所有解答里,都一再表达了一个概念:“几个队、各个队伍几个人”,比如“某队有几种非0的取值情况,所以需要几人”。

  1. 1个队,需要有 $[1, 49]$ 这49种非0取值,所以要49人
  2. 2个队,X队有 $[1, 6]$ 6种非0取值、Y队有 $ [1, 7] $ 7种非0取值,所以要 $ 6 + 7 = 13 $ 人
  3. 3个人,X、Y、Z三队均有 $[1, 3]$ 3种非0取值,所以要 $3 + 3 + 3 = 9$ 人

等等

其实这都是可以给出通用解释的,因为这件事情的本质在于:

  1. 我们用了几队人,就相当于把“50中可能中的哪一种”这1件$ \frac{1}{50} $ 概率的事情给拆分成了几件
  2. 这几个队各自去确定“事实是x种可能中的哪一种”
  3. 向我们表达每个分拆事件的结果,汇总后得出原$ \frac{1}{50} $ 概率事件的结果

以前面的两队13人求解策略为例来讲解,再贴一下之前的表格,把0号也补上:

相应的结果判定方法:

  1. 全员存活,编号1的酒有毒
  2. 13人中仅有1人死亡,则相应的那桶酒有毒。例如仅X6死亡意味着编号49的酒有毒
  3. 13人中有2人死亡,则这两人同时喝到的酒有毒。例如X6和Y1死亡代表编号50的酒有毒

在这套策略中:

  1. 我们将“50桶酒那一桶有毒”这件 $ \frac{1}{50} $ 概率的事情拆分给了X、Y两个队伍
  2. X队需要给出“7组混合酒里哪一组有毒”这件 $ \frac{1}{7}$ 概率事件的确定答案
  3. Y队需要给出“8组混合酒里哪一组有毒”这件 $ \frac{1}{8}$ 概率事件的确定答案

当我们去查看结果的时候,只能从“发现某队的尸体”上得出“该队有喝到毒酒”这种信息,但无法确定死者死于哪一组混合酒。相当于之前我们分派给X、Y队的测试任务,未能给出足够的信息,无法得出最终的结果。

对X的7种混合酒、Y队的8种混合酒,我们使用的办法是:

  1. X队派6人,能反映 [“无人死亡”, “1号死亡”, … “6号死亡]这7种可能的事件结果

  2. Y队派7人,能反映 [“无人死亡”, “1号死亡”, … “7号死亡]这8种可能的事件结果

上篇的策略里我们选定的是每队取0值的不用派人,是因为只要该队其他人没死,就等同于取0值所代表的事件发生了。

以X队为例,因为确定只有一瓶毒酒,所以对X队来说7组混合酒必然有一组有毒,即$\frac{1}{7}$ 概率,派6人即可试出。也就是 $ 1 = \frac{1}{7} \times \boxed{6} + \frac{1}{7}$

这样:

  1. X队就能给出$ \frac{1}{7}$ 概率事件的确定答案;

  2. Y队就能给出$ \frac{1}{8}$ 概率事件的确定答案;

  3. 合起来给出$ \frac{1}{50}$ 概率事件的确定答案;

2. 500桶的2人和“超人”试酒者

在500桶版本里,虽然只需要2人,但由于时间更加宽裕,每人所能给出的可能性更高——可以通过“死在哪一刻”来表达多种可能性:

囚犯A、B均每隔1小时喝一行/列,共23行23列,意味着他们的死亡时间都是 $ \frac{1}{23}$ 概率的事件;

合起来给出$ \frac{1}{500}$ 概率事件的确定答案;

每小时喝1次,喝23次,跟一队的23人每人喝一行/列,其实是等价的,都是给出了 $ \frac{1}{23}$ 概率事件确定答案

在我们对50桶酒的作妖解法里,只需要1个人,也就是1个队。但它也提供了50种可能性。我们以喝满50次为例:

1个队1个人,可以死在[ $1h$, $1h + \Delta t$, $1h + 2 \Delta t$, … ,$1h + 49 \Delta t$] 这50种可能的时刻点

它依然成功地给出$ \frac{1}{50}$ 概率事件的确定答案,跟派50人跟酒桶一一对应一齐喝,是等价的。500桶的2人、作妖解法的“超人”试酒者,无非是在时空维度上展开,来表述 概率事件确定答案

总结一下就是:

  1. $ \frac{1}{P_0} $ 概率的事件拆分成 $n$ 件概率事件,它们的概率分别是 $ \frac{1}{P_1}, \frac{1}{P_2}, \frac{1}{P_3}, … \frac{1}{P_n} $

  2. 用某种求和的方法汇总这 $n$ 件概率事件,表示这 $n$ 件概率事件各自处在某一系列特定结果时,等价(确定)原来的$ \frac{1}{P_0} $ 概率的事件处在某一特定结果

现在的问题就是,这种求和方法是什么?

前面朴素解法:

在二维平面里的 $ a \times b \ge 50$

三维空间里的$ a \times b \times c \ge 50$

等等

其实前后已经对应上了,完全可以可以归纳出 $ P_1 \times P_2 \times … P_n \ge P_0$ 就是我们所求的“求和方法”。

很好,从问题到数学,从数学回到问题,都能圆上了,两个乃至更多版本的“国王毒酒”问题也都统一了。但这就是我们想要的通法通则了吗?我们找到的明明就是个乘法!

另一方面也应该明显感觉到了,可能性越多,发生的概率也就越低的事件,确定其发生,要做的测试越复杂。如果有一种理论能解释、度量、计算这种特性,那它才是我们想要的通法通则。

其实到这一步,已经离主题一步之遥了

前面讲过我曾向“羊宝宝”大佬提过50桶版本的题,大佬沉思片刻就给出答案6,再问理由,回答的是:

毒酒以 $ \frac{1}{50} $ 的概率出现,信息量是 $log_2\,50$,即6比特,所以要6人

我当即恍然大悟,这也就是上一篇提过的事情。我回问道,你们还开了《信息论》这门课不成?大佬答“自己随便看的”。

总是从学校出来后才觉得书本里的知识好用

是的,国王与毒酒的问题用信息论来解释是普适的。本篇最终就是要讲这个。

某乎上500桶版本的众多回答里有一条就提到过,应该是同道中人。不过并没有更进一步的描述,旁的人看来应该也不太明白吧

3. 信息的度量

信息论是什么?简单讲它是一门研究对信息进行量化、传输、存储的理论。这里我们需要它“对不确定性进行度量”的能力。

信息论是我大学学过的一门课,隐约只记得香农、Huffman编码、信息熵

更具体的可以自行搜索了。一般日常所见,直接感触到它的应该是压缩文件了。有的文件可以压缩得很小,而有的压缩前后几乎差别不大,信息论已经指明了这里面的原因。

比如两张同样分辨率的图片,一张是全部黑色像素点,一张是美食。分别zip压缩两张图片,得到的压缩包的体积相差极大

信息熵,用简单的话来解释,信息的可能性越多,预测该信息的值所涉及到不确定度的量 也就越大。这个量度就叫“信息熵”。

当年给这个量度取名 信息熵 除了唬人,也是有道理的。越随机也越无序,热力学的熵和信息论的熵在这点上相通了。

找不到课本,拉出维基。当取自有限样本时,信息熵的公式:

其中 $P(x_i)$ 是 $x_i$ 事件发生的概率,$I(x_i)$ 是 $x_i$ 事件的自信息(self-information),其计算方法是:

在这里 $b$ 是对数计算的底数,一般用$2, e, 10$

  1. $b=2$时,信息熵的单位是bit
  2. $b=e$时,信息熵的单位是nat
  3. $b=10$时,信息熵的单位是Hart

这里有两个概念,信息熵自信息:

  1. 度量“概率空间中单一事件或者离散随机变量的值”相关信息量的量度,叫做自信息:$ I(x_i) = -log_b{P(x_i)}$。它有单位,单位跟计算底数相关。
  2. 自信息的期望值,就是信息熵。

期望值的计算应该不必讲述了吧

这两个量,分别是对整体情况和特定情况的度量。一系列事件中,发生概率越低的情况发生了,这情况本身的自信息也就越大

信息被从信息源传递到接收者,当且仅当接收者无法预知内容,信息才得以传递,否则信息量为0。换而言之,100%确定的事情发生了,其自信息是0。

学以致用

了解了两个概念及其算式,现在开始用起来

1. 再试题目

以我们50桶酒的题目为例:

  1. $ \frac{49}{50} $ 的概率是无毒酒,其自信息是 $ -log_2{\frac{49}{50}} $ bit
  2. $ \frac{1}{50} $ 的概率是有毒酒,其自信息是 $ -log_2{\frac{1}{50}} $ bit

计算期望,就得到了信息熵。但我们解题需要的是“找到毒酒”,也就是预测 $ \frac{1}{50} $ 概率的事件。

只有当我们通过测试、观测所能获取的信息量大于等于某个阈值时,“确定毒酒是第几号”这件事情才能被我们确认,相当于我们收到了“毒酒是第X号”这条消息。否则就是信息不足,无法判定。

而这个阈值就是$ \frac{1}{50} $ 概率事件的自信息 $ -log_2{\frac{1}{50}} \approx 5.64386$ bit

  1. 观测一个人“是死是活”,生死几率各半。通过其结果所以我们可以得到的自信息是 $ -log_2{\frac{1}{2}} = 1$ bit

    那么我们需要的人数是: $ \frac{-log_2{\frac{1}{50}}}{-log_2{\frac{1}{2}}} \approx 5.64386$

    向上取整就是6人,也就是我们需要观测6个人分别“是死是活”,获取总计6bit的信息,足以100%预测毒酒所在。

  2. 作妖解法里,是观测一个人“死在第1小时零几分钟”,共50种可能性。通过其结果,我们得到的自信息是 $ -log_2{\frac{1}{50}} $ bit

    那么我们需要的人数是: $ \frac{-log_2{\frac{1}{50}}}{-log_2{\frac{1}{50}}} = 1$

    也就是只需要1人,观测这个人死在哪一刻,获取足够的信息100%预测毒酒所在

  3. 500桶版本的题目里,是观测 一个囚犯“死在第T小时零几小时” $ T \in [23,24] $ , 按题目48小时内囚犯可以尝试24次,有24种可能性。通过其结果,我们得到的自信息是 $ -log_2{\frac{1}{24}} $ bit

    那么我们需要的人数是: $ \frac{-log_2{\frac{1}{500}}}{-log_2{\frac{1}{24}}} \approx 1.95548$

    向上取整就是2人,分别观测这2人死在哪一刻,获取足够的信息100%预测毒酒所在

这也是前面所说的“分成 $n$ 件概率事件,观测后汇总求和”的本质。至于拆成怎样的概率事件,就需要读题了。

是不是觉得说破之后,这种题目一下子非常简单?

2. 实际与理论

本次“国王毒酒”从朴素解法的具体实践,到推广问题,尝试找到普适规律,再到引入可描述、概括普适规律的理论,最后又从理论回过头指导解题方案。

这是一套完整的流程,也是数学的特点所在:来自现实、超脱现实、指导现实

而我们知道理论上可行,但到具体实现还有一段距离,这就是应用的范畴了。

本篇小结

1. 数学是什么

历来自然科学的发展进步,离不开数学工具的发展。因为人类的常识实在是太过渺小不堪了,比如:

完全无法想象三维以上的空间,天体的引力对空间的拉伸影响,只能想象成沙发上有个铅球。

数学最擅长做的,就是基于已知结论进行推而广之:证明现有公式定理,在推广集里依然为真,再推导出更多规律。以此来对人类常识之外的东西进行研究,给现有的研究指出方向。

然而正如我前面感叹的,总是从学校出来后才觉得书本里的知识好用。以前上课的时候很难有直观的理解“这有什么用”——数学不光是那堆完全看不懂的符号听不懂的定义,它一定不是思考游戏,更不是试卷上的证明题计算题。

它是一种思考的方式、套路,归纳分析问题的理论,实践解决问题的工具。

2. 用数学思考

回到现实,我们在工作生活里,面对这样那样的实际问题,如果能找到合适的数学理论工具,就能简化流程,少走很多弯路。

例如编程中对多个条件进行if else 判断,如果漏写所有情况,程序很可能就会跑出未定义的行为,而且还极难定位。但如果数学知识还在,简单画一画就能列清楚。

也不一定非得是针对编程工作,比如所谓“最优停止理论”,或者叫秘书问题(Secretary problem):

要聘请一名秘书,有 n 个应聘者。每次面试一人,面试后就要及时决定是否聘他,如果当时决定不聘他,他便不会回来。面试后总能清楚了解应聘者的合适程度,并能和之前的每个人做比较。问什么样的策略,才使最佳人选被选中的概率最大

答案是最优截断值趋近于 $ \frac{n}{e}$,最佳人选被选中的概率为 $ \frac{1}{e} \approx 0.367879$。这个问题类似名称有很多很多:

比如:把“秘书”替换成“对象”,“应聘者”替换成“相亲者”,就变成相亲问题了呗。不过现实里可不是题目里假设的那么单纯、绝对,比如舔狗啦、备胎啦之类的

比如:换成手游里初始送了30次10连抽,抽到第几次“见好就收”。等等

是不是非常有意思?

我觉得很有意思!这也是开坑这个系列的本意所在

本篇到此结束,不知下一篇是什么题目,什么时候会写……

参考资料和工具

  1. Wikipedia
  2. Mathematica
  3. Java

用数学思考01-国王与毒酒(1)

引子

好几年前跟朋友吃饭的时候惯例闲聊,我提了一道题,昵称“羊宝宝”的大佬立刻指出答案以及求解思路。我立刻茅塞顿开,联想起了自己大学的课程,灵感迸发,一番酣畅的讨论,仿佛回到了学校。

后来跟当时在场的另一朋友聊起此事(上一篇里提到过开坑说明),而这么久过去也没写。一个既有趣,又引人思考的话题,可不能浪费了。

题目

这道题有各种版本,我第一次知道的版本是这样的:

国王有50桶酒,已知有且仅有1桶有毒,人喝下去1小时后见效。而国王可以随意命令士兵/死囚去试毒,求最少多少人且最快多久分辨出有毒的酒

如果搜索国王 毒酒,则可以找到各种变种,例如酒桶增多了、毒发时间变长了等。且住,先不看那些,来思考一下上面的“50桶版本”

问题初解

当时我是在面试的时候被问到这道题,“自然而然”是按程序员的思路去看待问题——“嗯,这是要找到一个时间、空间开销最优的算法”,典型的应试思维。当时过了几分钟,我就放弃了,当然更多原因是面试得很差。

不过这个题目一直在我脑子里转悠,我想找到解法

先简单粗暴地来,50人一人试一桶(49人也可以, 1小时全没中毒那就是最后一桶有毒),1小时可解。那么,最快最少的答案,必然是大于等于1小时且小于50人,那么必然得喝下不同桶的混合酒,于是剩下的问题是怎么安排策略。

策略必须满足的条件:

  1. 输入$x$人($x < 50$),每人喝下混合的酒,等待1小时后获取“死亡结果”
  2. 通过最终结果能唯一确定毒酒

所以就变成了怎么安排混合方式的问题,先来朴素的解法

朴素的解法

统统只需要1小时

1. 排成一条线

将50个点依次放到X坐标轴上,那么按50桶酒从1到50的编号,列出其在X轴上的坐标是:

1
2
3
4
5
6
7
8
9
0
1
2
3
4
...省略
47
48
49

其中取值为0的无须测试,X轴上有49个值,所以需要49人:哪一个挂掉了,就表示相应的酒有毒;都没挂掉,则是坐标原点0所代表的第一桶酒有毒。这也是前面的简单粗暴解法的答案,明显不满足要求,那么更进一步

2. 摆一个方阵

将50个点依次放到XY平面的第一象限,但这可以有很多种摆法。设摆成a行、b列,则需要满足条件: $ab \ge 50$ 且 $a,b$ 均是正整数,目标是使得 $a + b$ 尽量小。不用想就知道当 $a = b$ 的时候满足条件,又因为 $a,b$ 都是正整数,所以 $a = 7, b = 8 $ 即可。故而令 $y \in [0, 7]$ ,是当前最优解

那么按50桶酒从1到50的编号,列出其在XY平面上的坐标是:

点击展开/折叠
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
(0,0)
(0,1)
(0,2)
(0,3)
(0,4)
(0,5)
(0,6)
(0,7)
(1,0)
(1,1)
(1,2)
(1,3)
(1,4)
(1,5)
(1,6)
(1,7)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(2,5)
(2,6)
(2,7)
(3,0)
(3,1)
(3,2)
(3,3)
(3,4)
(3,5)
(3,6)
(3,7)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)
(4,5)
(4,6)
(4,7)
(5,0)
(5,1)
(5,2)
(5,3)
(5,4)
(5,5)
(5,6)
(5,7)
(6,0)
(6,1)

同上,取值为0则无需测试,那么X轴上有6个值,Y轴上7个值,所以需要13个人。

到这里一下子少牺牲一波倒霉蛋,可喜可贺。上面这段50行坐标似乎好有道理,但这个摆好的难道不是8行7列,那为什么是 $6 + 7 = 13$ , 需要13人?取值为0无需测试是什么含义?

在X坐标轴上 $x = 0$ 无需测试,很容易理解,49人没死,那就是没人喝的有毒呗,那XY坐标平面是怎么操作的?

莫慌,我们把这么个酒桶阵画出来,为了方便用markdown语法表述,将酒桶阵顺时针旋转了90°,如下表格:

来两拨人,分别记作X队、Y队。如此,X队每人按上面的表格喝一行,Y队每人按上面的表格喝一列。例如X队1号就喝编号9,10,11,12,13,14,15,16 这8桶的酒, Y队1号2,10,18,26,34,42,50这7桶的酒

最终结果:

  1. 全员存活,编号1的酒有毒
  2. 13人中仅有1人死亡,则相应的那桶酒有毒。例如仅X6死亡意味着编号49的酒有毒
  3. 13人中有2人死亡,则这两人同时喝到的酒有毒。例如X6和Y1死亡代表编号50的酒有毒

嗯,能完美地唯一确定毒酒编号!

想到这一步,立刻觉得事情有眉目了,如果扩展到XYZ三维空间中,摆成a行b列c层,应该能进一步减少人数要求

3. 堆成一摞

将50个点放进XYZ空间直角坐标系的第一卦限(类比二维平面,三维空间的有 $2^3 = 8$ 个”象限”,所以中文译名就用卦限了。正所谓“两仪四象八卦”),也就是前面提到的a层b行c列

需要满足条件: $a \times b \times c \ge 50$ 且 $a,b,c$ 均是正整数,目标是使得 $a + b + c$ 尽量小

同理,得到XYZ空间直角坐标系中酒桶编号排列如下:

点击展开/折叠
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
(0,0,0)
(0,0,1)
(0,0,2)
(0,0,3)
(0,1,0)
(0,1,1)
(0,1,2)
(0,1,3)
(0,2,0)
(0,2,1)
(0,2,2)
(0,2,3)
(0,3,0)
(0,3,1)
(0,3,2)
(0,3,3)
(1,0,0)
(1,0,1)
(1,0,2)
(1,0,3)
(1,1,0)
(1,1,1)
(1,1,2)
(1,1,3)
(1,2,0)
(1,2,1)
(1,2,2)
(1,2,3)
(1,3,0)
(1,3,1)
(1,3,2)
(1,3,3)
(2,0,0)
(2,0,1)
(2,0,2)
(2,0,3)
(2,1,0)
(2,1,1)
(2,1,2)
(2,1,3)
(2,2,0)
(2,2,1)
(2,2,2)
(2,2,3)
(2,3,0)
(2,3,1)
(2,3,2)
(2,3,3)
(3,0,0)
(3,0,1)

依然去掉0值,X,Y,Z的取值都有三种,也就是X,Y,Z三个小队都派出3人,因此需要9人

这里我就不画排列表格了,这可是一个 $4 \times 4 \times 4$ 的未填满的立方体:如果把X的取值作为层高的话,那它就是4行4列4层的一摞酒桶,有3层填满而第4层只有两个桶。对照上面完整的“XYZ坐标-编号”,能轻易地从最终结果唯一确定毒酒编号

4. 朴素解法的终点

4.1 从问题到数学

9人就是最终解了吗?如果你想到了放进三维空间这一步,给出答案 $9$ 而不是 $4\times3=12$ ,已经很厉害了,我觉得这是通过常识能做到的极限。毕竟谁也想象不出三维以上的空间是啥样、怎么摆,对吧?

虽然隐隐约约感觉将50个酒桶丢进更高维空间里去,几维空间就派出几队人,这能进一步减少所需人数,但这个方向的终点到底是多少呢?能做到的极限是多少呢?

常识不好使了很正常,赶紧回想一下数学归纳法吧,中学数学老师会比较欣慰的

设维度为正整数 $n$ , 那么已知:

  1. $n = 1$ 时, $50^1 = \boxed{50}$ , 需要1队人。合计 $(50 - 1)$ 人
  2. $n = 2$ 时, $8^2 > 8 \times (8 - 1) > \boxed{50} > 7^2$ , 需要2队人。合计 $(8 - 1) + (7 - 1)$ 人
  3. $n = 3$ 时, $4^3 > \boxed{50} > 4^2 \times (4 - 1)$ , 需要3队人。合计 $(4 - 1) + (4 - 1) + (4 - 1)$ 人

接着推测:

$n = 4$ 时, $3^4 > 3^3 \times (3 - 1) > \boxed{50} > 2^4 $, 需要4队人。合计 $(3 - 1) + (3 - 1) + (3 - 1) + (2 - 1)$ 人

看起来好规整,这个合计人数看起来也很有规律,先试着固定它猜测一下

那么当 $n$ 为某一常数时,设 $x$ 为满足要求 $x^n \ge 50$ 的最小正整数,是否可以有推论:

  1. 若 $x^n \ge \boxed{50} > x^{n-1} \times (x - 1)$ , 所求解为 $(x - 1) \times n$ 人
  2. 若 $x^n > x^{n-1} \times (x - 1) \ge \boxed{50}$ , 所求解为 $(x - 1) \times (n - 1) + (x - 2)$ 人

看起来好复杂,但若把 $n$ 当做变量, $x$ 也从正整数扩展到正实数范围内,那么可知 $x=\sqrt[n]{50}$ ,上面的公式可以大胆简化为:

所需人数等于 $n(\sqrt[n]{50} - 1)$

又由于最终人数必须整数,所以向上取整

所需人数等于 $\lceil{n(\sqrt[n]{50} - 1)}\rceil$

接着验算下 $n = 1,2,3$ 的情况,发现居然都是对的。我们先假装公式是正确的吧!

简单地画个图可以发现随着 $n \to +\infty $ ,所需人数的确是不断减少的。如果数学分析的知识还在,不难发现:

$\lim_{n \to +\infty}\,{n(\sqrt[n]{50} - 1)} = ln\,50 \approx 3.91202$

对其向上取整:

$\lceil{3.91202}\rceil = 4$

4.2 从数学回到问题

队伍数量越多,所需总人数越少没毛病。等于4,提交答案?

不行的,这个推测出来的公式是有现实含义的,$n$对应着n队人,$(\sqrt[n]{50} - 1)$ 对应着平均各队派出的人数

回到题目, 确定 $n \in {\displaystyle \mathbb {Z} ^{+}}$ (即 $n$ 为正整数)且 $(\sqrt[n]{50} - 1) \ge 1$, 不然平均每队派人数不到1人,肯定是出现了空队伍,这毫无意义

随着 $n$ 递增, $\sqrt[n]{50}$ 在逐渐减小且无限趋近于 $1$

令 $(\sqrt[n]{50} - 1) = 1$ , 求出满足上述条件的最大的 $n$

计算得到 $n$ 的合适取值就在 $log_2\,50 \approx 5.64386$ 附近了

那么n取5或者6的时候就是最优解了,列一下底数x:

  1. $n = 5, x = \sqrt[5]{50} \approx 2.18672, \lceil{x}\rceil = 3$

  2. $n = 6, x = \sqrt[6]{50} \approx 1.91938, \lceil{x}\rceil = 2$

实际使用中 $n = 5$ 的情况是严重不可取,因为 $3^5 = 243$ 太大了,把50个酒桶放进去会有非常多的浪费, 其结果就是需要人数肯定不止是6人

生成对应的5维坐标清单如下:

点击展开/折叠
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
(0,0,0,0,0)
(0,0,0,0,1)
(0,0,0,0,2)
(0,0,0,1,0)
(0,0,0,1,1)
(0,0,0,1,2)
(0,0,0,2,0)
(0,0,0,2,1)
(0,0,0,2,2)
(0,0,1,0,0)
(0,0,1,0,1)
(0,0,1,0,2)
(0,0,1,1,0)
(0,0,1,1,1)
(0,0,1,1,2)
(0,0,1,2,0)
(0,0,1,2,1)
(0,0,1,2,2)
(0,0,2,0,0)
(0,0,2,0,1)
(0,0,2,0,2)
(0,0,2,1,0)
(0,0,2,1,1)
(0,0,2,1,2)
(0,0,2,2,0)
(0,0,2,2,1)
(0,0,2,2,2)
(0,1,0,0,0)
(0,1,0,0,1)
(0,1,0,0,2)
(0,1,0,1,0)
(0,1,0,1,1)
(0,1,0,1,2)
(0,1,0,2,0)
(0,1,0,2,1)
(0,1,0,2,2)
(0,1,1,0,0)
(0,1,1,0,1)
(0,1,1,0,2)
(0,1,1,1,0)
(0,1,1,1,1)
(0,1,1,1,2)
(0,1,1,2,0)
(0,1,1,2,1)
(0,1,1,2,2)
(0,1,2,0,0)
(0,1,2,0,1)
(0,1,2,0,2)
(0,1,2,1,0)
(0,1,2,1,1)

不难发现,$3^5$ 的5维空间中空余的位置太多,非常浪费。其第一个维度取值都是0,直接退化成了4维空间,而所需人数也的确是 $0 + 1 + 2 + 2 + 2 = 7$ ,第一队完全就是吃空饷的

那么,$2^6$ 的6维空间似乎比较合理了,出6队,每队都出1人就刚好6人

到了这里,你应该也发现了,上面一大堆所做的事情是:

  1. 通过某种方式生成一串 $(a_1, a_2,…, a_n)$ ,用n队人来表示另一串数字——也就是酒桶编号

  2. 对每个酒桶编号都有唯一一组 $(a_1, a_2,…, a_n)$ 序列,它们的取值分别代表第几队第几号得来喝这桶酒。如果是第0号,该队无需派人

  3. 每个队出人的最大编号,刚好是 $\sqrt[n]{50}$ 向上取整后减去1

这听起来怎么特别耳熟呢,程序员思维已经急不可耐了:

从程序员角度去理解,也就是把0~49这50个数字,分别用 $\lceil{\sqrt[n]{50}}\rceil$ 进制去转换:

  1. 当 $n=1$ 时$\lceil{\sqrt[1]{50}}\rceil=50$, 用的是50进制
  2. 当 $n=2$ 时$\lceil{\sqrt[2]{50}}\rceil=8$, 用的是8进制
  3. 当 $n=3$ 时$\lceil{\sqrt[3]{50}}\rceil=4$, 用的是4进制
  4. 当 $n=4$ 时$\lceil{\sqrt[4]{50}}\rceil=3$, 用的是3进制
  5. 当 $n=5$ 时$\lceil{\sqrt[5]{50}}\rceil=3$, 还是3进制, 它也的确退化成了 $n=4$ 的情况
  6. 当 $n=6$ 时$\lceil{\sqrt[6]{50}}\rceil=2$, 用的是2进制, 是我们推测出的最优解6人

转换到相应的进制后,左侧高位可能是没有数字的空位
这些左边高位为空的就用0去填充对齐,最终解读编码结果:

  1. 从高位向低位依次计数,有几位就需要几个队伍
  2. 每个队伍对应的那一列有几种非0的值,那一队就需要派出几人
  3. 最终对每个队伍派出的人数求和,就是总人数

很好,这很程序员,很二进制!

程序员的解法

1. 代码和输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int wineCnt = 50; // 酒桶数
int radix = 2; // 二进制
int dimCnt = (int) Math.ceil(Math.log(50) / Math.log(radix)); // 位数(派出几队人)
String fmtStr = "%" + dimCnt + "s";
IntStream.range(0, wineCnt)
.mapToObj(idx -> Integer.toUnsignedString(idx, radix))
.map(s -> String.format(fmtStr, s))
.map(s -> s.replace(' ', '0'))
.map(s -> charsToVector(s.toCharArray()))
.forEach(System.out::println);
/**
* 把char数组以逗号作分隔符拼接, 首尾包上括号, 按字符串返回
* 省略具体实现
*/
String charToVector(char[] chars) {...}

直接上列表:

点击展开/折叠
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
(0,0,0,0,0,0)
(0,0,0,0,0,1)
(0,0,0,0,1,0)
(0,0,0,0,1,1)
(0,0,0,1,0,0)
(0,0,0,1,0,1)
(0,0,0,1,1,0)
(0,0,0,1,1,1)
(0,0,1,0,0,0)
(0,0,1,0,0,1)
(0,0,1,0,1,0)
(0,0,1,0,1,1)
(0,0,1,1,0,0)
(0,0,1,1,0,1)
(0,0,1,1,1,0)
(0,0,1,1,1,1)
(0,1,0,0,0,0)
(0,1,0,0,0,1)
(0,1,0,0,1,0)
(0,1,0,0,1,1)
(0,1,0,1,0,0)
(0,1,0,1,0,1)
(0,1,0,1,1,0)
(0,1,0,1,1,1)
(0,1,1,0,0,0)
(0,1,1,0,0,1)
(0,1,1,0,1,0)
(0,1,1,0,1,1)
(0,1,1,1,0,0)
(0,1,1,1,0,1)
(0,1,1,1,1,0)
(0,1,1,1,1,1)
(1,0,0,0,0,0)
(1,0,0,0,0,1)
(1,0,0,0,1,0)
(1,0,0,0,1,1)
(1,0,0,1,0,0)
(1,0,0,1,0,1)
(1,0,0,1,1,0)
(1,0,0,1,1,1)
(1,0,1,0,0,0)
(1,0,1,0,0,1)
(1,0,1,0,1,0)
(1,0,1,0,1,1)
(1,0,1,1,0,0)
(1,0,1,1,0,1)
(1,0,1,1,1,0)
(1,0,1,1,1,1)
(1,1,0,0,0,0)
(1,1,0,0,0,1)

前面已经说了,这是派出6个队伍,每队至多1人,没有空间浪费,也符合我们未经证明的计算公式,很好很好

2. 程序员总结

到这一步,面试官应该无话可说了,可惜当时我没想到这里来。像个程序员一般地总结一下:碰到题不要慌,编号啊编码之类的事情,多想想二进制祖宗😂

这就是毫无异议的最优解了,这就完事了?

是的,在前面被“羊宝宝”大佬启发之前,在搜索网上相关问题之前,我是这么以为的

直到我膝盖中了一箭

问题的延伸

国王、毒酒问题的诸多变种版本里,有一种是这样的:

500桶酒,其中1桶是毒酒;48小时后要举行酒会;毒酒喝下去会在之后的第23-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪一桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

诸多人推广(互相抄袭)、转发的答案是两人

什么?!两人就能搞定?肯定有什么是之前没想到的!

仔细看下两种问题之间的区别,不难发现……

欲知后事如何,且听下回分解

Java8学习笔记(1)

前言

Java8 于2014年发布,新项目基本都开始使用这个版本了。个人工作中经常使用它,有时也会和朋友讨论。讨论中略有感悟,但终归是“一时之快”。又有朋友建议我说,既然你自己理解了,又能通俗地讲出来,为什么不写下来呢?你觉得简单粗浅,但对别人来说就不一定了。

我想了想,觉得“写下来”最大的障碍是“坚持写”。自从离开校园就很少书写了,多年下来的后果就是词汇贫乏、语句零碎,偏向口语、网络语言。比如:一句万能的“卧槽”,通过不同语气音调表达不同含义,甚为好用;某些时候词不达意,找不到表达自己想法的词句;最后,就像这段话一样,啰里啰嗦废话多多。

于是,发挥特长多说废话,就开这个坑了,但愿能坚持下去。

“新”特性

所谓新特性也只是相对上个版本,5年过去也不算新了。如果面试时自称熟悉Java8,面试官大概会问都有些什么新特性,然后追问其中几条,诸如内存模型、GC以及并发、线程池、锁之类的。

口头表达(背诵)的是原理、概念,手上的才是学以致用。光说不练是假,光练不思更是蠢。这里还是按部就班,先讲个人觉得最有趣的“新”特性——函数式接口以及lambda表达式。

一. 函数式接口以及lambda表达式

1. 前情扩展

从此我假设大家都有足够的基础知识

众所周知,在Java中几乎可以在任何地方定义一个class,而在Java中几乎没有函数(function)这个概念,只能在class里面定义一个函数,而且它们一律被叫做方法(method)。这是为什么?

按C++的习惯,定义在class里面的是方法,不在class里面的叫做函数。而在Java这种“class至上”的语言中,所有东西都必定能找到它的类型,不可能存在一个定义在class外面的、被称为function的东西,更没有函数指针。一句话就是:“class是一等公民,function不是”。

但是实际运用中,我们又很需要有这种东西,能描述并自定义一类行为,并且当做参数传递给别人。

其实这种事情非常常见,例如你告诉同桌:“老师过来了就通知下我”,然后开始打瞌睡。即是说,你把 “send _通知_ to _我_” 这种具体的行动过程传递给了别人,这个行为也由别人来执行。当事件真的发生的时候,别人来进行判断、执行。

由于你睡得太死没能收到同桌的提醒,付出了一定的代价。第二天你再次告诉同桌:“老师过来了就弄醒我”,这回传递的是 “send _唤醒_ to _我_”。

那么,既然举了这个例子,难道Java8之前就无法实现吗?当然不是!

回忆(抄写)一下经典代码:

1
2
3
4
5
6
deskmate.addEventListener(new EventListener() {
@Override
public void onTeacherLaunchDetected(Event e) {
deskmate.whisper("老师来了!", me);
}
});

第二天则是:

1
2
3
4
5
6
7
8
deskmate.addEventListener(new EventListener() {
@Override
public void onTeacherLaunchDetected(Event e) {
while(me.isSleep()){
deskmate.awakeByShake(me);
}
}
});

没错,匿名内部类,为了传递一种行为,实例化出来一个描述该行为具体实现的对象,把这个对象传递给别人。

如果经常写事件驱动的程序,比如swing或者Android,应该经常能看到它。匿名内部类本身就是自定义(@Override)某类型的一个或多个方法并直接实例化出该类型的对象,而且还不给这个实现类取名字。

但匿名内部类最大的问题是使得代码逻辑分散,显得冗长,导致可读性差。而在Java8里,这些事情有所改变。

2. 函数式接口(Functional Interfaces)

在Java8 里接口里可以定义已经实现的方法。例如:

1
2
3
4
5
6
7
8
9
10
11
interface AAA {

void doSth1();

default void doSth2() {
System.out.println("invoke doSth2()");
}
static void doSth3() {
System.out.println("invoke doSth3()");
}
}

从这个角度看,接口和抽象类的界限变得更加模糊了。当然,别忘记还是有区别的。当接口里有且仅有一个抽象方法时,它可以被称作“函数式接口”。给它加上@FunctionalInterface 注解,可以让编译器检查它是否符合约定。例如经典的Runnable接口就是一个典型的函数式接口,在Java8里,它也被加上了这么一个注解:

1
2
3
4
@FunctionalInterface
public interface Runnable {
public abstract void run();
}

那么,新增这个约定没什么稀罕的,它的意义是什么?

它的意义是,给Java加上新功能的同时,不破坏原有的代码,尽力保持兼容性。说明如下:

  1. 新增了一包java.util.stream,给Java加上了Stream操作,定义了一些常用的对流进行操作的方法,而这些操作方法的入参又都是之前讲过的“某一类行为的具体操作”,使得并行操作大集合变得方便,充分发挥多核CPU特性,减少并发操作的开发难度

  2. 紧接着通过添加接口以及扩展原本就符合约定的接口,得到了一堆函数式接口用于描述行为,能与Stream互相配合。例如将某对象映射为另一对象的Function接口。如果用过guavaLists.transform(List<F> fromList, Function<? super F, ? extends T> function) 方法,应该印象深刻,当时全部都是匿名内部类来实现Function<? super F, ? extends T> function。在Java8中就新增了这个接口:

    1
    2
    3
    4
    @FunctionalInterface
    public interface Function<T, R> {
    R apply(T t);
    }
  3. 为了让原有的类支持Stream操作,需要扩展接口,并实现新增的方法。例如定义在Collection接口中的stream()方法,可以将集合转为一个stream

    1
    2
    3
    default Stream<E> stream() {
    return StreamSupport.stream(spliterator(), false);
    }

    如果按之前的规范,接口里不可有已实现的方法,那么要么在原来的基础上插入一层抽象类,在抽象类里补上实现;要么就把实现复制粘贴到所有实现类或者中间的抽象类里面。

    前者破坏力太强就不用想了,而后者是把这三行代码复制粘贴到所有Collection的实现类/抽象类里去——呃,相信我,在项目里一定不要这么干,除非你是“我挖坑别人填”的爱好者,天知道是不是哪天就成了“别人挖坑自己填”。

  4. 用lambda表达式实例化一个接口的充分必要条件就是“该接口是函数式接口”。否则将无法确定lambda表达式实现的是接口的哪一个抽象方法。同时lambda表达式也无法实例化抽象类,哪怕抽象类的确只有一个抽象方法。可以说,正是有了函数式接口,才能引入lambda表达式,否则必须对原有的Java世界进行天翻地覆的改造。也正因为有了lambda表达式,Stream 操作才好用,才有人用,不然就是“链式匿名内部类地狱”了。

可以说,Java8增加的lambda, Stream特性,就是建立在函数式接口基础上的。根本原因就是前面提到的“class是一等公民,function不是”,这符合“一切都是class”的思想,而function又恰好不是class

我相信这一定不是给Java增加lambda, Stream的最优解,依然充满了很多“为什么这也没有”、“为什么不能这么干”之类的,但我更相信它是目前不破坏原有的代码,尽力保持兼容性前提下的近似解。况且,Java也是依然出在发展中,在不断进步。

3. lambda表达式和方法引用

于是终于进入了这一段。在不少语言中,都有lambda表达式,这里也不掉书袋了。拿众所周知的Runnable接口举例:

1
2
3
4
5
6
7
8
9
10
11
// 以前的写法
threadPool.execute(new Runnable() {
@Override
public void run() {
// 随便干点啥
}
});
// lambda 的写法
threadPool.execute(() -> {
// 随便干点啥
});

看起来简洁不少,这里简述lambda语法和方法引用:

  1. 箭头->左边的()表示无需入参,因为lambda实例化接口时所需实现的方法是public abstract void run();

    1. 如果需要入参,参数用圆括号包裹,圆括号中的参数是形参,名称也不能和外部的变量重名
    2. 由于lambda形参有类型自动推断,所以一般无需显式书写类型
    3. 当只需要一个入参时,可以省略圆括号
    1
    2
    3
    4
    5
    6
    7
    8
    // 完整版
    BiFunction<Integer, Integer, Integer> sum = (Integer a, Integer b) -> {
    return a + b;
    };
    // 可简化为
    BiFunction<Integer, Integer, Integer> sum = (a, b) -> {
    return a + b;
    };
  2. 箭头->就是lambda表达式的符号,不是指针。如果你用IDE工具,点击这个符号应该能看到此处的lambda是实例化的哪一个接口, 上面的例子里,实例化的接口如下:

    1
    2
    3
    4
    @FunctionalInterface
    public interface BiFunction<T, U, R> {
    R apply(T t, U u);
    }
  1. 箭头->右边是就是方法体(body),由一对花括号包裹具体实现。当实现只有一句话时,花括号都可以省略,因此:

    1
    2
    3
    4
    // 前例可简化为
    BiFunction<Integer, Integer, Integer> sum = (a, b) -> a + b;
    // 又如打印一对值
    BiConsumer<String, Integer> bic = (name, value) -> System.out.println(name + ": " + value);
  2. 当lambda是方法体部分没有对形参做任何操作,可以进一步简化为方法引用。其符号是两个连续的英文冒号::。该符号左边表示方法所在,而右边表示所引用方法的名称,无需圆括号,自然也无需形参,这么做能使代码更加简洁,便于阅读。例如:

    1
    Consumer<Integer> printIntger = integer -> System.out.println(integer);

    直接拿到形参integer调用println()方法,即可简化为:

    1
    Consumer<Integer> printIntger = System.out::println;

    不光可以调用静态方法,构造方法、成员方法都可以。例如:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // 1. 构造方法
    Function<Integer, int[]> createIntArrayFunc = len -> new int[len];
    // 方法引用,简化后:
    Function<Integer, int[]> createIntArrayFunc = int[]::new;

    // 2. 形参自身类的成员方法
    Function<List<?>, Integer> getLenOfListBySelf = list -> list.size();
    // 方法引用,简化后:
    Function<List<?>, Integer> getLenOfListBySelf = List::size;

    // 3. 本类成员方法:
    Function<List<?>, Integer> getLenOfListByMe = list -> this.customGetSize(list);
    // 方法引用,简化后:
    Function<List<?>, Integer> getLenOfListByMe = this::customGetSize;

    // 4. 其他类成员方法:
    Function<List<?>, Integer> getLenOfListByMe = list -> service.customGetSize(list);
    // 方法引用,简化后:
    Function<List<?>, Integer> getLenOfListByMe = service::customGetSize;

写得更完整当然没问题,但在符合语言规范的前提下,适当简化代码提高可读性是更好的选择。

4. 小结

许多代码读起来都比较头疼,常常是刚读到“想干什么”之后,立刻就是具体的“怎么怎么干”,看完具体“怎么怎么干”之后,接着又回头去看接下来再干什么。

其实关键不在于怎么写,而在于怎么思考的。一个变量从被定义到被使用跨过一个屏幕的高度,对人脑的压力实在太大了,而在for循环里嵌套多层if语句块、for语句块,在里面修改一个或多个外部变量,而且还特别长。回想一下被面条式代码(Spaghetti code)支配的恐惧吧!

熟悉lambda这套之后,我最大的收获不是什么减少了for循环遍历,而是习惯把业务过程分解成一个个的“行为”,每个“行为”都尽量简单,只干一件简单明了的事。

是的,做任何事情都有一个度,你完全可以激进地重构面条式代码,但有可能得到了馄饨代码(Ravioli Code)

没有银弹,没有万能药。并不是掌握了某种语言、语法、技巧就能解决一切问题。编码的过程中多多思考,实现功能的同时,减少重复、提高可读性,才是最终目标。如果觉得困惑了,多去阅读、交流,并思考、总结。

最后举一个例子,已有一个全公司雇员信息的list,从中找到所有大于35岁的程序员,统计一下他们的工资水平。

传统的写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// List<Employee> employeeList = ...
double maxSalary = Double.NEGATIVE_INFINITY;
double minSalary = Double.POSITIVE_INFINITY;
double total = 0;
int count = 0;
for (Employee e : employeeList) {
if (e.getAge() >= 35 && e.isProgrammer()) {
double salary = e.getSalary();
maxSalary = Math.max(maxSalary, salary);
minSalary = Math.min(minSalary, salary);
total += salary;
count++;
}
}
double avgSalary = count == 0 ? 0 : total / count;

Java8 的写法:

1
2
3
4
5
6
7
8
9
// List<Employee> employeeList = ...
DoubleSummaryStatistics stats = employeeList.stream()
.filter(e -> e.getAge() >= 35)
.filter(Employee::isProgrammer)
.mapToDouble(Employee::getSalary)
.summaryStatistics();
double maxSalary = stats.getMax();
double avgSalary = stats.getAverage();
double minSalary = stats.getMin();

是不是觉得一下子省事儿了许多?下一篇再详细讨论这个吧