小兔的棋盘
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8336 Accepted Submission(s): 4388
Problem Description
小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!
Input
每次输入一个数n(1<=n<=35)，当n等于－1时结束输入。
Output
对于每个输入数据输出路径数，具体格式看Sample。
Sample Input
1
3
12
-1
3
12
-1
Sample Output
1 1 2
2 3 10
3 12 416024
2 3 10
3 12 416024
又是一道考察递推公式的题目，然而以我的水平还是得百度。
得知递推公式为：f(n)=f(n-1)*(4n-2)/(n+1)
做法：设一个符合题目规模的二维数组（必须是足够大的__int64型，否则会溢出），然后将其看作一个棋盘，这样与题目相结合后发现每一步的情况个数map[n][n]=左边map[n][n-1]+上面map[n-1][n]；本来是用递归的，后来发现到后面数字特别大的情况下计算过程会溢出，导致结果出错，即使转换为double也无效，只好用二维数组加法。
代码：
#include<stdio.h>
__int64 map[36][36]={};
int main(void)
{
__int64 n,ans,i,j,t=0;
for(i=0;i<36;i++)
map[i][0]=1;
for(i=1;i<=35;i++)
for(j=1;j<=i;j++)
map[i][j]=map[i-1][j]+map[i][j-1];
while(~scanf("%I64d",&n)&&n!=-1)
{
t++;
printf("%I64d %I64d %I64d\n",t,n,2*map[n][n]);
}
return 0;
}