c++递推代码 输入一个正整数n。 输出描述 输出Catalan数的前n项。 用例输入 1 0 用例输出 1 1 用例输入 2 5 用例输出 2 1 1 2 5 14 42

C++中递归实现Catalan数的代码通常用于计算组合数学中的序列，Catalan数是一个常见的数学问题，其第n项C(n)有一个递推公式：

C(0) = 1
C(1) = 1
对于n > 1:
C(n) = (4 * n - 2) / (n + 1) * C(n - 1)

下面是一个递归版本的C++代码示例：

#include <iostream>
using namespace std;

int catalan(int n) {
    if (n <= 1)
        return n;
    else
        return (4 * n - 2) / (n + 1) * catalan(n - 1);
}

int main() {
    int n;
    cout << "请输入一个正整数n: ";
    cin >> n;
    
    for (int i = 0; i <= n; ++i) {
        cout << catalan(i) << ' ';
    }
    cout << endl;

    return 0;
}

当你运行这个程序并输入不同的`n`值，它会输出Catalan数的前n项。比如，如果你输入2，输出将是`1 1 2`。

相关问题

c++求组合数描述 输入两个整数m,n，求m个数字中选n个数的组合数。（1<=n<=m<=100） 用例输入 1 5 3 用例输出 1 10

在C++中，求组合数可以使用多种方法，其中一种常用且简单的方法是利用递归公式 C(m, n) = C(m-1, n-1) + C(m-1, n)，同时利用组合数的性质 C(m, n) = C(m, m-n) 来减少计算量，特别是当n > m/2时。另外，可以使用帕斯卡三角形来递推组合数，或者直接使用公式 C(m, n) = m! / (n! * (m-n)!) 来计算，但直接使用阶乘会涉及到大量的重复计算，因此一般使用递归或者迭代的方式来优化计算过程。

下面是一个使用递归方法的示例代码：

#include <iostream>
using namespace std;

int C(int m, int n) {
    if (n == 0 || n == m) {
        return 1;
    } else {
        return C(m - 1, n - 1) + C(m - 1, n);
    }
}

int main() {
    int m, n;
    cin >> m >> n;
    cout << C(m, n) << endl;
    return 0;
}

这段代码中，函数C是用来计算组合数的递归函数。为了避免重复计算，可以使用动态规划的方法，将已经计算过的组合数存储起来以备后用。

另外，由于问题中提到的是1<=n<=m<=100，直接使用递归可能会导致大量的重复计算和栈溢出的风险。因此，实际应用中可以使用动态规划优化过的代码，或者使用迭代的方式计算阶乘来避免递归的复杂性。