正整数分解
题目编号：Exp08-Basic01，GJBook3-12-05
题目名称：正整数分解
题目描述：正整数n，按第一项递减的顺序依次输出其和等于n的所有不增的正整数和式。
输入：一个正整数n（0<n≤15）。输出：每行输出如样例所示，和等于n的不增正整数和式，数字和运算符间无符号，最后一行结尾有一个回车换行符。
样例：
输入： 4输出： 4=3+1 4=2+2 4=2+1+1 4=1+1+1+1
这道题虽然看上去很简单，但是实际上也很简单（误）
深度优先搜索（DFS，Depth-First Search)是搜索的手段之一。它从某个状态开始，不断地转移状态直到状态无法转移，然后退到前一步的状态，继续转移到其他状态，如此不段重复，直到找到最终的解。
如求解本题，首先在数组内填入适当的数字，然后继续在下一个位置填入符合题目要求的数字，如此继续下去。如果发现某个数字下面不能再填入数字了，则将数组打印输出，随后继续回到上一个数字搜索其他情况。
跟据深度优先搜索的特点，采用递归函数实现比较简单
下面我们来看一下求解本题的思路：
题目要求，“
第一项递减
的顺序依次输出其和等于n的所有
不增
的正整数和式
”，其中关键字已标红
通过下面的代码来实现
void dfs(int x, int y,int i)//x为要分解的总量，y为最大值，i为数组下标
{
if (x <= y)//此时满足题意，可以直接打印输出
{
a[i] = x;
Print(i);
}
for (int z = 1;z < x;z++)
{
if (x - z <= y)
{
a[i] = x - z;
dfs(z, x - z, i + 1);
}
}
}
dfs函数有三个参数，
x代表需要进行分解操作的总量；
y表示已分解出数字的最大值；
i则保存数组下标，方便给数组元素赋值。
基于此，我们在main函数中调用DFS时以此形式 dfs(n,n-1,0)，
以n=4为例 dfs(4,3,0)
进入dfs函数后（有条件的话大家可以拿着纸笔在纸上写写画画）
- 此时不满足4<=3，进入for循环
- 第一次for循环，z=1，x-z=3，此时x-z<=y， 把x-z存放到数组的第一位即a[0]
- 调用dfs(1,3,1),此时满足 1<=3 , 把x存到a[1],输出数组
3 1 - 第二次for循环，z=2, x-z=2, 此时x-z<=y, 把x-z存放到数组的第一位即a[0],因为上次在dfs循环中传入的为 dfs(z, x - z, i + 1) ，所以实际上 i 的值不变，仍为1
- 调用dfs(2,2,1),此时满足 2<=2 , 把x存到a[1],输出数组
2 2 - 然后进入第二次for循环中的第一次for循环，此时 z=1，x=2, x-z=1, 此时x-z<=y，把x-z存放a[1], 调用dfs(1,1,2)
- 此时满足1<=3，把1存到a[2],打印数组
2 1 1 - 最后调用一次dfs，输出数组
1 1 1 1 -
游戏结束，芜湖！！！
相比之下，打印的函数就显得尤为很简单了呀
void Print(int i)//打印输出已排好的数组
{
printf("%d=%d", n, a[0]);
for (int j = 1;j <= i;j++)
{
printf("+%d", a[j]);
}
printf("\n");
}
综上，总代码如下
#include <iostream>
using namespace std;//DFS
int a[20];
int n;
void Print(int i)//打印输出已排好的数组
{
printf("%d=%d", n, a[0]);
for (int j = 1;j <= i;j++)
{
printf("+%d", a[j]);
}
printf("\n");
}
void dfs(int x, int y,int i)//x为要分解的总量，y为最大值，i为数组下标
{
if (x <= y)//此时满足题意，可以直接打印输出
{
a[i] = x;
Print(i);
}
for (int z = 1;z < x;z++)
{
if (x - z <= y)
{
a[i] = x - z;
dfs(z, x - z, i + 1);
}
}
}
int main()
{
scanf_s("%d", &n);
dfs(n, n - 1, 0);
return 0;
}
