How Many Trees?

​

卡特兰数

#include <iostream>

#include <algorithm>

using namespace std;

int a105;//ansi i表示第几个卡特兰数，

              //j=0表示位数，j从1到ans[i][0]是个位数往上                

void ktl()

{

a1=1; a1=1;

a2=1; a2=2;

int len=1,yu,t,i,j;

for( i=3;i<=104;i++)

 {

yu=0;

for(j=1;j<=len;j++)

{

t=a[i-1][j]\*(4\*i-2)+yu;//注意先乘再加余数 

  a[i][j]=t%10;//这一位的值是对10取余 

   yu=t/10;//进位是除以10 

      }

      while(yu)

        {

ai=yu%10;

 yu/=10;

}

for(j=len;j>=1;j--)

  {

t=ai+yu*10;//除法先加“余数”再除

    a[i][j]=t/(i+1);//留在这一位是除 

yu=t%(i+1);//“余数”是取余

//除法和乘法是逆过程，计算时也是反过来

}

while(!ai)

  {

len--;

}

ai=len;

}

}

int main()

{

ktl();

int n;

while(~scanf("%d",&n))

   {

for(int i=a[n][0];i>0;i--)

    printf("%d",a[n][i]);

    printf("\n");

}

return 0;

}