>

卡特兰数

- 编辑:正版管家婆马报彩图 -

卡特兰数

POJ 2084 Game of Connections Carter兰数,poj2084

看了下大牌们的,原本那题是Carter兰数,顺便练练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]);
        }
    }

}

 

2084 Game of Connections 卡特兰数,poj2084 看了下大腕们的,原本那题是Carter兰数,顺便练练java。递归式子: h(0)=1,h(1)=1 h(n)=h(0)*h(n-1)+h(1)...

看了下大牌们的,原本那题是Carter兰数,顺便练练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]);
        }
    }

}

 

本文由网络计算发布,转载请注明来源:卡特兰数