|
#2
Susake2013-02-27 14:38
|
(时间限制为：100毫秒)
问题描述
这是一个小而古老的游戏，假设你将1~2n个数按顺时针方向写下来组成一个圆环，然后用一些线段将这些数组成一个数对。每个数只仅仅与另一个相连。而且所有线段不能相交。
请你写一个程序，计算当写下2n个数后，一共有多少种不同的相连方式。
连接方式数Ai的推导公式如下：
A1=1 An=（4n-2）/(n+1)*An-1 (n>=2)
输入
每行输入一个正整数n（1<=n<=100），最后一行是-1，代表结束。
输出
对于每个n，输出一行数字，表示2n个数相连的可能数目。
样例输入
2
3
-1
样例输出
2
5
程序代码：#include <iostream>
using namespace std;
int f(int n)
{ unsigned long s;//范围小了，怎么办
if(n==1)
s=1;
else if(n>=2)
s=(4*n-2)*f(n-1)/(n+1);
return s;
}
int main()
{
int x;
while(cin>>x)
{
if(x==-1)break;
cout<<f(x)<<endl;
}
return 0;
}
using namespace std;
int f(int n)
{ unsigned long s;//范围小了，怎么办
if(n==1)
s=1;
else if(n>=2)
s=(4*n-2)*f(n-1)/(n+1);
return s;
}
int main()
{
int x;
while(cin>>x)
{
if(x==-1)break;
cout<<f(x)<<endl;
}
return 0;
}
