hdu 1130 How Many Trees?(卡特兰数,大数的乘法与除法)
发布时间:2020-12-14 02:24:39 所属栏目:大数据 来源:网络整理
导读:原题链接: http://acm.hdu.edu.cn/showproblem.php?pid=1130 题目大意: n个结点所能构成的多少种不同的搜索二叉树。 卡特兰数:(令 h(0)=1,h(1)=1 ) ① 递推式: F (n)= F(0)*F(n-1)+F(1)*F(n-2) + ... + F(n-1)*F(0) ?(n=2) 通项式: F (n)=C(2n,n) / (n+
原题链接: http://acm.hdu.edu.cn/showproblem.php?pid=1130 题目大意: n个结点所能构成的多少种不同的搜索二叉树。 卡特兰数:(令h(0)=1,h(1)=1)
① 递推式:F(n)= F(0)*F(n-1)+F(1)*F(n-2) + ... + F(n-1)*F(0) ?(n>=2)
通项式:F(n)=C(2n,n) / (n+1) ? ?(n=0,1,2,...)
② 递推式:F(n)=F(n-1)*(4*n-2)/(n+1);
通项式:F(n)=C(2n,n)-C(2n,n-1) ? ? ?(n=0,...)
代码如下:
(②递推式)
#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> using namespace std; const int base = 10000; const int N = 100 + 2; int katelan[N][N]; int main() { katelan[1][1] = 1; katelan[2][1] = 2; katelan[3][1] = 5; for (int i = 4; i <= 100; i++) { for (int j =1; j<100; j++)//大数乘法 { katelan[i][j] += katelan[i - 1][j] * (4 * i - 2); katelan[i][j + 1] += katelan[i][j] / base; katelan[i][j] %= base; } int temp; for (int j = 100; j > 0; j--)//大数除法 { temp=katelan[i][j] % (i + 1); katelan[i][j-1]+=temp* base; katelan[i][j] /= (i + 1); } } int n; while (cin >> n) { int i = 100; while (katelan[n][i] == 0)i--; cout << katelan[n][i--]; while (i > 0) printf("%04d",katelan[n][i--]); cout << endl; } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |