hdu 1023 Train Problem II

it2022-05-06  17

额,同一个代码,贴了三道题 ,都不用改的,卡特兰数的应用,还有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

相关资源:数据结构—成绩单生成器

最新回复(0)