目錄
1. 問題描述
2. 解法1—作為計數問題的閉式解
3. 解法2—作為計數問題的遞推表達式
4. 代碼及測試
1. 問題描述
本題來自《程式員的算法趣題》中的第17題。
男生和女生一起參加“30人31足”比賽。由于女生體力有劣勢，是以兩個女生排在一起的話整個隊伍就會在體力上處于明顯不利地位。是以原則上盡量不讓女生相鄰排列，稱沒有女生相鄰排列的排列方式為“合理”排列。
請問，當總共N個男生和女生一起排成一排時，一共有多少種合理的排列方式？
假設這裡男生之間、女生之間不考慮區分（即不考慮男生之間的相對位置的不同，也不考慮女生之間的相對位置的不同）。舉個例子，4個人（4人5足）的情況下共有8種排列方式，如下所示（B表示boy，G表示Girl）：
BBBB, GBBB, BGBB, BBGB, BBBG, GBGB, BGBG, GBBG
2. 解法1—作為計數問題的閉式解
這個問題可以當作一個計數問題來考慮，可以直接通過數學推導得到閉式(closed-form)解。
令男生人數為Nb, 女生認識為Ng，首先它們滿足關系：
(1)
由于不允許兩個女生相鄰排列，是以必然滿足（考慮Nb個男生排成一排，包括兩端在内一共有Nb+1個位置可以插入女生，即Nb個男生構成的隊列中最多可以插入Nb+1個女生以構成“合理”排列）：
(2)
結合（1）和（2）可得：
(3)
接下來，由于男生人數為Nb，包括兩端在内一共有Nb+1個空檔可以插入女生。同時又由于不允許女生相鄰排列，是以不能有兩個女生插入同一個空檔。在這個條件下，所能構成的合理的排列數的問題就轉變成了：Ng個女生放入Nb+1個位置有多少種安排方法？由于女生之間不區分，是以這是一個組合問題，總共有
，然後對所有Nf的可能取值進行求和即可得到（将N個人的隊伍的合理排列方式數記為
）：
（4）(Nf為Ng的筆誤)
3. 解法2—作為計數問題的遞推表達式
将N個人的隊伍的合理排列方式數記為
。
考慮從左往右安排隊伍，則最右邊的人為最後一個安排的人。最後的人(即第N個人)有男生和女生兩種可能性，分别讨論如下：
- 如果最後一個人為男生，則對前N-1個人的排列方式沒有限制條件。即這種情況下的排列方式等于前(N-1)個人的“合理”排列方式，也即是
程式員的算法趣題Q17：30人31足遊戲1. 問題描述2. 解法1—作為計數問題的閉式解3. 解法2—作為計數問題的遞推表達式 4. 代碼及測試 - 如果最後一個人為女生，則倒數第二個人必定為男生，進而同理可得對前N-2個人的排列方式沒有限制條件。即這種情況下的排列方式等于前(N-2)個人的“合理”排列方式，也即是
程式員的算法趣題Q17：30人31足遊戲1. 問題描述2. 解法1—作為計數問題的閉式解3. 解法2—作為計數問題的遞推表達式 4. 代碼及測試
基于以上讨論可以得到遞推關系式，如下所示：
(5)
這個遞推關系式與斐波那契數列的遞推關系式完全相同，但是本問題的解序列
的解序列并不構成标準的斐波那契數列，原因在于初始化條件不同。為了利用(5)式解出
的具體值，我們需要給出序列的最初幾個值作為初始化條件。
N=1：很顯然
，這裡我們假定允許單獨一個女生參賽（“1人2足”）
N=2：
，“BB”, “BG”, “GB”
N=3：
，“BBB”, “MBB”, “BMB”, “BBM” , “MBM”
…
是以，本問題的遞推關系式表達的解為：
……………… (6)
有興趣的讀者可以自行驗證式(4)表示的解和式(6)表示的解式完全等價的。
以上是從最後一個人倒着往前推，但是從第一個正向地往後推也可以得到相同的遞推關系。具體來說就是，假設第一個人為男生，第2個人可以為男生也可以為女生，則其後的排法與N-1的情況相同；假設第一個人為女生，第2個人必然為男生，第3個人可以為男生也可以為女生，則其後的排法與N-2的情況相同。由此可得到與式(6)相同的遞推關系。
4. 代碼及測試
程式設計計算就是以代碼的方式實作式(6)所示的遞推關系而已，可以以遞歸(recursion)的方式外加memoization來實作（代碼簡潔但是有額外計算代價），另一種方式是以疊代（iteration）的方式計算。遞歸的方式是從目标值開始從大到小反向回溯的方式進行遞推計算，而疊代（iteration）則是前向地從小到大地進行遞推計算。
另外，本序列的總連結如下，歡迎閱讀指點：
程式員的算法趣題：詳細分析和Python全解