【编程之美】金刚坐飞机问题

问题：

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

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

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

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

1

class

第一题：

因为每位乘客（包括金刚）都是随机的，问题等同于抽奖问题，先到先抽，即第 i 个乘客抽到自己的座位的概率为1/N。

2

class

第二题：

因为每位乘客（包括金刚）都是随机的，问题等同于抽奖问题，先到先抽，即第 i 个乘客抽到自己的座位的概率为1/N。对对对得得得地对地导弹 顶顶顶顶

用 F(i, n) 表示当座位总数为n时，第 i 个乘客坐到自己原位置的概率。根据全概率公式，得

其中 P(K=j) 表示金刚坐在位置j上，P(i | K=j) 是条件概率，表示当金刚坐在位置 j 上时，第 i 个乘客坐到自己原位置的概率。显然 P(K=j)=1/n，现在来分析 P(i | K=j)。

1、金刚若挑自己的座位或选的座位在第i个座位后（即 i < j），则第 i 个乘客肯定能坐到原来的座位。此时 P(i │ K=j) = 1；

2、金刚若挑选的座位在第 i 个座位前，（即 i > j），则第j个乘客除非坐到金刚的座位，不然就会抢其他人的座位，因为他的行为和金刚相似，可以将他当做金刚处理。去除前 j 个座位，剩下的座位和乘客再按原大小排序重新从1开始编号，则先前的第 i 个乘客，其座位号变为 i-j，新的总座位数变为 n-j。所以得 P(i │ K=j) = F(i-j, n-j)。

由上分析得：

再取 n+1 和 i+1 代入上式并与原式相减得：

code也是一种艺术，它能展现出自己的美。