飞机座位分配概率Java
文章发布较早,内容可能过时,阅读注意甄别。
# 题目
有 n 位乘客即将登机,飞机正好有 n 个座位。第一位乘客的票丢了,他随便选了一个座位坐下。
剩下的乘客将会:
如果他们自己的座位还空着,就坐到自己的座位上,
当他们自己的座位被占用时,随机选择其他座位
第 n 位乘客坐在自己的座位上的概率是多少?
示例 1:
输入:n = 1
输出:1.00000
解释:第一个人只会坐在自己的位置上。
示例 2:
输入: n = 2
输出: 0.50000
解释:在第一个人选好座位坐下后,第二个人坐在自己的座位上的概率是 0.5。
提示:
- 1 <= n <= 10^5
# 思路
因为我们不知道乘客对应哪个座位
# 解法
class Solution {
public double nthPersonGetsNthSeat(int n) {
/*
因为我们不知道乘客对应哪个座位
因此我们直接按入场顺序给它们的座位编号
1 号乘客是 1 号座位,(ps:1 号 票丢了,并不知道自己坐 1 号座位)
2 号乘客 是 2 号座位
。。。
我们要求的是最后一位乘客 n 最终能坐到自己座位,即 n 号座位的概率
因为 1 号 票丢了,因此分析 1 号 坐不同座位的情况,它有 3 种选择
1、1 号有 1 / n 的概率 坐到 1 号座位,那么不会对 [2, n] 号乘客产生影响,因为它们都有票,那么 n 号乘客坐到自己座位的概率为 1
2、1 号有 1 / n 的概率 坐到 n 号座位,那么 n 号 肯定坐不到 n 号座位,那么概率为 0
3、1 号有 n - 2 / n 的概率 坐到 [2, n - 1] 号座位,假设是 k 号座位,
那么对于 k 号乘客来说它有 3 种选择
1、k 号有 1 / n - 1 的概率 坐到 1 号座位,那么不会对其他乘客产生影响,那么 n 号乘客坐到自己座位的概率为 1
(为什么分母是 n - 1? 因为 k 号座位被坐了,它必定不会去坐)
2、k 号有 1 / n - 1 的概率 坐到 n 号座位,那么 n 号 肯定坐不到 n 号座位,那么概率为 0
3、k 号有 n - 3 / n - 1 的概率坐到 除 1、k、n 外的座位,假设是 m 号座位
。。。
递归分析
当 n = 1 时,那么概率必定为 1
*/
if(n == 1){
return 1;
}
//注意不能直接写 1 / n, 否则结果直接为 0
return 1.0 / n + (double)(n - 2) / n * nthPersonGetsNthSeat(n - 1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 总结
- 分析出几种情况,然后分别对各个情况实现