[1227] 飞机座位分配概率

递归

details

思路：

我们使用递归来计算第 n 位乘客坐在自己座位上的概率。

如果 n = 1，概率为 1.0，因为只有一个人，必定坐在自己的座位上。
如果 n > 1，则第一个乘客有 n 种选择座位的方式：
- 若第一个乘客选择了自己的座位（概率为 1/n），则剩余的 n-1 位乘客按顺序坐下，此时最后一位乘客坐到自己座位的概率等于 1.0。
- 若第一个乘客选择了第 k 位乘客的座位（概率为 1/n），那么问题变成 n-1 位乘客的问题（因为此时第 k 位乘客没有自己的座位，需要随机选择一个空座位）。因此，此时第 n 位乘客坐到自己座位上的概率等于 f(n-1)。

递推关系式：

当 n = 1 时，f(1) = 1.0。
当 n > 1 时，f(n) = (1/n) * 1.0 + (n-2)/n * f(n-1)。

递归代码实现（JavaScript）：

var nthPersonGetsNthSeat = function (n) {
    // 递归基：n=1 时，直接返回 1
    if (n === 1) return 1.0;
    return 1 / n + ((n - 2) / n) * nthPersonGetsNthSeat(n - 1);
};

数学归纳

details

归纳推导：

n = 1 时，乘客必然坐在自己的座位上，概率为 1。
n = 2 时：
- 第一个乘客有 50% 的概率选择 1 号座位或 2 号座位。
- 如果他选择了 1 号座位，第二个乘客可以直接坐到自己的座位上，概率是 1。
- 如果他选择了 2 号座位（即第二个乘客的座位），第二个乘客只能随机选择第一个乘客的座位，概率是 0。
- 因此，最终的概率是 0.5。
n = 3 时：
- 第一个乘客有三种可能：
  - 他选择自己的座位，剩下两位乘客按顺序入座，最后一位乘客坐到自己的座位上，概率是 1。
  - 他选择了最后一位乘客的座位，最后一位乘客不能坐到自己的座位上，概率是 0。
  - 他选择了第 2 位乘客的座位，这时第 2 和第 3 位乘客的情况与 n = 2 的情形相同，因此此时的概率是 0.5。
由此可推得递推公式：
- 当 n = 3 时，最终概率为 (1/n) * 1 + (1/n) * 0 + (1/n) * 0.5，即 1/3 + 1/6 = 0.5。

推广到一般情况：

当 n 较大时，第一个乘客要么选择自己的座位，要么选择其他人的座位。
- 如果第一个乘客选择了自己的座位，那么问题简化为 n-1 位乘客依次入座。
- 如果第一个乘客选择了第 k 位乘客的座位（1 < k < n），则第 k 位乘客的入座问题与 n-1 的情形相同。

经过归纳和递推，可以得出结论：

无论 n 的大小，第 n 位乘客坐在自己座位上的概率始终是 0.5。

代码实现（JavaScript）：

var nthPersonGetsNthSeat = function (n) {
    return n === 1 ? 1.0 : 0.5;
};

复杂度分析：

时间复杂度: O(1)，因为该算法直接返回结果，无需复杂计算。
空间复杂度: O(1)，只需常量空间存储中间结果。

迭代实现

details

var nthPersonGetsNthSeat = function (n) {
    if (n === 1) return 1.0; // 基础情况

    // 从 n=2 开始，逐步计算到 n
    let result = 1.0; // 初始值 f(1) = 1.0
    for (let i = 2; i <= n; i++) {
        result = 1 / i + ((i - 2) / i) * result;
    }
    return result;
};