【递归】整数划分（C++）

article/2025/10/7 20:25:31

一、什么是整数划分

所谓整数划分，是指把一个正整数n写成如下形式： $n=m_1+m_2+···+m_i$ ；
其中 $m_i$ 为正整数，并且 $\leq m_i \leq n$ ，则 ${m_1,m_2,···,m_i\}$ 为n的一个划分。
如果 ${m_1,m_2,···,m_i\}$ 中的最大值不超过m，即 $max(m_1,m_2,…,m_i) \leq m$ ，则称它属于n的一个m划分。
例如：当n=4时，它有5个划分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};
　　注意4=1+3和4=3+1被认为是同一个划分。
整数划分问题就是求出 n 的所有划分个数。

二、递归算法实现

1. 设计递归方程

思考：根据n和m的关系，有以下几种情况：（引用“百度百科”）

当n=1时，不论m的值为多少（m>0)，只有一种划分即{1}；
当m=1时，不论n的值为多少，只有一种划分即n个1，{1,1,1,…,1}；
当n=m时，根据划分中是否包含n，可以分为两种情况：
1. 划分中包含n的情况，只有一个即{n}；
2. 划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有(n-1)划分。
3. 因此 $f (n, n) = 1 + f (n, n - 1)$ 。
当n<m时，由于划分中不可能出现负数，因此就相当于 $f (n, n)$ ；
当n>m时，根据划分中是否包含最大值m，可以分为两种情况：
1. 划分中包含m的情况，即 ${m,\{x_1,x_2,···,x_i\}\}$ ，其中 ${x_1,x_2,···,x_i\}$ 的和为n-m，可能再次出现m，因此是（n-m）的m划分，因此这种划分的个数为 $f (n - m, m)$ ；
2. 划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划分，个数为 $f (n, m - 1)$ ；
3. 因此 $f (n, m) = f (n - m, m) + f (n, m - 1)$ 。

综上所述：
$\begin{cases} f(n, m)= 1 & n=1 || m=1 \\ f(n, n) & n<m \\ 1+ f(n, m-1) & n=m \\ f(n-m,m)+f(n,m-1) & n>m \end{cases}$

2. 编写程序代码

此程序不仅计算了划分个数，而且输出打印了所有的划分形式（移除show()函数可移除此功能）。
注：show()函数曾借鉴学习于一位博主，但是找不到这位了qaq。

// 整数划分的递归实现算法
#include <iostream>
#include <string>
using namespace std;int int_HuaFen(int n, int m);
void show(int n, int m, string s);int main()
{string s; // 用于展示所有整数划分形式int n = 1; // 用于整数划分的整数cout << "请输入一个正整数进行整数划分：";cin >> n;cout << "全部划分为：" << endl;show(n, n, s);cout << "划分数为：" << int_HuaFen(n, n) << endl;return 0;
}// 递归计算划分数
int int_HuaFen(int n, int m)
{if (n == 1 || m == 1)return 1;else if (n < m)return int_HuaFen(n, n);else if (n == m)return 1 + int_HuaFen(n, n - 1);elsereturn int_HuaFen(n, m - 1) + int_HuaFen(n - m, m);
}// 递归展示所有划分形式
void show(int n, int m, string s) {if (n == 1 || m == 1) {for (int i = 0; i < n - 1; i++)s += string("1+");cout << s << "1\n";return;}else if (m > n) {return show(n, n, s);}else if (n == m) {cout << s << n << endl;return show(n, m - 1, s);}if (n - m != 0)show(n - m, m, s + to_string(m) + string("+"));elsecout << s << m << endl;show(n, m - 1, s);
}