额，同一个代码，贴了三道题 ，都不用改的，卡特兰数的应用，还有hdu1130，hdu1134
出栈次序问题，其实就是卡特兰数的应用
卡特兰公式：
令h(1)＝1,h(0)=1，catalan数满足递归式：
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2)
另类递归式：
h(n)=((4*n-2)/(n+1))*h(n-1);
该递推关系的解为：
h(n)=C(2n,n)/(n+1) (n=1,2,3,...)
用递归式来做，接下来就是一个大数问题了，（4*n-2）/(n+1) 不能直接算，未必整除呀ORZ
先算（4*n-2）*h（n-1） ，再除以（n+1)
#include <iostream> using namespace std; #define SIZE 100 int main() { int a[101][SIZE]={0}; //数组用来存放结果 a[1][0]=1; //初始化第一项 int i,j,r=0,temp=0,len=1; //len 表示当前最长的有效位数，初始为1 for(i=2;i<=100;i++) //从第二项到第100项，用公式计算 { for(j=0;j<len;j++) //---------------乘法部分------------------ { a[i][j]=a[i-1][j]*(4*i-2); //乘法从低位到高位 } for(j=0;j<len;j++) //对乘出的结果进行处理，不包括最高位 { temp=a[i][j]+r; a[i][j]=temp; r=temp/10; } while(r) //对最高位进位处理 { a[i][len]=r; r/=10; len++; } //-----------------除法部分----------------- for(j=len-1,r=0;j>=0;j--) { //除法从高位到低位 temp=r*10+a[i][j]; a[i][j]=temp/(i+1); r=temp%(i+1); } while(!a[i][len-1]) //处理高位的零位 len--; } //------------------------------------------- int n; while(cin>>n&&n!=-1) { for(i=SIZE-1;!a[n][i];i--); for(i;i>=0;i--) cout<<a[n][i]; cout<<endl; } return 0; }转载于:https://www.cnblogs.com/nanke/archive/2011/08/05/2128968.html
相关资源：数据结构—成绩单生成器