用c语言计算组合·数cmn

在C语言中，组合数（Combinatorial number, 也称为“从n个不同元素中取出m个元素的组合数”，记作 C(n, m) 或者 n! / (m!(n-m)!)) 可以通过公式直接计算，其中 `!` 表示阶乘。以下是使用递归或迭代的方式实现组合数计算：

**递归方式**:

#include <stdio.h>

int factorial(int n) {
    if (n == 0 || n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

int combination(int n, int m) {
    if (m > n || m < 0)
        return 0; // 条件错误
    else
        return factorial(n) / (factorial(m) * factorial(n - m));
}

int main() {
    int n, m;
    printf("请输入总元素数量n和选取元素数量m：");
    scanf("%d %d", &n, &m);
    printf("C(%d,%d) = %d\n", n, m, combination(n, m));
    return 0;
}

**迭代方式**:
如果要优化递归，可以使用动态规划存储中间结果以减少重复计算。这里需要一个大小为 `(n+1)` 的数组 `dp`，因为组合数最多只到 `C(n,n)`。

#include <stdio.h>

int combination_iterative(int n, int m) {
    if (m > n || m < 0)
        return 0;

    int dp[n + 1];
    for (int i = 0; i <= n; ++i)
        dp[i] = 1; // 初始化为1

    for (int i = 2; i <= n; ++i)
        for (int j = 1; j < i; ++j)
            dp[j] = dp[j] * i;

    return dp[m];
}

int main() {
    int n, m;
    printf("请输入总元素数量n和选取元素数量m：");
    scanf("%d %d", &n, &m);
    printf("C(%d,%d) = %d\n", n, m, combination_iterative(n, m));
    return 0;
}