金刚坐飞机问题

问题：

    现在有一班飞机将要起飞，乘客们正准备按机票号码（1, 2, 3, …N）依次排队登机。突然来了一只大猩猩（对，他叫金刚）。他也有飞机票，但是他插队第一个登上了飞机，然后随意地选了一个座位坐下了1。根据社会的和谐程度，其他的乘客有两种反应：

1. 乘客们都义愤填膺，“既然金刚同志不遵守规定，为什么我要遵守？”他们也随意地找位置坐下，并且坚决不让座给其他乘客。

2. 乘客们虽然感到愤怒，但还是以“和谐”为重，如果自己的位置没有被占领，就赶紧坐下，如果自己的位置已经被别人（或者金刚同志）占了，就随机地选择另一个位置坐下，并开始闭目养神，不再挪动位置。

那么，在这两种情况下，第 i 个乘客（除去金刚同志之外）坐到自己原机票位置的概率分别是多少？

1） 由于是随机的，则可用组合计数

    排列i 在 位上为 ： (n-1)!

    样本总体为：       n!

    第 i 个乘客（除去金刚同志之外）坐到自己原机票位置的概率分别是: 1/n

2)  概率问题。首先搞清楚一点，0号是个金刚，他不会专门去找自己的位置坐，而后面上飞机的人都是               知道自己的位置的，如果被占了他才会去随便找地方坐。也就是说如果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; }