作者:baihacker?
來源:http://hi.baidu.com/feixue http://hi.csdn.net/baihacker?

問題描述:?
12個高矮不同的人,排成兩排,每排必須是從矮到高排列,而且第二排比對應的第一排的人高,問排列方式有多少種??
這個筆試題,很YD,因為把某個遞歸關系隱藏得很深.?

問題分析:?
我們先把這12個人從低到高排列,然后,選擇6個人排在第一排,那么剩下的6個肯定是在第二排.?
用0表示對應的人在第一排,用1表示對應的人在第二排,那么含有6個0,6個1的序列,就對應一種方案.?
比如000000111111就對應著?
第一排:0 1 2 3 4 5?
第二排:6 7 8 9 10 11?
010101010101就對應著?
第一排:0 2 4 6 8 10?
第二排:1 3 5 7 9 11?
問題轉換為,這樣的滿足條件的01序列有多少個.?
觀察1的出現,我們考慮這一個出現能不能放在第二排,顯然,在這個1之前出現的那些0,1對應的人?
要么是在這個1左邊,要么是在這個1前面.而肯定要有一個0的,在這個1前面,統計在這個1之前的0和1的個數.?
也就是要求,0的個數大于1的個數.?
OK,問題已經解決.?
如果把0看成入棧操作,1看成出棧操作,就是說給定6個元素,合法的入棧出棧序列有多少個.?
這就是catalan數,這里只是用于棧,等價地描述還有,二叉樹的枚舉,多邊形分成三角形的個數,圓括弧插入公式中的?
方法數,其通項是c(2n, n)/(n+1).?

在 < <計算機程序設計藝術>>,第三版,Donald E.Knuth著,蘇運霖譯,第一卷,508頁,給出了證明:?
問題大意是用S表示入棧,X表示出棧,那么合法的序列有多少個(S的個數為n)?
顯然有c(2n, n)個含S,X各n個的序列,剩下的是計算不允許的序列數(它包含正確個數的S和X,但是違背其它條件).?
在任何不允許的序列中,定出使得X的個數超過S的個數的第一個X的位置.然后在導致并包括這個X的部分序列中,以?
S代替所有的X并以X代表所有的S.結果是一個有(n+1)個S和(n-1)個X的序列.反過來,對一垢一種類型的每個序列,我們都能?
逆轉這個過程,而且找出導致它的前一種類型的不允許序列.例如XXSXSSSXXSSS必然來自SSXSXXXXXSSS.這個對應說明,不允許?
的序列的個數是c(2n, n-1),因此an = c(2n, n) - c(2n, n-1).[Comptes Rendus Acad.Sci.105(Paris, 1887), 436~437]?

驗證:?
其中F表示前排,B表示后排,在枚舉出前排的人之后,對應的就是后排的人了,然后再驗證是不是滿足后面的比前面對應的人高的要求.

C/C++ code

#include <iostream> using namespace std;int bit_cnt(int n) {int result = 0;for (; n; n &= n-1, ++result);return result; }int main() {int F[6], B[6];int ans = 0;for (int state = 0; state < (1 << 12); ++state) if (bit_cnt(state) == 6){int i = 0, j = 0;for (int k = 0; k < 12; ++k) if (state&(1<<k)) F[i++] = k; else B[j++] = k;int ok = 1;for (int k = 0; k < 6; ++k) if (B[k] < F[k]) {ok = 0; break;}ans += ok;}cout << ans << endl;return 0; }

結果:132?
而c(12, 6)/7 = 12*11*10*9*8*7/(7*6*5*4*3*2) = 132?
注意:c(2n, n)/(n+1) = c(2n, n) - c(2n, n-1)?

估計出題的人也讀過 < <計算機程序藝術>>吧.?

PS:?
另一個很YD的問題:?
有編號為1到n(n可以很大,不妨在這里假定可以達到10億)的若干個格子,從左到右排列.?
在某些格子中有一個棋子,不妨設第xi格有棋子(1 <=i <=k, 1 <=k <=n)?
每次一個人可以把一個棋子往左移若干步,?
但是不能跨越其它棋子,也要保證每個格子至多只有一個棋子.?
兩個人輪流移動,移動不了的為輸,問先手是不是有必勝策略

總結

以上是生活随笔為你收集整理的12个高矮不同的人排成两排的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。