今天的题目是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)={1.0,n==11n(1.0+0+k=2n1f(nk+1)),n!=1f(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.

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

f(n)=1n(1.0+0+k=2n1f(nk+1))=1n(f(1)+k=2n1f(k))=1nk=1n1f(k)\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)={1.0,n==11nk=1n1f(k),n!=1f(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;
}

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

f(2)=12f(1)f(3)=13(f(1)+f(2))=12f(1)...f(n)=1n(f(1)+f(2)+...+f(n1))=1n(f(1)+12f(1)+...+12f(1))=1n(f(1)+n22f(1))=12f(1)\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)={1.0,n==112f(1),n!=1f(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;
}

作者:wuxiaobai24

发表日期:10/11/2020

本文首发地址:1227. Airplane Seat Assignment Probability

版权声明:CC BY NC SA 4.0

本站总访问量次 本站访客数人次

Design by wuxiaobai24. Power by Gatsby.js. The website content is licensed CC BY NC SA 4.0.

You can find the source code in Github.