1. 题目

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

剩下的乘客将会：

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

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/airplane-seat-assignment-probability
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

1个人，1
2个人，0.5
n个人，分情况讨论，假设n个座位最后一个人坐自己的座位的概率为 f ( n ) f(n) f(n)

• 1、第一个人在自己位置，最后一个人在自己位置概率概率： 1 n ∗ 1 \frac{1}{n}*1 n1​∗1
• 2、第一个人在最后一个人的位置，最后一个人在自己位置概率概率： 1 n ∗ 0 \frac{1}{n}*0 n1​∗0
• 3、第一个人在 2~n-1 号位置，最后一个人在自己位置概率概率： n − 2 n ∗ f ( n − 1 ) \frac{n-2}{n}*f(n-1) nn−2​∗f(n−1)
• 所以加起来， f ( n ) = 1 n + n − 2 n ∗ f ( n − 1 ) f(n) = \frac{1}{n}+\frac{n-2}{n}*f(n-1) f(n)=n1​+nn−2​∗f(n−1)
• 数学归纳法证明， f ( n ) = 0.5 , n ≥ 2 f(n)=0.5,n\ge 2 f(n)=0.5,n≥2
• f ( n + 1 ) = 1 n + 1 + n + 1 − 2 n + 1 ∗ f ( n ) = 1 n + 1 + n + 1 − 2 n + 1 ∗ 1 2 = 2 + n + 1 − 2 2 ∗ ( n + 1 ) = 1 2 f(n+1) = \frac{1}{n+1}+\frac{n+1-2}{n+1}*f(n) = \frac{1}{n+1}+\frac{n+1-2}{n+1}*\frac{1}{2}=\frac{2+n+1-2}{2*(n+1)}=\frac{1}{2} f(n+1)=n+11​+n+1n+1−2​∗f(n)=n+11​+n+1n+1−2​∗21​=2∗(n+1)2+n+1−2​=21​,得证

• 不用数学归纳法，可以由 f ( n ) = 1 n + n − 2 n ∗ f ( n − 1 ) f(n) = \frac{1}{n}+\frac{n-2}{n}*f(n-1) f(n)=n1​+nn−2​∗f(n−1)
• 容易得到 n f ( n ) + ∑ i = 1 n − 1 f ( i ) = n nf(n) + \sum\limits_{i = 1}^{n-1}f(i) = n nf(n)+i=1∑n−1​f(i)=n

class Solution {
public:
    double nthPersonGetsNthSeat(int n) {
        double fn = 1.0, sum_f_i = 1.0;
        for (int i = 2; i <= n; ++i) {
            fn = 1 - sum_f_i/i;
            sum_f_i += fn;
        }
        return fn;
    }
};

24 ms 6 MB

class Solution {
public:
    double nthPersonGetsNthSeat(int n) {
        return n==1 ? 1.0 : 0.5;
    }
};

0 ms 5.8 MB