要求用递归算法解决具有递推关系的序列和计数问题，用分治法高效解决具有非线性复 杂度的实际问题，结合文件操作处理大规模数据输入的问题，用 clock_t tm=clock()测定算法 执行时间，单位：毫秒。
样例引入Catalan 数 C(n)的计算:小兔的棋盘
题意：Catalan 数的定义如下，首先规定 C(0)为 1，然后按照下式定义 C(n)。
例如 n=5，C(5)=C(0)C(4)+C(1)C(3)+C(2)C(2)+C(3)C(1)+C(4)C(0)。
前 6 个 Catalan 数是 1，2，5，14，42，132。要求计算各个 Catalan 数。
输入：n（n≤19）。
输出：C(n)。
输出（对比观察）：+运行时间(ms)。
样例输入样例输出6132191 757 263 190353 116 285 494 907 301 262方法1：递归算法。用递归程序计算 C(n)，依次输入 n=1, 2, 3, …, 19，输出 Catalan 数 C(n)，观察哪个 C(n)的计算时间开始大于 10 秒，记录能在 10 秒钟内计算出结果的最大 n 值、C(n)和计算时间。
按照上式设计的递归函数如下：
long long C(int n){ if (n == 0) return 1; long long sum(0); for (int i = 0; i < n; i++) sum += C(i) * C(n-1-i); return sum;}基本思路是从n递归到1，每次都进行累加与乘法，假设n为六，那么从6进入递归
n654321C(6)C(0)C(5)C(1)C(4)C(2)C(3)C(3)C(2)C(4)C(1)C(5)C(0)C(5)C(0)C(4)C(1)C(3)C(2)C(2)C(3)C(1)C(4)C(0)C(4)C(0)C(3)C(1)C(2)C(2)C(1)C(3)C(0)C(3)C(0)C(2)C(1)C(1)C(2)C(0)C(2)C(0)C(1)C(1)C(0)C(1)C(0)C(0)随着n的增大，计算复杂性会呈指数级增长，其中影响最大的就是C(n)的重复计算，如果将C(n)的前n-1个子项提前记录下来，也就是在每个子项中只要计算一次乘再相加，计算复杂度会从O(n^2)降至O(n)，下面看方法2。
方法2：非递归算法:为计算 C(n)，按顺序依次计算 C(1), C(2), …, 直 至 C(n)。
long long DPC(int n){long long int a[36];//用数组进行存储long long sum=0;a[0]=1;a[1]=1;for(int i=2; i<=n; i++){sum=0;for(int j=0; j<i; j++){sum+=a[j]*a[i-j-1];}a[i]=sum;}return a[n];}在main函数中进行比较：
int main(){clock_t x1,x2,x3;int n;scanf("%d",&n);x1=clock();printf("%lldn",C(n));x2=clock();printf("递归方法用时：%d msn",x2-x1);printf("%lldn",DPC(n));x3=clock();printf("备忘录方法用时：%d msn",x3-x2);return 0;}结果如下：
可以发现，效率大大提升。