卡特兰数的模拟。

CODE：

#include <stdio.h>

#include <stdlib.h>

#include <

string.h>

#include <math.h>

using 

namespace std;

#define MAX 101

#define BASE 10000

int a[

101][MAX];

void multiple(

int a[], 

int size, 

int b)

{

    

int i, j;

    

int carry = 

0;

    

for(i = size-

1; i >= 

0; i--)

    {

        carry += a[i]*b;

        a[i] = carry%BASE;

        carry = carry/BASE;

    }

    

return ;

}

void divide(

int a[], 

int size, 

int b)

{

    

int i, j;

    

int div = 

0;

    

for(i = 

0; i < size; i++)

    {

        div = div*BASE + a[i];

        a[i] = div/b;

        div = div%b;

    }

    

return; 

}

void init()

{

    

int i;

    memset(a, 

0, 

sizeof(a));         

//

数组高位存放大数低位 

    a[

1][MAX-

1] = 

1;

    

for(i = 

2; i < 

101 ; i++)

    {

        memcpy(a[i], a[i-

1], 

sizeof(a[i-

1]));    

//

h(n) = h(n-1)

        multiple(a[i], MAX, 

4*i-

2);              

//

 h(n) = h(n-1)*(4*n-2)

        divide(a[i], MAX, i+

1);                     

//

h(n) = h(n-1)*(4*n-2)/(n+1)

    }

    

return ;

}

void output(

int n)

{

    

int i;

    

for(i = 

0; a[n][i] == 

0; i++);     

//

跳过数组前面的0 

    printf(

"

%d

", a[n][i++]);           

//

输出第一位非0数 

    

for(; i < MAX; i++)

    {

        printf(

"

%04d

", a[n][i]);       

//

由于进位是10000，所以每位保持4位长度 

    }

    printf(

"

\n

");

}

int main()

{

    

int n;

    init();

    

while(~scanf(

"

%d

", &n))

    {

        output(n);

    }

    

return 

0;

}