跳至主要內容

1227. 飞机座位分配概率

ITCharge大约 4 分钟

1227. 飞机座位分配概率open in new window

  • 标签:脑筋急转弯、数学、动态规划、概率与统计
  • 难度:中等

题目链接

题目大意

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

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

要求:计算出第 nn 位乘客坐在自己座位上的概率是多少。

说明

  • 1n1051 \le n \le 10^5

示例

  • 示例 1:
输入:n = 1
输出:1.00000
解释:第一个人只会坐在自己的位置上。
  • 示例 2:
输入: n = 2
输出: 0.50000
解释:在第一个人选好座位坐下后,第二个人坐在自己的座位上的概率是 0.5

解题思路

思路 1:数学

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

n=1n = 1 时:

  • 11 位乘客只能坐在第 11 个座位上,f(1)=1f(1) = 1

n=2n = 2 时:

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

n3n \ge 3 时:

  • 先来考虑第 11 位乘客登机情况:

    • 11 位乘客有 1n\frac{1}{n} 的概率选择坐在自己位置上,这样第 11 位到第 n1n - 1 位乘客的座位都不会被占,第 n 位乘客一定能坐到自己位置上。那么第 n 位乘客坐在自己座位上的概率为 1n1.0\frac{1}{n} * 1.0

    • 11 位乘客有 1n\frac{1}{n} 的概率选择坐在第 nn 位乘客的位置上,这样第 22 位到第 n1n - 1 位乘客的座位都不会被占,第 nn 位乘客只能坐到第 11 位乘客的位置上,那么第 nn 位乘客坐在自己座位上的概率为 1n0.0\frac{1}{n} * 0.0

    • 11 位乘客有 n2n\frac{n-2}{n} 的概率坐在第 ii 号座位上,2in12 \le i \le n - 1,每个座位被选中概率为 1n\frac{1}{n}。这样第 22 位到第 i1i - 1 位乘客的座位都不会被占。此时第 ii 位乘客,会在剩下的 n(i1)n - (i - 1) 个座位中进行选择:

      • 坐在第 11 位乘客的位置上,这样后面的乘客座位都不会被占,第 nn 位乘客一定能坐到自己位置上。

      • 坐在第 nn 个乘客的位置上,这样第 nn 个乘客肯定无法坐到自己的位置上。

      • 在第 [i+1,n1][i + 1, n - 1] 之间找个位置坐。

  • 再来考虑第 ii 位乘客登机情况:

    • ii 为乘客所面临的情况跟第 11 位乘客所面临的情况类似,只不过问题的规模数从 nn 减小到了 n(i1)n - (i - 1)

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

f(n)=1n1.0+1n0.0+1ni=2n1f(ni+1)=1n(1.0+i=2n1f(ni+1))\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}

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

nn 换为 n1n - 1,得:

$\begin{aligned} 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{aligned} $

f(n)nf(n) * nf(n1)(n1)f(n - 1) * (n - 1) 进行比较:

f(n)n=1.0+i=2n1f(ni+1)(1)f(n1)(n1)=1.0+i=2n2f(ni)(2)\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) 式相减得:

f(n)nf(n1)(n1)=i=2n1f(ni+1)i=2n2f(ni)=f(n1)\begin{aligned} & 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{aligned}

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

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

所以可以得出结论:

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

思路 1:代码

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

思路 1:复杂度分析

  • 时间复杂度O(1)O(1)
  • 空间复杂度O(1)O(1)

参考资料