和尚的烦恼（卡特兰数）

我就是我 2022-05-23 12:58 160阅读 0赞

## 问题 : 和尚的烦恼4 ##

## 题目描述 ##

小和尚每日练武真的是很累啊，但是为了以后更和谐。也没有办法了，只能天天那刻苦了；有一日练武结束后去找师傅聊天，猛然间，师傅说到，其实在这个世界上想混的好的话，光武功高是不行的，也要能喷能聊，你们要多读书了，从此以后小和尚每天都要抽出一部分时间来读书，有一天看到了一个叫卡特兰数的东西，看了半天你没有看懂，只知道是个数列，因此想让小朋友们帮忙找到数列前边的一些卡特兰数；快快帮忙吧；  
注:　卡特兰数递推关系的解为：  
h(n)=C(2n,n)/(n + 1) (n=1,2,3,)

## 输入 ##

输入数据有多组，每组数据首先输入一个整数n(n<=30). 然后有n个正整数m(每个正整数m<50)；

## 输出 ##

对于每个正整数m,输出相应的卡特兰数，每个数占一行；

## 样例输入 ##

3
    1
    2
    3

## 样例输出 ##

1
    2
    5

## 题意描述： ##

求出前50项卡特兰数。

## 解题思路： ##

从网上查找卡特兰数的通项是c(2n, n)/(n+1)。

计算：a(n)=a(0)×a(n-1)+a(1)\*a(n-2)+...+a(n-1)\*a(0)。

## 程序代码： ##

#include<stdio.h>   
    long long a[55];  
    int main()  
    {  
        int t,n,m,i,j;  
        a[0]=a[1]=1;a[2]=2;  
        for(i=3;i<=50;i++)  
        {  
            m=i-1;  
            for(j=0;j<i;j++)  
            {  
                a[i]+=a[j]*a[m];  
                m--;  
            }  
        }  
        scanf("%d",&t);  
        while(t--)  
        {  
            scanf("%d",&n);  
            printf("%lld\n",a[n]);  
        }  
        return 0;  
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关卡特兰数

告诉你一个非常好用的方法，你学还是不学？今天给大家分享的是在组合数学中用途非常广泛的数列，它的名字叫做卡特兰数！！！下面有道力扣题，如果让你30秒给出答案，你觉得有没有

Bertha 。/ 2023年10月09日 23:29/ 0 赞/ 49 阅读

相关卡特兰数归纳

卡特兰数文章目录卡特兰数参考卡特兰数定义从递推式

秒速五厘米/ 2022年09月12日 11:51/ 0 赞/ 354 阅读

相关卡特兰数

[组合数学：卡特兰数 ][Link 1] 卡特兰数又称卡塔兰数，是[组合数学][Link 2]中一个常出现在各种计数问题中出现的[数列][L

ゝ一世哀愁。/ 2022年08月07日 15:58/ 0 赞/ 405 阅读

相关卡特兰数

　Catalan数　　中文:卡特兰数　　原理：　　令h(1)＝1,h(0)=1，catalan数满足递归式：　　h(n)= h(1)\h(n-1) + h(2)

旧城等待，/ 2022年08月05日 05:15/ 0 赞/ 238 阅读

相关算法-数论-卡特兰数

卡塔兰数是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。令h(0)=1,h(1)=1，catalan数

我会带着你远行/ 2022年08月04日 13:34/ 0 赞/ 225 阅读

相关算法卡特兰Catalan数

介绍 Catalan数是组合数学中一个常在各种计数问题中出现的数列。一般项公式为 ![这里写图片描述][104330_1eSF_2243330.png] Cn的另一个

我不是女神ヾ/ 2022年06月08日 08:52/ 0 赞/ 240 阅读

相关卡特兰数

卡特兰数是组合数学中的一个重要概念。卡特兰数可以解决以下四种典型的问题： 1.括号化问题矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用

心已赠人/ 2022年06月08日 01:23/ 0 赞/ 594 阅读

相关和尚的烦恼（卡特兰数）

问题 : 和尚的烦恼4 题目描述小和尚每日练武真的是很累啊，但是为了以后更和谐。也没有办法了，只能天天那刻苦了；有一日练武结束后去找师傅聊天，猛然间，师

我就是我/ 2022年05月23日 12:58/ 0 赞/ 161 阅读

相关卡特兰数

问题引出若一序列进栈顺序为e1,e2,e3,e4,e5,问存在多少种可能的出栈序列（）问题分析 ![这里写图片描述][70] ![这里写图片描述][70

╰半夏微凉°/ 2022年05月18日 01:04/ 0 赞/ 238 阅读

相关卡特兰数（catalan number）

1. 卡特兰数是什么卡塔兰数是[组合数学][Link 1]中一个常在各种计数问题中出现的[数列][Link 2]。公式为： ![C\_n = \\

青旅半醒/ 2022年04月14日 02:16/ 0 赞/ 264 阅读