1227. Airplane Seat Assignment Probability

今天的题目是1227. Airplane Seat Assignment Probability。

比较简单的题目，我的思路大概是这样的。

先假设f(n)为有 n 个人时，第 n 个人坐到自己位置的概率。

首先，第 1 个人随机选位置的时候，可能有三种情况：

1. 选到了自己的位置，那么后面就不会有人发现自己座位被做了，此时第 n 个人一定会坐到自己的位置。
2. 选到了第 n 个人的位置，这时第 n 个人就会坐到第 1 个人的位置上。
3. 选到了第 k 个人位置，这时，第 k 个人前面的（除了第一个人）都坐到了自己的位置，直到第 k 个人时，问题转化求解f(n-k+1)。

因此，我们可以列出下面的递推公式：

$$
f(n) = \left{
\begin{aligned}
1.0 &, & n == 1 \
\frac 1 n (1.0 + 0 + \sum_{k=2}^{n-1}f(n-k+1)) &, & n!=1
\end{aligned}
\right.
$$

对第二个公式进一步化简得到：

$$
\begin{aligned}
f(n) = & \frac 1 n (1.0 + 0 + \sum_{k=2}^{n-1}f(n-k+1)) \
= & \frac 1 n (f(1) + \sum_{k=2}^{n-1}f(k)) \
= & \frac{1}{n} \sum_{k=1}^{n-1}f(k)
\end{aligned}
$$

因此递推公式可以写成：

$$
f(n) = \left{
\begin{aligned}
1.0 &, & n == 1 \
\frac{1}{n} \sum_{k=1}^{n-1}f(k) &, & n!=1
\end{aligned}
\right.
$$

根据递推公式可以写出如下代码：

double nthPersonGetsNthSeat(int n) {
	double sum = 1.0;
	for(int k = 2;k <= n;k++) {
		res = sum / k;
		sum += res;
	}
	return res;
}

我们将一些值代入到公式中可以发现这样一个事情：

$$
\begin{aligned}
f(2) & = \frac{1}{2} f(1) \
f(3) & = \frac{1}{3} (f(1) + f(2)) = \frac{1}{2} f(1) \
… & \
f(n) & = \frac{1}{n} (f(1) + f(2) + … + f(n-1) ) \
& = \frac{1}{n} (f(1) + \frac{1}{2}f(1) + … + \frac{1}{2}f(1)) \
& = \frac{1}{n} (f(1) + \frac{n-2}{2}f(1)) \
& = \frac{1}{2} f(1)
\end{aligned}
$$

因此递推公式进一步简化成：

$$
f(n) = \left{
\begin{aligned}
1.0 &, & n == 1 \
\frac{1}{2} f(1) &, & n!=1
\end{aligned}
\right.
$$

因此，代码如下：

double nthPersonGetsNthSeat(int n) {
	return n > 1 ? 0.5 : 1.0;
}