本文共 1740 字，大约阅读时间需要 5 分钟。

问题描述

X星球特别讲究秩序，所有道路都是单行线。一个甲壳虫车队，共16辆车，按照编号先后发车，夹在其它车流中，缓缓前行。

路边有个死胡同，只能容一辆车通过，是临时的检查站，如图所示。

如果车辆进入检查站和离开的次序可以任意交错。那么，该车队再次上路后，可能的次序有多少种？

为了方便起见，假设检查站可容纳任意数量的汽车。

显然，如果车队只有1辆车，可能次序1种；2辆车可能次序2种；3辆车可能次序5种。

现在足足有16辆车啊，亲！需要你计算出可能次序的数目。

这是一个整数，请输出答案，不要输出任何多余的内容（比如说明性文字）。

没有输入。

输出一个整数，即可能次序的数目。

运用递归调用即可求解，代码如下：

#include 
   
    int f(int n,int m) {
   	if(n==0) //如果左边没有车返回1		return 1;	if(m==0) //如果检车站没车就入栈		return f(n-1,1);	if(m>0)//如果检车站有车		//分两种情况，车辆入站和出站		return f(n-1,m+1)+f(n,m-1);	return 0;}int main() {
   	printf("%d",f(16,0));	return 0;}
   

答案;35357670

一些其他的方法;

1.递归的其他思路

#include 
   
    int num=0;/*求出栈次序，无非就是问一共有多少种满足要求的排列，满足条件在本题中就是指，只有站中有“车”，才能够出来。假设1，代表进站，0代表出站，r代表进栈的个数，L代表出栈的个数，易知只有进栈的个数r大于等于出栈的个数L才可以出栈或进栈，否则只能进栈,因此可以进行回溯求出所有可能的方案。*/void dfs(int n,int r,int l){
       if(n==32)	{
           num++;        return;    }        if(r>l)		{
               if(r<16)            dfs(n+1,r+1,l);            if(l<16)            dfs(n+1,r,l+1);        }		else		{
               if(r==l)            if(r<16)            dfs(n+1,r+1,l);        }    return;} int main(){
         dfs(0,0,0);    printf("%d",num);    return 0;}
   

2.利用卡特兰数的公式f(n) = f(0)*f(n-1) + f(1)*f(n-2) + … +f(n-1)*f(0)

#include 
   
    int main(){
       int f[20];    int i,j;    f[0]=1;    f[1]=1;    f[2]=2;    f[3]=5;    for(i=4;i<=16;i++)        f[i]=0;//注意必须给其他数组置0    for(i=4; i<=16; i++) //求16个元素    {
           for(j=0; j<=i-1; j++)            f[i]+=f[j]*f[i-1-j];    }    printf("%d",f[16]);    return 0;}
   

3.卡特兰数的另一种递推公式h(n)=h(n-1)(4n-2)/(n+1)

#include 
   
    int main(){
       int n,h[20];    h[0]=1;    h[1]=1;    for(n=2;n<=16;n++)        h[n]=h[n-1]*(4*n-2)/(n+1);    printf("%d\n",h[16]);    return 0;}
   

转载地址：http://ejrzi.baihongyu.com/