《編程之美》讀書(shū)筆記13： 4.1 金剛坐飛機(jī)問(wèn)題

問(wèn)題：

    現(xiàn)在有一班飛機(jī)將要起飛，乘客們正準(zhǔn)備按機(jī)票號(hào)碼（1, 2, 3, …N）依次排隊(duì)登機(jī)。突然來(lái)了一只大猩猩（對(duì)，他叫金剛）。他也有飛機(jī)票，但是他插隊(duì)第一個(gè)登上了飛機(jī)，然后隨意地選了一個(gè)座位坐下了1。根據(jù)社會(huì)的和諧程度，其他的乘客有兩種反應(yīng)：

1. 乘客們都義憤填膺，“既然金剛同志不遵守規(guī)定，為什么我要遵守？”他們也隨意地找位置坐下，并且堅(jiān)決不讓座給其他乘客。

2. 乘客們雖然感到憤怒，但還是以“和諧”為重，如果自己的位置沒(méi)有被占領(lǐng)，就趕緊坐下，如果自己的位置已經(jīng)被別人（或者金剛同志）占了，就隨機(jī)地選擇另一個(gè)位置坐下，并開(kāi)始閉目養(yǎng)神，不再挪動(dòng)位置。

那么，在這兩種情況下，第 i 個(gè)乘客（除去金剛同志之外）坐到自己原機(jī)票位置的概率分別是多少？

對(duì)問(wèn)題一，每個(gè)人都是隨機(jī)選擇座位，任意一個(gè)人坐在指定座位的概率相同，因而第i個(gè)乘客坐在其座位的概率是 1/n。

對(duì)問(wèn)題二，答案和金剛的原來(lái)座位編號(hào)有關(guān)。不妨先去除金剛的座位，將乘客（根據(jù)機(jī)票號(hào)）和剩下的座位，按原大小順序從1開(kāi)始重新編號(hào)。用F(i，n)表示在新排列中（共有n-1個(gè)乘客座位和金剛原來(lái)的座位），新的第i個(gè)乘客坐在其原來(lái)座位的概率，則在n個(gè)座位中：

① 金剛?cè)籼糇约旱淖换蜻x的座位在第i個(gè)座位后（共有n-i個(gè)座位滿足這個(gè)條件），則第i個(gè)乘客肯定能坐到原來(lái)的座位；

② 金剛?cè)籼暨x的座位在第i個(gè)座位前，不妨假設(shè)為j，則第j個(gè)乘客除非坐到金剛的座位，不然就會(huì)搶其他人的座位，因?yàn)樗男袨楹徒饎傁嗨疲梢詫⑺?dāng)做金剛處理。去除前j個(gè)座位，剩下的座位和乘客再按原大小排序重新從1開(kāi)始編號(hào)，則先前的第i個(gè)乘客，其座位號(hào)變?yōu)?span lang=EN-US>i-j，新的總座位數(shù)變?yōu)?span lang=EN-US>n-j。因而可得公式：

用 G(i, n)表示原排列中，第i個(gè)乘客坐到自己座位的概率，假設(shè)金剛的座位編號(hào)為j。

若 i<j 則   G(i,n)=F(i,n)= (n-i)/(n+1-i)。

若 i>j 則   G(i,n)=F(i-1,n)= (n+1-i)/(n+2-i) 。

類似題：

“約瑟芬環(huán)：n個(gè)人，編號(hào)為0到n-1，圍成一圈，從編號(hào)為0的開(kāi)始，從1開(kāi)始報(bào)數(shù)，所有報(bào)到m的出列，下一個(gè)人從1開(kāi)始繼續(xù)報(bào)數(shù)。求最后一個(gè)人的編號(hào)。”