作者:baihacker
來(lái)源:http://hi.baidu.com/feixue http://hi.csdn.net/baihacker
問(wèn)題描述:
12個(gè)高矮不同的人,排成兩排,每排必須是從矮到高排列,而且第二排比對(duì)應(yīng)的第一排的人高,問(wèn)排列方式有多少種?
這個(gè)筆試題,很YD,因?yàn)榘涯硞€(gè)遞歸關(guān)系隱藏得很深.
問(wèn)題分析:
我們先把這12個(gè)人從低到高排列,然后,選擇6個(gè)人排在第一排,那么剩下的6個(gè)肯定是在第二排.
用0表示對(duì)應(yīng)的人在第一排,用1表示對(duì)應(yīng)的人在第二排,那么含有6個(gè)0,6個(gè)1的序列,就對(duì)應(yīng)一種方案.
比如000000111111就對(duì)應(yīng)著
第一排:0 1 2 3 4 5
第二排:6 7 8 9 10 11
010101010101就對(duì)應(yīng)著
第一排:0 2 4 6 8 10
第二排:1 3 5 7 9 11
問(wèn)題轉(zhuǎn)換為,這樣的滿足條件的01序列有多少個(gè).
觀察1的出現(xiàn),我們考慮這一個(gè)出現(xiàn)能不能放在第二排,顯然,在這個(gè)1之前出現(xiàn)的那些0,1對(duì)應(yīng)的人
要么是在這個(gè)1左邊,要么是在這個(gè)1前面.而肯定要有一個(gè)0的,在這個(gè)1前面,統(tǒng)計(jì)在這個(gè)1之前的0和1的個(gè)數(shù).
也就是要求,0的個(gè)數(shù)大于1的個(gè)數(shù).
OK,問(wèn)題已經(jīng)解決.
如果把0看成入棧操作,1看成出棧操作,就是說(shuō)給定6個(gè)元素,合法的入棧出棧序列有多少個(gè).
這就是catalan數(shù),這里只是用于棧,等價(jià)地描述還有,二叉樹(shù)的枚舉,多邊形分成三角形的個(gè)數(shù),圓括弧插入公式中的
方法數(shù),其通項(xiàng)是c(2n, n)/(n+1).
在 < <計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)>>,第三版,Donald E.Knuth著,蘇運(yùn)霖譯,第一卷,508頁(yè),給出了證明:
問(wèn)題大意是用S表示入棧,X表示出棧,那么合法的序列有多少個(gè)(S的個(gè)數(shù)為n)
顯然有c(2n, n)個(gè)含S,X各n個(gè)的序列,剩下的是計(jì)算不允許的序列數(shù)(它包含正確個(gè)數(shù)的S和X,但是違背其它條件).
在任何不允許的序列中,定出使得X的個(gè)數(shù)超過(guò)S的個(gè)數(shù)的第一個(gè)X的位置.然后在導(dǎo)致并包括這個(gè)X的部分序列中,以
S代替所有的X并以X代表所有的S.結(jié)果是一個(gè)有(n+1)個(gè)S和(n-1)個(gè)X的序列.反過(guò)來(lái),對(duì)一垢一種類(lèi)型的每個(gè)序列,我們都能
逆轉(zhuǎn)這個(gè)過(guò)程,而且找出導(dǎo)致它的前一種類(lèi)型的不允許序列.例如XXSXSSSXXSSS必然來(lái)自SSXSXXXXXSSS.這個(gè)對(duì)應(yīng)說(shuō)明,不允許
的序列的個(gè)數(shù)是c(2n, n-1),因此an = c(2n, n) - c(2n, n-1).[Comptes Rendus Acad.Sci.105(Paris, 1887), 436~437]
驗(yàn)證:
其中F表示前排,B表示后排,在枚舉出前排的人之后,對(duì)應(yīng)的就是后排的人了,然后再驗(yàn)證是不是滿足后面的比前面對(duì)應(yīng)的人高的要求.
- 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;
}
結(jié)果: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)
估計(jì)出題的人也讀過(guò) < <計(jì)算機(jī)程序藝術(shù)>>吧.
PS:
另一個(gè)很YD的問(wèn)題:
有編號(hào)為1到n(n可以很大,不妨在這里假定可以達(dá)到10億)的若干個(gè)格子,從左到右排列.
在某些格子中有一個(gè)棋子,不妨設(shè)第xi格有棋子(1 <=i <=k, 1 <=k <=n)
每次一個(gè)人可以把一個(gè)棋子往左移若干步,
但是不能跨越其它棋子,也要保證每個(gè)格子至多只有一個(gè)棋子.
兩個(gè)人輪流移動(dòng),移動(dòng)不了的為輸,問(wèn)先手是不是有必勝策略.