C++ 整数拆分算法详解：从递推公式到代码实现

唐可

发布时间：2026-10-14 | 3人浏览过

原创

整数拆分是将一个正整数分解为若干个正整数之和的问题。本文以 C++ 为例，详细解析如何使用递推法计算整数拆分的方案数。核心在于定义状态 f(n,m)（表示最大加数不超过 m 的 n 的拆分方案数），并根据 n 与 m 的大小关系推导出递推公式，最后提供可直接运行的完整代码。

一、问题分析与定义

整数拆分是指将一个整数 n 分解成若干个整数的和。例如，整数 3 可以拆分为：

3 = 2 + 1
3 = 1 + 1 + 1

注意：在整数拆分中，顺序不影响结果，即 2+1 与 1+2 被视为同一种拆分方案。

为了计算拆分方案数，我们定义函数 f(n, m)：

n：待拆分的整数。
m：拆分中允许出现的最大整数（最大拆分数）。
f(n, m)：表示整数 n 的最大加数不大于 m 的拆分方案总数。

二、递推关系推导

根据 n 和 m 的不同大小关系，我们可以将问题分解为以下四种基本情况，从而建立递归或动态规划的递推式。

第1步：处理边界条件 (n=1 或 m=1)

当 n=1 时，只有一种拆分方式：1。
当 m=1 时，只能使用 1 进行拆分，即 1+1+...+1，也只有一种方案。
因此，这两种情况下的方案数均为 1：

f(n, m) = 1 （当 n=1 或 m=1 时）

第2步：处理 n = m 的情况

当最大加数 m 等于待拆分数 n 时，包含两种情形：

选取 m：即直接取 n=n，这算作 1 种方案。
不选取 m：此时最大加数必须小于 m，即最大加数为 m-1。方案数为 f(n, m-1)。

综合可得：
f(n, m) = f(n, n-1) + 1

第3步：处理 n < m 的情况

当最大加数 m 大于待拆分数 n 时，由于拆分出的整数不可能超过总和 n，所以参数 m 中大于 n 的部分是无效的。
此时可以将问题等价转化为最大加数为 n 的情况：

f(n, m) = f(n, n)

第4步：处理 n > m 的情况

这是最普遍的情况，我们将方案分为两类互斥的情况：

拆分式中包含 m：既然已经选了一个 m，剩余部分需要拆分为 n - m，且剩余部分的最大加数仍不能超过 m。这部分方案数为 f(n - m, m)。
拆分式中不包含 m：意味着所有加数都小于 m，即最大加数不超过 m-1。这部分方案数为 f(n, m - 1)。

综合可得：
f(n, m) = f(n, m - 1) + f(n - m, m)

三、 C++ 代码实现

基于上述递推关系，我们可以编写递归函数来实现整数拆分的计数。为了提升输入输出效率，示例代码使用了文件重定向（也可根据需要改为标准输入输出）。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

// 计算整数 n 拆分且最大加数不超过 m 的方案数
int f(int n, int m)
{
    // 边界条件：n=1 或 m=1 时，方案数为 1
    if (n == 1 || m == 1)
        return 1;
    
    // 当 n < m 时，等价于 f(n, n)
    if (n < m)
        return f(n, n);
    
    // 当 n == m 时，方案数为 f(n, n-1) + 1
    if (n == m)
        return 1 + f(n, n - 1);
    
    // 当 n > m 时，方案数为 f(n, m-1) + f(n-m, m)
    return f(n, m - 1) + f(n - m, m);
}

void work()
{
    int n, m;
    cin >> n >> m;
    cout << f(n, m);
}

int main()
{
    // 文件重定向：从 cut.in 读取数据，写入 cut.out
    // 若需直接在终端调试，可注释掉这两行并使用标准 cin/cout
    freopen("cut.in", "r", stdin);
    freopen("cut.out", "w", stdout);
    
    work();
    return 0;
}

代码说明：