塔兰数是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰(1814–1894)命名。
卡塔兰数满足以下递推关系
它的通项公式为
前几项为 : 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190...
应用:Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况:
- 输入
-
输入数据有十几组,每组一行,有一个正整数k(1<=k<=109)
- 输出
-
每组数据输出一行,为不小于k的最小的Catalan数
- 样例输入
-
5 10 20
- 样例输出
-
5 14 42
解题思路:此题其实很简单,输入1-10^9次方直接的catalan数都告诉你了,打表过。
#include <iostream> #include<cstdio> using namespace std; int main() { double number; int i; double a[]={1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452}; while(scanf("%lf",&number)!=EOF) { for(i=1;i<26;i++) { if(a[i]>=number) { printf("%.0lf\n",a[i]); break; } else { continue; } } } return 0; }