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）
3. 解法2—仍然作為一個計數問題
將N個人的隊伍的合理排列方式數記為
，
考慮從左往右安排隊伍，則最右邊的人為最后一個安排的人，最后的人(即第N個人)有男生和女生兩種可能性，分別討論如下：
- 如果最后一個人為男生，則對前N-1個人的排列方式沒有約束條件，即這種情況下的排列方式等于前(N-1)個人的“合理”排列方式，也即是
- 如果最后一個人為女生，則倒數第二個人必定為男生，進而同理可得對前N-2個人的排列方式沒有約束條件，即這種情況下的排列方式等于前(N-2)個人的“合理”排列方式，也即是
基于以上討論可以得到遞推關系式，如下所示：
(5)
這個遞推關系式與斐波那契數列的遞推關系式完全相同，但是本問題的解序列
的解序列并不構成標準的斐波那契數列，原因在于初始化條件不同，為了利用(5)式解出
的具體值，我們需要給出序列的最初幾個值作為初始化條件，
N=1：很顯然
，這里我們假定允許單獨一個女生參賽（“1人2足”）
N=2：
，“BB”, “BG”, “GB”
N=3： ，“BBB”, “MBB”, “BMB”, “BBM” , “MBM”
…
因此，本問題的遞推關系式表達的解為：
……………… (6)
有興趣的讀者可以自行驗證式(4)表示的解和式(6)表示的解式完全等價的，
4. 解法3—編程解法
To be added.
另外，本序列的總鏈接如下，歡迎閱讀并相互討論：
程式員的演算法趣題：詳細分析和Python全解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294311.html
標籤：其他
上一篇：C語言——猜游戲