Game of Connections
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2101 Accepted Submission(s): 1208
Problem Description
This is a small but ancient game. You are supposed to write down the numbers 1, 2, 3, ... , 2n - 1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one another. And, no two segments are allowed to intersect.
It's still a simple game, isn't it? But after you've written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right?
It's still a simple game, isn't it? But after you've written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right?
Input
Each line of the input file will be a single positive number n, except the last line, which is a number -1. You may assume that 1 <= n <= 100.
Output
For each n, print in a single line the number of ways to connect the 2n numbers into pairs.
Sample Input
2 3 -1
Sample Output
2 5
View Code
1 /* 2 卡特兰计算公式： 3 数列 a[n]=C(2n,n)/(n+1) 4 为了计算的方便将其推导为递推公式：a[n]=((4*n-2)/(n+1))*a[n-1]; 5 卡特兰数实质：h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)h(0) (其中n>=2) 6 卡特兰数模型： 7 1.出栈次序问题 8 一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列? 9 2.凸多边形的三角剖分问题 10 求将一个凸多边形区域分成三角形区域的方法数。 11 3.用给定节点组成二叉树的问题 12 （能构成h（N）个） 13 */ 14 #include <iostream> 15 #include <cstring> 16 using namespace std; 17 18 long long ans[105];//仍然溢出 19 20 void init() 21 { 22 int i,j,k; 23 ans[1] = 1,ans[2] = 2,ans[3] = 5; 24 for(i=4;i<=100;i++) 25 ans[i] = ((4*i-2)/(i+1))*ans[i-1]; 26 } 27 28 int main() 29 { 30 int i,j,k; 31 int num; 32 init(); 33 while(cin>>num,~num) 34 cout<<ans[num]<<endl; 35 return 0; 36 } 37
1 #include <iostream> 2 using namespace std; 3 4 const int SIZE = 100; 5 6 int main() 7 { 8 int ans[101][SIZE]={0}; //数组用来存放结果 9 ans[1][0]=1; //初始化第一项 10 int i,j,r=0,temp=0,len=1; //len 表示当前最长的有效位数，初始为1 11 for(i=2;i<=100;i++) //从第二项到第100项，用公式计算 12 { 13 for(j=0;j<len;j++) //---------------乘法部分------------------ 14 { 15 ans[i][j]=ans[i-1][j]*(4*i-2); //乘法从低位到高位 16 } 17 for(j=0;j<len;j++) //对乘出的结果进行处理，不包括最高位 18 { 19 temp=ans[i][j]+r; 20 ans[i][j]=temp%10; 21 r=temp/10; 22 } 23 while(r) //对最高位进位处理 24 { 25 ans[i][len]=r%10; 26 r/=10; 27 len++; 28 } 29 //除法部分 30 for(j=len-1,r=0;j>=0;j--) 31 { //除法从高位到低位 32 temp=r*10+ans[i][j]; 33 ans[i][j]=temp/(i+1); 34 r=temp%(i+1); 35 } 36 while(!ans[i][len-1]) //处理高位的零位 37 len--; 38 39 } 40 int n; 41 while(cin>>n&&n!=-1) 42 { 43 for(i=SIZE-1;!ans[n][i];i--); 44 for(i;i>=0;i--) 45 cout<<ans[n][i]; 46 cout<<endl; 47 } 48 return 0; 49 }
