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)
完事了，就这么简单...
很有意思的一道题,完全依靠数学公式的推导。
#include <stdio.h> #include <stdlib.h> 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); } return 0; }