最新消息:点击查看大S的省钱秘笈

傻子坐飞机(概率问题)

编程相关 Slyar 91浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

09-12-05网络赛的一道题,概率公式的推导及化简。

Description

有一个架载人为n(2<=n<=1000)的飞机,有n个旅客上机。第一个旅客是个傻子,他随便找了一个位置坐下来;第二个旅客上机后,如果发现他的位置被占,那么他也随便找一个位置坐下来,所有的乘客都是如此。现在问你第 k(1<k<=n)个人上飞机时,他能坐在他自己位置上的概率是多少?

Input

单组测试数据。
首先一组n,m分别表示飞机有n个座位、有m(m<=1000)次查询。
接下来m个数,每个数表示他是第k(2<=k<=n)个人。

Output

输出相应的概率,要求用以最简分数的形式输出(即分子和分母没有不是1的公约数)。

Sample Input

100 1
100

Sample Output

1/2

Slyar:概率问题。首先搞清楚一点,1号是个傻子,他不会专门去找自己的位置坐,而后面上飞机的人都是知道自己的位置的,如果被占了他才会去随便找地方坐。也就是说如果1号恰好坐对了自己的位置,那后面的所有人都能坐对。

假设一共有100名乘客,我们令F(k)为第k个乘客坐不到自己位置的概率,他坐不到自己位置的原因是之前有某个乘客坐了他的位置,我们从k=2开始考虑:

F(2) = 1/100    //1号(傻子)坐到2号的位置,概率是1/100

F(3) = 1/100 + F(2)*(1/99) //可能是1号坐了3号的位置,也可能是2号坐了3号的位置

F(4) = 1/100 + F(2)*(1/99) + F(3)*(1/98) //被1号占+被2号占+被3号占

F(5) = 1/100 + F(2)*(1/99) + F(3)*(1/98) + F(4)*(1/97)

很明显的一个递推过程,而且可以发现:

F(3) = F(2)*(1+1/99)

F(4) = F(3)*(1+1/98)

推广一下,一共有N名乘客,则F(K)的表达式:

F(k) = (1/N)*(1+1/(N-1))*(1+1/(N-2))*(1+1/(N-3))...(1+1/(N-k+3))*(1+1/(N-k+2))

F(k) = 1 / (N-k+2)

所以k能坐上自己座位的概率就是:

1 - F(k) = (N-k+1) / (N-k+2)

完事了,就这么简单...

转载请注明:Slyar Home » 傻子坐飞机(概率问题)

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (1)

  1. 请问你是怎么推知 F(k) = (1/N)*(1+1/(N-1))*(1+1/(N-2))*(1+1/(N-3))...(1+1/(N-k+3))*(1+1/(N-k+2)) = 1 / (N-k+2) 的? 省略号前面、后面的式子分子分母都可以消掉,但是怎么确定能刚好接起来呢?
    liulishuo5年前 (2012-04-25)回复