c++写组合数公式代码

可以使用递归公式计算组合数，也可以使用杨辉三角等方式来计算。以下是使用递归公式计算组合数的代码：

#include <iostream>

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

int main() {
    int n, k;
    std::cout << "Enter n and k: ";
    std::cin >> n >> k;
    std::cout << "C(" << n << "," << k << ") = " << combination(n, k) << std::endl;
    return 0;
}

其中 `combination` 函数使用了递归公式 C(n,k) = C(n-1,k-1) + C(n-1,k) 来计算组合数。如果 k 等于 0 或 n，返回 1；否则递归计算 C(n-1,k-1) 和 C(n-1,k) 并相加返回结果。

相关问题

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，直接使用递归可能会导致大量的重复计算和栈溢出的风险。因此，实际应用中可以使用动态规划优化过的代码，或者使用迭代的方式计算阶乘来避免递归的复杂性。

c++求大组合数 题目描述 从1到n这些整数中，选m个数的组合的个数。用这个公式计算： n!是n的阶乘表示1*2*3*……*n n很大时这个结果会特别大，请输出组合数模100000007的结果 输入 两个整数 n，m 输出 一个整数

在 C++ 中，计算大组合数通常涉及动态规划，特别是当涉及到模运算时，因为直接计算阶乘可能导致数值溢出。你可以使用 Lucas 定理或递推算法结合取模操作来解决这个问题。这里是一种常见的做法，即使用 `modular_inverse` 函数来处理模逆和乘法的优化。

#include <iostream>
using namespace std;

// 计算 a * b mod p 的快速幂方法
long long modular_multiply(long long a, long long b, int p) {
    long long res = 0;
    a %= p;
    while (b > 0) {
        if (b % 2 == 1) {
            res = (res + a) % p;
        }
        a = (a * 2) % p; // 使用双倍法加速乘法
        b /= 2;
    }
    return res;
}

// 计算阶乘模 p 的逆元
long long modular_inverse(long long num, int p) {
    long long inv = 1, temp = p;
    for (int i = 2; i <= num / temp; ++i) {
        inv = (inv * temp) % p;
        temp = (temp * temp) % p;
    }
    return (num * inv) % p;
}

// 用 Lucas 定理计算组合数
long long combination(int n, int m, int p) {
    if (m > n || m < 0 || n < 0)
        return 0;

    long long fact[n + 1], inv_fact[n + 1];
    fact[0] = inv_fact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = fact[i - 1] * i % p;
        inv_fact[i] = modular_inverse(fact[i], p);
    }

    long long res = fact[n];
    res = modular_multiply(res, inv_fact[m], p);
    res = modular_multiply(res, inv_fact[n - m], p);

    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    cout << "组合数 mod 100000007: " << combination(n, m, 100000007) << endl;
    return 0;
}

在这个代码中，我们首先计算了阶乘和它们的逆元，然后利用组合数公式 `C(n, m) = n! / [m!(n-m)!]` 来计算组合数，并在每次乘法中都对 `p` 取模，避免数值溢出。输入 n 和 m 后，程序将输出 n 个数中选 m 个的组合数，结果对 100000007 取模。