跳转至

1227. 飞机座位分配概率#

问题描述#

有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。

剩下的乘客将会：

  • 如果他们自己的座位还空着，就坐到自己的座位上，

  • 当他们自己的座位被占用时，随机选择其他座位

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

 

示例 1：


输入：n = 1
输出：1.00000
解释：第一个人只会坐在自己的位置上。

示例 2：


输入: n = 2
输出: 0.50000
解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。

 

提示：

  • 1 <= n <= 10^5

解题思路#

假设用 \(f(n)\) 表示 \(n\) 个人时第 \(n\) 个人坐在自己座位上的概率。

  1. 如果第一个人恰好选择自己的本来的座位（概率为 \(\frac{1}{n}\)），那么第 \(n\) 个人显然会坐在自己的座位上。
  2. 如果第一个人坐在了 不是自己本来的座位也不是第 n 个人的座位上（概率为 \(\frac{n-2}{n}\)），此时我们将被第一个人所占据的座位的 原本座位主人看作是下一个选择座位的人，那么此时问题相当于 \(f(n-1)\)。因为如果第二个人选择了第一个人的座位，此时第 \(n\) 个人显然会坐在自己的座位上，或者选择除了三者（第一个人本来的座位、第 \(n\) 个人的座位以及第二个人本来的座位（被第一个人占据））之外的座位，他的选择情况与第一个人一致，只是问题规模更小。

综上所述，我们得到了递推公式：

\[ f(n) = \frac{1}{n} + \frac{n-2}{n}f(n-1) \]
\[ \begin{aligned} f(1)&=1\\ f(2)&=\frac{1}{2}\\ \end{aligned} \]

当 \(f(n-1)=\frac{1}{2}\) 时， \(f(n)=\frac{1}{n}+\frac{n-2}{n}\times\frac{1}{2}=\frac{1}{2}\)。

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

在手机上阅读