又是一個考驗(yàn)算法積累的題目，該題討論的是卡特蘭數(shù)的應(yīng)用。
卡特蘭數(shù)的使用條件為：h(n)=h(0)×h(n-1)+h(1)×h(n-1)+~~~+h(n-1)×h(0)
通式為：h(n)=(2×n)!/[(n+1)!×n!] (n>=2)
使用的情況有：如二叉樹的個數(shù)，有序樹的個數(shù)，多邊形分成三角形的個數(shù)等。
如：排隊(duì)的問題，十個人排兩排，第一排的人比第二排的人低，有幾種排法：
我們可以先把這10個人從低到高排列，然后，選擇5個人排在第一排，那么剩下的5個人肯定是在第二排。
用0表示對應(yīng)的人在第一排，用1表示對應(yīng)的人在第二排，那么含有5個0，5個1的序列，就對應(yīng)一種方案。
比如0000011111就對應(yīng)著
第一排:0 1 2 3 4
第二排:5 6 7 8 9
0101010101就對應(yīng)著
第一排:0 2 4 6 8
第二排:1 3 5 7 9
所以，看到問題相應(yīng)的轉(zhuǎn)換為，這樣的滿足條件的01序列有多少個。
觀察規(guī)律我們發(fā)現(xiàn)1的出現(xiàn)前邊必須有一個相應(yīng)的0對應(yīng)，所以從左到右的所有序列中0的個數(shù)要一直大于1的個數(shù)。那這種數(shù)列有多少種排列方式呢？
從左往右，假設(shè)第一個零的個數(shù)等于一的個數(shù)是在第k個數(shù)，那么k的左邊一定0的個數(shù)不小于1的個數(shù)，共有k-1個數(shù)，在k的右邊，應(yīng)有n-k個數(shù)，這n-k個數(shù)也滿足從左到右0的個數(shù)不小于1的個數(shù)。假設(shè)n個人的情況共h（n）個，那么左邊h（k-1）個，右邊h（n-k）個，共h（k-1）*h（n-k），k可取1~n，故是一個累加的過程，符合卡特蘭數(shù)的規(guī)則。
在該題中，一共有n個結(jié)點(diǎn)的情況共有f（n）中，那么取一個結(jié)點(diǎn)為根結(jié)點(diǎn)，若左子樹有k-1個結(jié)點(diǎn)，右子樹就有n-k個節(jié)點(diǎn)，左子樹共有f（k-1）種情況，右子樹則有f（n-k）種，共有f(k-1)*f(n-k)種情況，k-1可以取到0~n故需累加，符合卡特蘭數(shù)的規(guī)則。
卡特蘭數(shù)的公式有多種
由于多個求階乘的方法太占用時間復(fù)雜度，所以應(yīng)該對其進(jìn)行一系列的變化，在將該通式變換后得：
c(n)=c(n-1)(4n-2)/(n+1)?？筛鶕?jù)此式求解。
在解出卡特蘭數(shù)以后，求出的是從根結(jié)點(diǎn)到葉子節(jié)點(diǎn)的安置方式，但是每個結(jié)點(diǎn)的安置順序還是不確定的，因此還需要乘n?。ㄋ泄?jié)點(diǎn)的排序結(jié)果）
//輸出卡特蘭數(shù)
//首先需要肯定，程序是正確的
//這算是大數(shù)乘除法！記住他們是如何處理的！由于數(shù)據(jù)很大，用基本數(shù)據(jù)類型根本無法滿足要求，只能用數(shù)組來表示！
#include "stdafx.h"
//典型的卡特蘭數(shù)的應(yīng)用
//判定二叉樹的數(shù)量！假設(shè)有n個節(jié)點(diǎn)，一共有h(n)種數(shù)
//可以這樣考慮：先選定一個節(jié)點(diǎn)為根節(jié)點(diǎn)，則還余下n-1個節(jié)點(diǎn)
//如果根節(jié)點(diǎn)左子樹無節(jié)點(diǎn)，則右子樹有n-1個節(jié)點(diǎn)
//如果左子樹有1個節(jié)點(diǎn)，則右子樹有n-2個節(jié)點(diǎn)~~~
//因此一共的種數(shù)是h(n)=h(0)*h(n-1)+h(1)*h(n-1)+~~~+h(n-1)*h(0)
//而這恰好是卡特蘭數(shù)的表達(dá)式！卡特蘭數(shù)一般的表達(dá)式為h(n)=(2*n)!/[(n+1)!*n!] (n>=2)
//這道題使用的公式為c(n)=c(n-1)*(4*n-2)/(n+1);
#include <stdlib.h>
#include<iostream>
using namespace std;
#define MAX 101
#define BASE 10000
void multiply(int a[], int len, int b)//作用：四個數(shù)為一組，當(dāng)大于四個數(shù)時，開始進(jìn)位。乘法
{
for (int i = len - 1, carry = 0;i >= 0;--i)
{
carry = carry + b*a[i];//h[i]項(xiàng)中存放的是h[i-1]的數(shù)字，故需要先將其本身乘以4*i-2，再除以i+1便可，這里進(jìn)行的是乘項(xiàng)。
a[i] = carry%BASE;//為了避免h[i]超過10000，所以會對其除10000取余，只存放小于10000的數(shù)位。
carry = carry / BASE;//而carry變量將超出的位數(shù)記下，代表進(jìn)位，并將這些超出的數(shù)加入到更高位中（參考與數(shù)學(xué)中列豎式進(jìn)位）
}//對于第一行的下一個四位乘后再加carry的情況，可以參考：100 2000 --》100 2000*6=601 2000==（100*10000+2000）*6=100*10000*6+2000*6
}//直到carry==0并且a[i~MAX]==0
void divide(int a[], int len, int b)//除法，從高位到低位，可參考與除法的豎式運(yùn)算
{
for (int i = 0, div = 0;i<len;i++)
{
div = div*BASE + a[i];
a[i] = div / b;
div = div%b;
}
}
int main()
{
int i, j, h[101][MAX];
int a[MAX];
memset(h[1], 0, MAX * sizeof(int));
for (i = 2, h[1][MAX - 1] = 1;i <= 100;i++)
{
memcpy(h[i], h[i - 1], MAX * sizeof(int));//把第h[i+1]項(xiàng)放入h[i]中
multiply(h[i], MAX, 4 * i - 2);
divide(h[i], MAX, i + 1);
}
while (cin >> i && i >= 1 && i <= 100)
{
memcpy(a, h[i], MAX * sizeof(int));
for (j = 2;j <= i;j++)
multiply(a, MAX, j);//依次乘1*2*3…*n 為n個節(jié)點(diǎn)的自行排序結(jié)果。
for (j = 0;j<MAX && a[j] == 0;j++);//自增到開始有數(shù)字的位數(shù)
printf("%d", j, a[j++]);//這個位數(shù)是最高的一個四位數(shù)，故可能是小于四位的，故不需要加限制輸出位數(shù)，格外輸出
for (;j<MAX;j++)
printf("%04d", j, a[j]);//在已自增到可輸出的位數(shù)后，在此基礎(chǔ)上輸出之后的相關(guān)四位數(shù)
printf("\n");
}//*/
system("pause");
return 0;
}
卡特蘭數(shù)為1，1，2，5，14，42，132，429，1430，4862……
在推理失敗時可以通過數(shù)字答案比對來驗(yàn)證題目是否為卡特蘭數(shù)。
