C语言实现整数划分：算法详解与代码优化155

整数划分问题是一个经典的组合数学问题，其描述如下：将正整数 *n* 划分成若干正整数之和，有多少种不同的划分方法？例如，整数 5 可以划分成以下几种方式：5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1。 这个问题的求解方法有很多，本文将重点介绍几种常见的 C 语言实现方法，并对代码进行优化，提高算法效率。

一、 递归方法

最直观的解法是使用递归。我们可以定义一个递归函数 `partition(n, m)`，其中 `n` 是要划分的整数，`m` 是当前可以使用的最大整数（初始值为 `n`）。当 `n` 等于 0 时，表示找到一种划分方法，返回 1；当 `n` 小于 0 时，表示当前划分方法不合法，返回 0；当 `m` 等于 0 时，表示没有找到合法划分方法，返回 0。递归的思路是：对于每个 `m`，我们可以选择使用它或不使用它。如果使用 `m`，则问题转化为 `partition(n - m, m)`；如果不使用 `m`，则问题转化为 `partition(n, m - 1)`。最终结果是这两种情况的和。
#include
int partition(int n, int m) {
if (n == 0) return 1;
if (n < 0 || m == 0) return 0;
return partition(n - m, m) + partition(n, m - 1);
}
int main() {
int n;
printf("请输入要划分的整数 n: ");
scanf("%d", &n);
printf("整数 %d 的划分方法总数为: %d", n, partition(n, n));
return 0;
}

这种递归方法简单易懂，但是效率极低。因为存在大量的重复计算，时间复杂度非常高，对于较大的 `n` 值，计算时间会呈指数级增长。因此，这种方法只适用于处理较小的整数。

二、 动态规划方法

为了提高效率，可以使用动态规划方法。我们可以创建一个二维数组 `dp[n+1][n+1]`，其中 `dp[i][j]` 表示将整数 `i` 划分成最大数不超过 `j` 的划分方法总数。我们可以通过递推公式计算 `dp[i][j]`：
当 `i` 等于 0 时，`dp[i][j] = 1`；
当 `j` 等于 0 时，`dp[i][j] = 0`；
否则，`dp[i][j] = dp[i][j-1] + dp[i-j][j]`。


#include
int partition_dp(int n) {
int dp[n + 1][n + 1];
for (int i = 0; i

2025-06-04

上一篇：C语言函数详解：从入门到进阶

下一篇：C语言循环结构及输出结果详解：从基础到进阶