HDU1023（JAVA···高精度卡特兰数）

最新推荐文章于 2022-09-29 19:47:58 发布

编码之夜

最新推荐文章于 2022-09-29 19:47:58 发布

阅读量1.1k

点赞数

分类专栏： HDU 文章标签：卡特兰数

本文链接：https://blog.csdn.net/u013447865/article/details/42526647

版权

HDU 专栏收录该内容

133 篇文章

订阅专栏

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1023

解题思路：

卡特兰数a[ i ] = a[ i - 1 ] * (4 * i - 2) / (i + 1)，a[0] = a[1] = 1。当i>10时，a[ i ]会很大，所以首选JAVA。

完整代码：

import java.math.BigInteger;
import java.util.Scanner;


public class Main {
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		BigInteger [] a = new BigInteger[101];
		BigInteger start = new BigInteger("1");
		a[0] = start;
		a[1] = start;
		for(int i = 2 ; i < 101 ; i ++){
			Integer t1 = i + 1;
			Integer t2 = 4 * i - 2; 
			BigInteger k1 = new BigInteger(t1.toString());
			BigInteger k2 = new BigInteger(t2.toString());
			a[i] = (a[i - 1].multiply(k2)).divide(k1);
		}
		while(cin.hasNext()){
			int n = cin.nextInt();
			System.out.println(a[n]);
		}
	}
}