首先看一道筆試題：
這個題的答案是垄琐，根據(jù)卡特蘭數(shù)公式赶袄，所有的輸出總數(shù)為5次，減掉3(標(biāo)識符不能數(shù)字開頭)開頭的2個猴娩，所以最終答案是3個阴幌。
那么什么是卡特蘭數(shù)呢？
卡特蘭數(shù)：規(guī)定C0＝1卷中，而C1＝1矛双，C2＝2，C3＝5蟆豫，C4＝14议忽，C5＝42，C6＝132十减，C7＝429栈幸，C8＝1430，C9＝4862帮辟，C10＝16796速址，C11＝58786，C12＝208012织阅，C13＝742900壳繁，C14＝2674440，C15＝9694845····································
原理如下：
令h(0)=1,h(1)=1，catalan數(shù)滿足遞推式[1]：h(n)= h(0)h(n-1)+h(1)h(n-2) + ... + h(n-1)h(0) (n>=2)
例如：h(2)=h(0)h(1)+h(1)h(0)=11+11=2 h(3)=h(0)h(2)+h(1)h(1)+h(2)h(0)=12+11+21=5
另類遞推式： h(n)=h(n-1)(4n-2)/(n+1);
遞推關(guān)系的解為： h(n)=C(2n,n)/(n+1) (n=0,1,2,3,...)
遞推關(guān)系的另類解為： h(n)=C(2n,n)-C(2n,n+1)(n=0,1,2,3,...)
C語言應(yīng)用：
void catalan() //求卡特蘭數(shù)
{
int i, j, len, carry, temp;
a[1][0] = b[1] = 1;
len = 1;
for(i = 2; i <= 100; i++)
{
for(j = 0; j < len; j++) //乘法
a[i][j] = a[i-1][j]*(4*(i-1)+2);
carry = 0;
for(j = 0; j < len; j++) //處理相乘結(jié)果
{
temp = a[i][j] + carry;
a[i][j] = temp % 10;
carry = temp / 10;
}
while(carry) //進(jìn)位處理
{
a[i][len++] = carry % 10;
carry /= 10;
}
carry = 0;
for(j = len-1; j >= 0; j--) //除法
{
temp = carry*10 + a[i][j];
a[i][j] = temp/(i+1);
carry = temp%(i+1);
}
while(!a[i][len-1]) //高位零處理
len --;
b[i] = len;
}
}
下面是一些大公司的筆試題
先來一道阿里巴巴的筆試題目：
16個人按順序去買燒餅闹炉，其中8個人每人身上只有一張5塊錢蒿赢，另外8個人每人身上只有一張10塊錢。燒餅5塊一個渣触，開始時燒餅店老板身上沒有錢羡棵。16個顧客互相不通氣，每人只買一個嗅钻。問這16個人共有多少種排列方法能避免找不開錢的情況出現(xiàn)皂冰。
答案：C8=1430，所以總數(shù)=14308养篓！8秃流！
騰訊實習(xí)招聘筆試題
在圖書館一共6個人在排隊，3個還《面試寶典》一書柳弄，3個在借《面試寶典》一書舶胀，圖書館此時沒有了面試寶典了，求他們排隊的總數(shù)碧注？
答案:C3=5嚣伐；所以總數(shù)為53！3萍丐！=180.
12個高矮不同的人轩端，排成兩排，每排必須是從矮到高排列逝变，而且第二排比對應(yīng)的第一排的人高基茵，問排列方式有多少種?
這個筆試題，很坑爹壳影，因為把某個遞歸關(guān)系隱藏得很深耿导。
首先來問題分析:
我們先把這12個人從低到高排列，然后态贤，選擇6個人排在第一排，那么剩下的6個肯定是在第二排醋火。
用0表示對應(yīng)的人在第一排悠汽，用1表示對應(yīng)的人在第二排，那么含有6個0芥驳，6個1的序列柿冲，就對應(yīng)一種方案。
比如000000111111就對應(yīng)著
第一排:0 1 2 3 4 5
第二排:6 7 8 9 10 11
010101010101就對應(yīng)著
第一排:0 2 4 6 8 10
第二排:1 3 5 7 9 11
問題轉(zhuǎn)換為兆旬，這樣的滿足條件的01序列有多少個假抄。
觀察1的出現(xiàn)，我們考慮這一個出現(xiàn)能不能放在第二排，顯然宿饱，在這個1之前出現(xiàn)的那些0熏瞄，1對應(yīng)的人
要么是在這個1左邊，要么是在這個1前面谬以。而肯定要有一個0的强饮，在這個1前面，統(tǒng)計在這個1之前的0和1的個數(shù)为黎。
也就是要求邮丰，0的個數(shù)大于1的個數(shù)。
OK铭乾，問題已經(jīng)解決剪廉。
如果把0看成入棧操作，1看成出棧操作炕檩，就是說給定6個元素斗蒋，合法的入棧出棧序列有多少個。
這就是神奇的卡特蘭數(shù)Ｅ跏椤４蹬荨！
