如何用C语言求组合数

创作时间:

作者:

@小白创作中心

如何用C语言求组合数

引用

来源

https://docs.pingcode.com/baike/1228775

如何用C语言求组合数

使用递归、利用动态规划、直接计算公式。我们将详细介绍如何利用这三种方法在C语言中求解组合数，并解释每种方法的优缺点。

1、递归方法

递归方法是最直观的一种计算组合数的方法。组合数C(n, k)可以通过递归关系来定义，即C(n, k) = C(n-1, k-1) + C(n-1, k)。这种方法的优点是简单明了，但缺点是对于大规模问题效率较低。

递归方法详解

代码示例：

#include <stdio.h>

// 递归函数计算组合数C(n, k)
int combination_recursive(int n, int k) {
    // 边界条件
    if (k == 0 || k == n)
        return 1;
    // 递归计算
    return combination_recursive(n - 1, k - 1) + combination_recursive(n - 1, k);
}

int main() {
    int n = 5, k = 2;
    printf("C(%d, %d) = %d\n", n, k, combination_recursive(n, k));
    return 0;
}

优缺点分析：

优点：代码简单，逻辑清晰。

缺点：对于大规模的组合数计算，效率较低，容易导致栈溢出。

2、动态规划方法

动态规划是一种优化递归的方法，通过将中间结果存储起来避免重复计算，从而提高效率。动态规划表格（二维数组）可以用来存储所有可能的组合数。

动态规划方法详解

代码示例：

#include <stdio.h>
#include <stdlib.h>

// 动态规划函数计算组合数C(n, k)
int combination_dp(int n, int k) {
    int **dp = (int **)malloc((n + 1) * sizeof(int *));
    for (int i = 0; i <= n; i++)
        dp[i] = (int *)malloc((k + 1) * sizeof(int));
    // 初始化DP表格
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= (i < k ? i : k); j++) {
            if (j == 0 || j == i)
                dp[i][j] = 1;
            else
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
    }
    int result = dp[n][k];
    // 释放内存
    for (int i = 0; i <= n; i++)
        free(dp[i]);
    free(dp);
    return result;
}

int main() {
    int n = 5, k = 2;
    printf("C(%d, %d) = %d\n", n, k, combination_dp(n, k));
    return 0;
}

优缺点分析：

优点：避免了递归方法中的重复计算，效率更高。

缺点：需要额外的存储空间来保存中间结果。

3、直接计算公式

直接计算组合数的公式为C(n, k) = n! / (k! * (n – k)!)。该方法通过计算阶乘来获得结果。虽然直观，但对于大数值可能会导致溢出问题。

直接计算公式方法详解

代码示例：

#include <stdio.h>

// 计算阶乘
long long factorial(int n) {
    long long result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

// 直接使用公式计算组合数C(n, k)
long long combination_formula(int n, int k) {
    return factorial(n) / (factorial(k) * factorial(n - k));
}

int main() {
    int n = 5, k = 2;
    printf("C(%d, %d) = %lld\n", n, k, combination_formula(n, k));
    return 0;
}