hdu 1134(大数+卡特兰数——Game of Connections)
发布时间:2020-12-14 04:02:08 所属栏目:大数据 来源:网络整理
导读:题目大意:输入一个整数n,用2n个数围成一个圆圈。然后用n条直线练成n对数(连线不能相交),求有多少种连法? 解题思路:大数+卡特兰数 1) an ? =C(2n,n)/(n+1)=(4n-2)*( an-1 )/(n+1) 代码如下: package com.njupt.acm;import java.math.BigInteger;import java.
题目大意:输入一个整数n,用2n个数围成一个圆圈。然后用n条直线练成n对数(连线不能相交),求有多少种连法? 解题思路:大数+卡特兰数 1) an?=C(2n,n)/(n+1)=(4n-2)*(an-1)/(n+1) 代码如下:
package com.njupt.acm; import java.math.BigInteger; import java.util.Scanner; public class HDU_1134 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); BigInteger one = new BigInteger("1"); BigInteger two = new BigInteger("2"); BigInteger four = new BigInteger("4"); while(scanner.hasNextInt()){ int n = scanner.nextInt(); BigInteger catalan = one; BigInteger N; if(n == -1){ break; } if( n == 1 ){ System.out.println("1"); continue; } for(int i = 1 ; i <= n ; ++i){ N = new BigInteger(String.valueOf(i)); catalan = catalan.multiply(four.multiply(N).subtract(two)).divide(N.add(one)); } System.out.println(catalan); } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |