你的位置:首页 > Java教程

[Java教程]POJ 2084 Game of Connections 卡特兰数


看了下大牛们的,原来这题是卡特兰数,顺便练练java。递归式子:h(0)=1,h(1)=1   h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2)   打表172MS

import java.math.BigInteger;import java.util.Scanner;public class Main {  public static void main(String[] args) {    Scanner in=new Scanner(System.in);    BigInteger[] a=new BigInteger [205];    a[0]=a[1]=BigInteger.ONE;    for(int i=2;i<=200;i++){      a[i]=BigInteger.ZERO;      for(int j=0;j<i;j++){        a[i]=a[j].multiply(a[i-j-1]).add(a[i]);      }      //System.out.println(a[i]);    }    while(true){      int n=in.nextInt();      if(n==-1)        break;      System.out.println(a[n]);    }  }}