飞机座位表分配
题型描述
递推式求概率
题目描述&数据范围
题解
设 $f(n)$ 表示第 $n$ 个人坐在自己座位上的概率
$\frac{1}{n}$ 的概率，当第一个人坐在自己座位上时，$f(n)=1$
$\frac{1}{n}$ 的概率，当第一个人坐在第 $i$ 个人的座位上时，$f(n)=0$
$\frac{n-2}{n}$ 的概率，当第一个人坐在 $[2,n-1]$ 的位置上时，假设第 $1$ 个人坐在 第 $t$ 位
则 $[2,t-1]$ 的人都坐在自己位置上，而第 $t$ 个人则有 $n-t+1$ 个可选位置
若坐在 $1$ 号位，则相当于两人交换位置，$f(n)=1$
若坐在 $n$ 号位，则 $f(n)=0$
若坐在其它位置，则问题再次缩小
由此可见，坐在 $[2,n-1]$ 中的 $t$ 时，$f(n)$ 缩小至 $f(n-t+1)$，得
$$
f(n)=\frac{1}{n}*1+\frac{1}{n}*0+\frac{1}{n}*\sum_{i=2}^{n-1}f(n-i+1)
$$
由于直接计算会达到 $n^2$ 的复杂度，考虑求解递推式
$$
n*f(n)=1+\sum_{i=2}^{n-1}f(n-i+1)
$$
$$
(n-1)*f(n-1)=1+\sum_{i=2}^{n-2}f((n-1)-i+1)
$$
相减得到
$$
n*f(n)-(n-1)*f(n-1)=f(n-1)
$$
$$
f(n)=f(n-1)
$$
而 $f(1)=1$ 为特殊情况
所以得到
$$
f ( x ) = \begin {cases}
1 & x = 1 \\
0.5 & x >= 2
\end {cases}
$$
