小兔的棋盘

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
 
Sample Output
1 1 2
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;
}
05-07 15:48