问题陈述:
问题解析:
卡特兰数(Catalan)的应用
基本性质:
f(n) = f(1)f(n-1) + f(2)f(n-2) + ... + f(n-2)f(2) + f(n-1)f(1);
f(n) = C(2n, n) / (n+1) = C(2n-2, n-1) / n;
Cn = (4n-2)/(n+1) Cn-1
代码详解:
I: C++
#include <iostream>
#include <cstdio>
#include <memory.h> using namespace std; #define MAX 101
#define BASE 10000 void multiply(int a[], int len, int b) {
for(int i=len-, carry=; i>=; i--) {
carry += b * a[i];
a[i] = carry % BASE;
carry /= BASE;
}
} void divide(int a[], int len, int b) {
for(int i=, div=; i<len; i++) {
div = div * BASE + a[i];
a[i] = div / b;
div %= b;
}
} int main()
{
int i, j, h[][MAX];
memset(h[], , MAX*sizeof(int));
for(i=, h[][MAX-]=; i<=; i++) {
memcpy(h[i], h[i-], MAX*sizeof(int));
multiply(h[i], MAX, *i-);
divide(h[i], MAX, i+);
} while(cin >> i && i>= && i <= ) {
for(j=; j<MAX && h[i][j]==; j++);
printf("%d", h[i][j++]);
for(; j<MAX; j++)
printf("%04d", h[i][j]);
cout << endl;
}
return ;
}
II: Java
import java.io.BufferedInputStream;
import java.math.BigInteger;
import java.util.Scanner; public class Main { public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n;
while(sc.hasNext()) {
BigInteger catalan = BigInteger.valueOf(1);
n = sc.nextInt();
for(int i=1; i<=n; i++) {
catalan = catalan.multiply(BigInteger.valueOf(4*i-2)).divide(BigInteger.valueOf(i+1));
}
System.out.println(catalan);
}
sc.close();
}
}
参考资料: