Catalan数推导及应用
Catalan數(shù)的定義：
?
設(shè)表示用下面的方法把凸多邊形區(qū)域分成三角形區(qū)域的方法數(shù)：在有n+1條邊的凸多邊形區(qū)域內(nèi)通過插入在其中不相交的對(duì)角線而把它分成三角形區(qū)域。定義。則滿足遞推關(guān)系
?????????
???????? ? ???
?
這個(gè)遞推關(guān)系的解是：，這里的叫做Catalan數(shù)。
?
?
那么上面的遞推式的正確性我們可以簡單描述一下即可：
證明：這里因?yàn)楸硎景凑丈鲜鲆?guī)則劃分的三角形區(qū)域個(gè)數(shù)，那么我們隨便選一條多邊形的一條邊作為基邊，那么
???? 再在剩余的n-1個(gè)點(diǎn)中選一個(gè)點(diǎn)，我們把所選的一條邊的兩點(diǎn)分別與所選的那一點(diǎn)連接起來，那么多邊形被劃
???? 分成3部分，一部分有k+1條邊，一部分有3條邊，另一部分有n-k+1條邊，那么這樣就劃分成了子問題了，所
???? 以按照這個(gè)思路可以證明遞推式成立。
?
那么根據(jù)遞推式是如何推出Catalan數(shù)的通項(xiàng)公式呢？
?
這里用到了生成函數(shù)：我們很容易寫出的生成函數(shù)
?
我們進(jìn)一步計(jì)算
?
?
因?yàn)橛?#xff1a;，所以進(jìn)一步得到：
?
，由于
?
所以有：，解之得到：
?
，另一個(gè)解不符合，舍去。
?
那么根據(jù)牛頓二項(xiàng)式有：
?
?
?
那么帶入化簡得到：
?
?
那么我們最終得到：
?
所以：，這就是Catalan的推導(dǎo)過程。
?
?
?
卡特蘭數(shù)的應(yīng)用
??????
1、括號(hào)化問題
?
矩陣連乘：，依據(jù)乘法結(jié)合律，不改變其順序，只用括號(hào)表示成對(duì)的乘積，問有幾種括號(hào)化的方案？
???????
?
2、出棧次序問題
?
一個(gè)棧(無窮大)的進(jìn)棧序列為1,2,3,..n,有多少個(gè)不同的出棧序列?
?
?
類似問題
?
a、有2n個(gè)人排成一行進(jìn)入劇場，入場費(fèi)5元。其中只有n個(gè)人有一張5元鈔票，另外n人只有10元鈔票，劇院無其它鈔票，問有多少中方法使得只要有10元的人買票，售票處就有5元的鈔票找零？(將持5元者到達(dá)視作將5元入棧，持10元者到達(dá)視作使棧中某5元出棧)
?
b、n個(gè)1和n個(gè)0組成一個(gè)2n位的二進(jìn)制數(shù)，要求從左到右掃描，0的累計(jì)數(shù)不小于1的累計(jì)數(shù)，求滿足條件的的數(shù)。
?
c、12個(gè)人排成兩排，每排必須是從矮到高排列，而且第二排比對(duì)應(yīng)的第一排的人高，問排列方式有多少種？
我們先把這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問題轉(zhuǎn)換為，這樣的滿足條件的01序列有多少個(gè)。與情況b一樣。
?
3、給定節(jié)點(diǎn)組成二叉樹的問題
?
給定N個(gè)節(jié)點(diǎn)，能構(gòu)成多少種形狀不同的二叉樹？
先取一個(gè)點(diǎn)作為頂點(diǎn),然后左邊依次可以取0至N-1個(gè)相對(duì)應(yīng)的,右邊是N-1到0個(gè),兩兩配對(duì)相乘,就是h(0)*h(n-1) + h(2)*h(n-2) +? + h(n-1)h(0)=h(n))能構(gòu)成h（N）個(gè)
?????
4.n*n棋盤從左下角走到右上角而不穿過主對(duì)角線的走法
?
5.n個(gè)+1和n個(gè)-1構(gòu)成的2n項(xiàng)序列，其部分和總滿足：的序列的個(gè)數(shù)。
?
Catalan數(shù)的高精度處理：利用遞歸式： h(n)=((4*n-2)/(n+1))*h(n-1)
?
#include <iostream> #include <stdio.h> #include <cmath> using namespace std;int a[105][105]; //大數(shù)卡特蘭數(shù) int b[105]; //卡特蘭數(shù)的長度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;} }int main() {int i,n;catalan();while(~scanf("%d",&n),n){for(i=b[n]-1;i>=0;i--)printf("%d",a[n][i]);printf("\n");}return 0; }
?
總結(jié)
以上是生活随笔為你收集整理的Catalan数推导及应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
