作者: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)
每次一個人可以把一個棋子往左移若干步,
但是不能跨越其它棋子,也要保證每個格子至多只有一個棋子.
兩個人輪流移動,移動不了的為輸,問先手是不是有必勝策略.