Catalan数（基础介绍篇）

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
using namespace std;
#define MAX 100
#define BASE 10000
int a[105][100];

void multiply(int a[],int b) //大数乘法(万进制）
{
    int array=0;
    for(int i=99;i>=0;i--)
    {
//      b 从99到0 依次 * a[i]
        array += b*a[i];
        a[i] = array%10000;
        array /= 10000;
    }
}

void divide(int a[],int b) //大数除法（万进制)
{
    int div=0;
    for(int i=0;i<100;i++)
    {
        div =div * 10000 + a[i];
        a[i] = div/b;
        div%=b;
    }
}

//卡特兰数的解法：
//h(n) = h(n-1) * (4n-2) / (n+1)
//前四项过程
//h[1] = 1
//h[2] = 1 * 6 / 3 = 2
//h[3] = 2 * 10 / 4 = 5
//h[4] = 5 * 14 / 5 = 14

int main()
{
    int n;
    a[1][99]=1;
//   将第一项变为1（99是最低位，相当于个位）
    for(int i=2;i<=100;i++)
    {
        memcpy(a[i],a[i-1],sizeof(a[i-1]));  //将a[i-1]赋给a[i]，从第二项开始
//        将a[1]赋给a[2]
    
//    对memcpy的解释：
//    char a[100]={'a','b','c','d'};
//    char b[100];
//    memcpy(b,a,sizeof(a));  将a复制到b里面，复制的个数是a的长度
//    cout << b << endl;
//    输出结果：abcd
    
        multiply(a[i],4*i-2);    //大数乘法
        divide(a[i],i+1);        //大数除法
    }
    while(cin>>n)
    {
        int i=0;
        if(n==-1) break;
        for (i=0;i<100;i++)
        {
            if(a[n][i]==0) continue;
            else break;
        }
        cout << a[n][i++];//最高项，不用填零补位
        for(;i<100;i++) printf("%04d",a[n][i]);  //必须是%04d，换成%4d或者%d都是错误的（不是最高项，要填零补位）

//知识点:
//      %d左对齐，输出变量的所有数字；
//      %4d右对齐，宽度为4，左边填充空格，当变量的实际宽度大于4时，输出变量的所有数字；
//      %04d与%4d的唯一区别就是左边填充0。

        cout<<endl;
    }
    return 0;
}