# 如厕问题

> source: 文章/toilet-problem/index.md

# 如厕问题

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

<!-- more -->

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

![toilet](https://mdstore.oss-cn-beijing.aliyuncs.com/markdown/toilet.png)

## 初探

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

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

我们可以列举一下情况：

| 人数 | 便池数 | 分布情况                      |
| ---- | ------ | ----------------------------- |
| 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，貌似就不满足男生隔一个空位分布的规律了

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

<center><iframe width="560" height="315" src="//player.bilibili.com/player.html?aid=926593567&bvid=BV1RT4y1j7pP&cid=218140360&p=1&autoplay=0&muted=true" scrolling="no" border="0" frameborder="no" framespacing="0" allowfullscreen="true"> </iframe></center>

## 递推

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

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

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

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

(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](https://mdstore.oss-cn-beijing.aliyuncs.com/markdown/relationship%20npm.png)

```python
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个便池的设计可能更为实用
