1227. 飞机座位分配概率

1227. 飞机座位分配概率 #

  • 标签:数学、动态规划
  • 难度:中等

题目大意 #

给定一个整数 n,代表 n 位乘客即将登飞机。飞机上刚好有 n 个座位。第一位乘客的票丢了,他随便选择了一个座位坐下。

则剩下的乘客将会:

  • 如果自己的座位还空着,就坐到自己的座位上,
  • 如果自己的座位被占用了,就随机选择其他座位

问:第 n 位乘客坐在自己座位上的概率是多少。

解题思路 #

我们按照乘客的登机顺序为乘客编下号:1~n,我们用 f(n) 来表示第 n 位乘客登机时,坐在自己座位上的概率。先从简单的情况开始考虑:

当 n = 1,第 1 位乘客只能坐在第 1 个座位上,$f(1) = 1$。

当 n = 2:

  • 第 1 位乘客有 $\frac{1}{2}$ 的概率选中自己的位置,第 2 位乘客一定能坐到自己的位置上,则第 2 位乘客坐在自己座位上的概率为 $\frac{1}{2} * 1.0$。
  • 第 1 位乘客有 $\frac{1}{2}$ 的概率坐在第 2 位乘客的位置上,第 2 位乘客只能坐到第 1 位乘客的位置上,那么第 2 位乘客坐在自己座位上的概率为 $\frac{1}{2} * 0.0$。
  • 综上,$f(2) = \frac{1}{2} * 1.0 + \frac{1}{2} * 0.0 = 0.5$。

当 $n \ge 3$ 时,先来考虑第 1 位乘客登记情况:

  • 第 1 位乘客有 $\frac{1}{n}$ 的概率选择坐在自己位置上,这样第 1 位到第 n - 1 位乘客的座位都不会被占,第 n 位乘客一定能坐到自己位置上。那么第 n 位乘客坐在自己座位上的概率为 $\frac{1}{n} * 1.0$。
  • 第 1 位乘客有 $\frac{1}{n}$ 的概率选择坐在第 n 位乘客的位置上,这样第 2 位到第 n - 1 位乘客的座位都不会被占,第 n 位乘客只能坐到第 1 位乘客的位置上,那么第 n 位乘客坐在自己座位上的概率为 $\frac{1}{n} * 0.0$。
  • 第 1 位乘客有 $\frac{n-2}{n}$ 的概率坐在第 i 号座位上,$2 \le i \le n - 1$,每个座位被选中概率为 $\frac{1}{n}$。这样第 2 位到第 i - 1 位乘客的座位都不会被占。此时第 i 位乘客,会在剩下的 $n - (i - 1)$ 个座位中进行选择:
    • 坐在第 1 位乘客的位置上,这样后面的乘客座位都不会被占,第 n 位乘客一定能坐到自己位置上。
    • 坐在第 n 个乘客的位置上,这样第 n 个乘客肯定无法坐到自己的位置上。
    • 在第 $[i + 1,n - 1]$ 之间找个位置坐。

上面第 i 位乘客所面临的情况跟第 1 位乘客所面临的情况类似,只不过问题的规模数从 n 减小到了 $n - (i - 1)$。

那么综合上面情况,可以得到 $f(n),(n \ge 3)$ 的递推式:

$\begin{aligned} f(n) & = \frac{1}{n} * 1.0 + \frac{1}{n} * 0.0 + \frac{1}{n} * \sum_{i = 2}^{n-1} f(n - i + 1) \cr & = \frac{1}{n} (1.0 + \sum_{i = 2}^{n-1} f(n - i + 1)) \end{aligned} $

接下来我们从等式中寻找规律,消去 $\sum_{i = 2}^{n-1} f(n - i + 1))$ 部分。

将 $n$ 换为 $n - 1$,得:

$\begin{align} f(n - 1) & = \frac{1}{n - 1} * 1.0 + \frac{1}{n - 1} * 0.0 + \frac{1}{n - 1} * \sum_{i = 2}^{n-2} f(n - i) \cr & = \frac{1}{n - 1} (1.0 + \sum_{i = 2}^{n-2} f(n - i)) \end{align} $

将 $f(n) * n$ 与 $f(n - 1) * (n - 1)$ 进行比较:

$\begin{aligned} f(n) * n & = 1.0 + \sum_{i = 2}^{n-1} f(n - i + 1)) & (1) \cr f(n - 1) * (n - 1) & = 1.0 + \sum_{i = 2}^{n-2} f(n - i) & (2) \end{aligned}$

将上述 (1)、(2) 式相减得:

$\begin{align} & f(n) * n - f(n - 1) * (n - 1) & \cr = & \sum_{i = 2}^{n-1} f(n - i + 1) - \sum_{i = 2}^{n-2} f(n - i) \cr = & f(n-1) \end{align}$

整理后得:$f(n) = f(n - 1)$。

已知 $f(1) = 1$,$f(2) = 0.5$,因此当 $n \ge 3$ 时,$f(n) = 0.5$。

所以可以得出结论:

$f(n) = \begin{cases} 1.0 & n = 1 \cr 0.5 & n \ge 2 \end{cases}$

代码 #

1
2
3
4
5
6
class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n == 1:
            return 1.0
        else:
            return 0.5

参考资料 #

本站总访问量  次  |  您是本站第  位访问者