本文主要是介绍UVa 10303 How Many Trees? (卡特兰数高精度)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
10303 - How Many Trees?
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1244
A binary search tree is a binary tree with root k such that any node v in the left subtree of k has label (v) <label (k) and any node w in the right subtree of k has label (w) > label (k).
When using binary search trees, one can easily look for a node with a given label x: After we compare x to the label of the root, either we found the node we seek or we know which subtree it is in. For most binary search trees the average time to find one of its n nodes in this way is O(log n).
Given a number n, can you tell how many different binary search trees may be constructed with a set of numbers of size n such that each element of the set will be associated to the label of exactly one node in a binary search tree?
Input and Output
The input will contain a number 1 <= i <= 1000 per line representing the number of elements of the set. You have to print a line in the output for each entry with the answer to the previous question.
Sample Input
1
2
3
Sample Output
1
2
5
经典卡特兰数之一。递推公式证明见《组合数学》。
完整代码：
Java：不得不说在这一题中终于逆袭C++...
/*0.285s*/import java.io.*;
import java.util.*;
import java.math.*;public class Main {public static Scanner cin = new Scanner(new BufferedInputStream(System.in));///不错的速度public static void main(String[] args) {BigInteger[] f = new BigInteger[1001];f[1] = BigInteger.ONE;for (int i = 2; i <= 1000; ++i)f[i] = f[i - 1].multiply(BigInteger.valueOf(4 * i - 2)).divide(BigInteger.valueOf(i + 1));while (cin.hasNextInt())System.out.println(f[cin.nextInt()]);}
}C++：
/*0.682s*/#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 700;///注意此值的设置要留意中间结果char numstr[maxn];///输入输出接口struct bign
{int len, s[maxn];bign(){memset(s, 0, sizeof(s));len = 1;}bign(int num){*this = num;}bign(const char* num){*this = num;}bign operator = (const int num){char s[maxn];sprintf(s, "%d", num);*this = s;return *this;}bign operator = (const char* num){len = strlen(num);for (int i = 0; i < len; i++) s[i] = num[len - i - 1] & 15;return *this;}///输出const char* str() const{if (len){for (int i = 0; i < len; i++)numstr[i] = '0' + s[len - i - 1];numstr[len] = '\0';}else strcpy(numstr, "0");return numstr;}///去前导零void clean(){while (len > 1 && !s[len - 1]) len--;}///加bign operator + (const bign& b) const{bign c;c.len = 0;for (int i = 0, g = 0; g || i < max(len, b.len); i++){int x = g;if (i < len) x += s[i];if (i < b.len) x += b.s[i];c.s[c.len++] = x % 10;g = x / 10;}return c;}///减bign operator - (const bign& b) const{bign c;c.len = 0;for (int i = 0, g = 0; i < len; i++){int x = s[i] - g;if (i < b.len) x -= b.s[i];if (x >= 0) g = 0;else{g = 1;x += 10;}c.s[c.len++] = x;}c.clean();return c;}///乘bign operator * (const bign& b) const{bign c;c.len = len + b.len;for (int i = 0; i < len; i++)for (int j = 0; j < b.len; j++)c.s[i + j] += s[i] * b.s[j];for (int i = 0; i < c.len - 1; i++){c.s[i + 1] += c.s[i] / 10;c.s[i] %= 10;}c.clean();return c;}///除bign operator / (const bign &b) const{bign ret, cur = 0;ret.len = len;for (int i = len - 1; i >= 0; i--){cur = cur * 10;cur.s[0] = s[i];while (cur >= b){cur -= b;ret.s[i]++;}}ret.clean();return ret;}///模、余bign operator % (const bign &b) const{bign c = *this / b;return *this - c * b;}bool operator < (const bign& b) const{if (len != b.len) return len < b.len;for (int i = len - 1; i >= 0; i--)if (s[i] != b.s[i]) return s[i] < b.s[i];return false;}bool operator > (const bign& b) const{return b < *this;}bool operator <= (const bign& b) const{return !(b < *this);}bool operator >= (const bign &b) const{return !(*this < b);}bool operator == (const bign& b) const{return !(b < *this) && !(*this < b);}bool operator != (const bign &a) const{return *this > a || *this < a;}bign operator += (const bign &a){*this = *this + a;return *this;}bign operator -= (const bign &a){*this = *this - a;return *this;}bign operator *= (const bign &a){*this = *this * a;return *this;}bign operator /= (const bign &a){*this = *this / a;return *this;}bign operator %= (const bign &a){*this = *this % a;return *this;}
};bign c[1001] = {1};int main()
{bign i;int ii;for (i = 1, ii = 1; ii <= 1000; i = i + 1, ++ii)c[ii] = c[ii - 1] * ((i * 4) - 2) / (i + 1);while (~scanf("%d", &ii))puts(c[ii].str());return 0;
}
这篇关于UVa 10303 How Many Trees? (卡特兰数高精度)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
