傻子坐飞机(概率问题)

Description

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

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)

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

#include #include     int main() { int i, k, n, m; scanf("%d%d", &n, &m); for (i = 0; i < m; i++) { scanf("%d", &k); printf("%d/%d\n", n-k+1, n-k+2); } //system("pause"); return 0; }