小兔的棋盘

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 154 Accepted Submission(s): 102

Problem Description

小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!

Input

每次输入一个数n(1<=n<=35)，当n等于－1时结束输入。

Output

对于每个输入数据输出路径数，具体格式看Sample。

Sample Input

1312-1

Sample Output

1 1 22 3 103 12 416024

小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己

的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋

盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),

现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路

径数有多少? 总共有 2 * C（n）种。 C（n）为卡特兰数

import java.math.BigDecimal;

import java.util.Scanner;
public class Main {

public static void main(String[] args){

BigDecimal []t = new BigDecimal[36];
BigDecimal n,b;
int k,j=1;
Scanner cin = new Scanner(System.in);

t[1] = BigDecimal.valueOf(1);
for(int i = 2;i< 36;i++){

n = BigDecimal.valueOf(i);

b = BigDecimal.valueOf(4).multiply(n);

b = b.subtract(BigDecimal.valueOf(2));

n = n.add(BigDecimal.valueOf(1));

b = b.multiply(t[i-1]);

t[i] = b.divide(n);

//System.out.println(t[i]);

}
while(cin.hasNext()){

k = cin.nextInt();
if(k==-1)break;
System.out.println(j+" "+k+" "+t[k].multiply(BigDecimal.valueOf(2)));

j++;
}
}
}

本文转自NewPanderKing51CTO博客，原文链接：http://www.cnblogs.com/newpanderking/archive/2011/07/31/2122526.html ，如需转载请自行联系原作者