有 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
一看到这种题就是要数学分析
搞个函数f(n),很明显有三种情况
1
0.5
f(n-i+1)
我们分析f(n-i+1),发现有
f(n) = 1/n + 0 + 1/n * (f(n-1) + f(n-2) + ... + f(2)) = 1/n * (f(n-1) + f(n-2) + ... + f(2) + 1) = 1/n * (f(n-1) + f(n-2) + ... + f(2) + f(1))*****（1）
f(n-1) = 1/(n-1) * (f(n-2) + f(n-3) + ... + f(1))*****（2）
(1) ,(2) 两边分别同乘 n 和 n - 1
n * f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(1)******(3)
(n-1) * f(n-1) = f(n-2) + f(n-3) + ... + f(1)******(4)
(3)-(4)得
n * f(n) - (n-1)*f(n-1) = f(n-1)
=>f(n)=f(n-1)
这就爽了
class Solution: def nthPersonGetsNthSeat(self, n: int) -> float: return 1 if n==1 else .5