题目地址:https://nanti.jisuanke.com/t/41288
题目:
(1)n个人,编号1->n, 每个人一张车票,车票上写着自己的座位号,座位号=编号。
编号为1的人弄丢了自己的车票,1->n按顺序上车,由于1号手中没有车票,不知道自己的座位号,所以他可以任选一个座位,对于其他人,如果他的座位被其他人占了,他可以任选一个座位坐,问编号为n的人坐到座位号n的概率?
(2)m个人,编号1->m, 每个人一张车票,车票上写着自己的座位号,座位号=编号。
编号为1的人弄丢了自己的车票,m个人按照1->m的某种排列顺序上车,同样的,1号可以任选没有人坐的座位,对于其他人,如果他的位置被占了,他可以任选一个座位坐,问编号为n的人坐到座位号n的概率?
解题思路:
表示n个人按照编号顺序从小到大排列准备上车,第n个人坐到座位n的概率。
易推得:
(1)n≥2时,对于第1个人:
若他选择的是1号座位,那么第n个人一定能坐到座位n;
若他选择的是n号座位,那么第n个人一定不能坐到座位n;
若他选择的是k号座位(2≤k≤n-1),那么当k≥3时,编号在[2,k-1]区间内的人都能坐到自己对应的座位上,当轮到第k个人选择座位时,因为k号座位已经选过,所以他只能从1、k+1、、、n-1、n之间选择,这n-k+1个人又可以转化为nn=n-k+1,求。
所以可以推出
手算可以得出
(2)m个人,考虑编号为1的人所处的位置,若为t,那么编号在[1,t-1]内的人都能坐到自己对应的位置上,那么问题就可以转化为
可推得
又因为,故最终求得
ac代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100;
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
int t, n, m, Case = 0;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &n, &m);
double a, b;
if(n == 1) a = 1.0;
else a = 1.0/2.0;
if(m == 1) b = 1.0;
else b = (m+1)*1.0/(m*2.0);
printf("Case #%d: %.6lf %.6lf\n", ++Case, a, b);
}
return 0;
}