一、题目

整数划分问题（写不出代码的同学，请给出7，8的整数划分，拍照上传。请注意图片不要旋转和倒置）
将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，
其中n1≥n2≥…≥nk≥1，k≥1。
正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。
例如正整数6有如下11种不同的划分：
6；
5+1；
4+2，4+1+1；
3+3，3+2+1，3+1+1+1；
2+2+2，2+2+1+1，2+1+1+1+1；
1+1+1+1+1+1。
输入正整数n的值，输出n的划分种类数及具体的划分情况。测试值（n=6，n=7）
当n=6时，则输出：共有11划分，分别为：
6=6；
6=5+1；
.................................
6=1+1+1+1+1+1;

二、分析

1.求总数的算法
根据题目的含义：如果x1+x2+x3…+xn=n 即为它的一个划分组，
如果取m=max{x1,x2,x3…,xn},则m为它的一个划分组，记作f（n，m）。
Ps： m只是它的最大值 不代表他必须包含m
本题主要是用递归法取得结果 主要分为以下几种结果：
（1）f（n,m）=f（1,1）时 显而易见等于1
（2）当m[HTML_REMOVED]n时，主要分为两种情况
第一种：划分中包含最大值m，那么相当于f（n-m,m）。因为已经说了包含最大值，那么就相当于固定了最大值在里面，减去m，划分方法也是相同的，所以就是f（n-m,m）
第二种：划分中不包含最大值m，因为最大值可以取m，自然也有不取得m的情况，可以取试试看取得m-1，根据递归算法，可以找到其最终结果f（n，m-1）
（4）当m=n时，f（n，m）=1+f（n，m-1）分为两种情况
第一种包含最大值时，仅有一种情况。
第二种，就相当于（3）的第二种

2.dfs输出划分种类
这是一个很经典的dfs问题，可以使用深度优先遍历。类似于多叉树，第一行取6,5,4,3,2,1；这里就举m=3的例子，此时第二行=3，那么还剩余p=3，从大往小取，可以第三行可以取3，这就结束了一组，返回上级，可以取2，此时底下就可以取1，并且满足要求，逐层递减的要求。根据这个方式，可以使用递归的方式，让原本的n，变为剩余值产生递归的效果，然后把数据依次存入数组num中，成功一组最大值数组，Ps:m=5为一组 m=4为一组。然后返回到代码的if（！p）即可。

代码

include[HTML_REMOVED]

int n;
const int N = 1e3 + 25;
int num[N];
int f(int n,int m)
{
if(m==1||n==1||n==0)
return 1;
else if(n<m)
return f(n,n);
else if(n==m)
return f(n,m-1)+1;
else
return f(n-m,m)+f(n,m-1);
}

void dfs(int k, int p, int mx)
//mx指的是上一层的数 p指的是当前剩余值 i指的是上一层给下一层的数 k指的是加法顺序
{
if(!p)
{
printf(“%d= “,n);
for(int i=0;i[HTML_REMOVED]0; –i) //把当前剩余值（下一层的数）传递给i
{
num[k]=i;
if(i<=mx) dfs(k+1,p-i,i);//此时i指的是剩余数相当于p 当下一层数小于上一层不可取
}//先进入for 存储数据到num中 直到剩余值小于0即输出首位相同数字进入if

}

int main()
{
printf(“请输入所要划分的数字：”);
scanf(“%d”,&n);
printf(“划分结果共有%d种\n”,f(n,n));
dfs(0,n,n+1);

}