🟢 如厕问题\#

一个递归的数学问题，最后我们能够找到最优解

我们知道厕所的小便区通常由一排立式小便器构成，一般情况下，小便器并排排列且由一块隔板隔开

toilet

初探\#

我们发现，小便器的利用情况通常不是随机分布的，而是男生们有意识地选择的，其中最突出的一点是，在空位足够的情况下，男生之间会至少相隔一个空位，否则将会感到不适以至于尿不出来，甚至有的男生宁愿站着等，直到空出这样一个满足条件的空位

于是上厕所的时候我就在想：厕所在很多情况下并不是达到最佳利用状态的，如果让我来设计厕所，应该怎样设计能让便池的利用率尽可能大呢？

我们可以列举一下情况：

人数	便池数	分布情况
1	1	｜1｜
2	2	｜1｜0｜1｜
3	5	｜1｜0｜1｜0｜1｜
4	8	｜1｜0｜1｜0｜1｜0｜0｜1｜
5	9	｜1｜0｜1｜0｜1｜0｜1｜0｜1｜

我们发现人数到了4，貌似就不满足男生隔一个空位分布的规律了

毕导的这期视频也恰好聊到了这个问题

递推\#

为了解决这个问题，我们需要将这个问题用数学语言精确地描述一遍

假设厕所有$n$个便池，现在有$m$个男生分别来上厕所，$m$与$n$之间满足一定的函数关系 $$ m = f(n) $$ 现在男生的行为满足以下条件：

男生总是走到离自己最近的可选空位
男生为了避免尴尬，总是会选择离别的男生尽可能远的空位
每个男生之间必须至少有一个空位

有了这三个条件，我们来尝试讨论一下解析解

(1)若$n$为奇数，我们可以发现，离两侧便池最远的中间的空位只有1个，这个时候第三个男生必然会占用这个位置 $$ \begin{matrix} 1 \quad |1|\ 3\quad |1|0|1|\ 5\quad|1|0|1|0|1|\ \quad|1|0|1|0|1|0|1|\ 9\quad |1|0|1|0|1|0|1|0|1|\ \end{matrix} $$ 我们发现，正是因为男生必定会占据中间这个位置，所以这种隔一个分布的最优占法在$n=7$时不存在

当我们从中间分开时，我们发现这形成了一个递归式：以$n=9$为例，我们将中间视为最右边，就可以得到$n=5$的情况，而5又可以分解为3的情况，3分解成1.现在我们好像就发现了规律

对于最中间有人的情况，左右两边有$f(\frac{n+1}{2})$，这时 $$ f(n) = 2f(\frac{n+1}{2})-1 $$ (2)若$n$为奇数，我们按照相同的思想，假设男生必定会选择中间两个空位中靠左的一个

则对左边，能容纳下$f(\frac{n}{2})$

对右边，由于比左边多了一个空位，则能容纳下$f(\frac{n}{2}+1)$

同样，我们要减去中间算重复的一个人 $$ f(n) = f(\frac{n}{2})+f(\frac{n}{2}+1)-1 $$ 于是我们得到了这样的递推式： $$ f(n)= \left{ \begin{align} 2f(\frac{n+1}{2})-1 ,\quad n为奇数\ f(\frac{n}{2})+f(\frac{n}{2}+1)-1,n为偶数 \end{align} \right. $$

全貌\#

有了递推公式，我们可以尝试绘制出这个函数的图像

注意我们之前的推导，3在规则下是一个特例，因为3首先必须遵从条件2，再遵从条件3

于是我们就可以得到下面的图像，利用率总是在振荡的

relationship npm

import numpy as np
"""
对于n
如果n为奇数：
    f(n) = 2f((n+1)/2) - 1
如果n为偶数：
    f(n) = f(n)/2 + f(n/2+1) - 1
"""

def f(n):
    if n == 1:
        return 1
    if n == 2:
        return 1
    if n == 3:
        return 2
    elif n % 2 == 1:
        return 2 * f((n+1)/2) - 1
    elif n % 2 == 0:
        return f(n/2) + f(n/2+1) - 1

n = np.arange(1, 10000) # linspace 生成的是浮点数数组
vf = np.vectorize(f) # 向量化，使f能接受向量作为输入
m = vf(n)
p = m/n
from matplotlib import pyplot as plt
plt.rc('font', family = 'Songti SC')

# 创建一个图和两个子图
fig, axs = plt.subplots(2, 1, figsize=(10, 10))

# 第一个子图为n和m的关系
axs[0].plot(n, m)
axs[0].set_title('便池数与能容纳下的人数的关系')
axs[0].set_xlabel('便池数n')
axs[0].set_ylabel('能容纳下的人数m')

# 第二个子图为n和p的关系
axs[1].plot(n, p)
axs[1].set_title('便池数与人均便池数的关系')
axs[1].set_xlabel('便池数n')
axs[1].set_ylabel('人均便池数p')

# 调整子图之间的间距
plt.tight_layout()
# 显示图表
plt.show()

结论\#

对于一般的厕所来说，5个或9个便池的设计可能更为实用