|
Hello！我是C风，专注与算法以及Java的学习，今天我们就来看一下数的拆分这个题目，并由此来总结一下递归算法。
话不多说，我们先来看一下这道题目：
题目描述：
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。现在给你一个自然数n，要求你求出n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。
输入格式：
输入：待拆分的自然数n。
输出格式：
输出：若干数的加法式子。
输入：
7
输出：
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4
这个题目就是将一个数不断拆分的过程，这里我们观察发现输出的首项是小于输入数字的一半的，我们首先就要想一下这个过程是如何的。
这其实就是一个DFS题目，首先就是将7拆分成1，2，3；之后再将拆分之后的数继续拆分直到最后只剩0；所以只要这样一想，我们就直到这是一道的典型的DFS题，按照我上一篇博客讲的，这里的递归结束条件就是不能继续拆分，另外一个需要注意的点拆分层的下一层的数要比该层大或者相等，也就是说第一步拆分2后就不能再拆1了
所以这样一想我们的关键函数就可以写出来了,不一定要if语句来表示递归结束的条件，这里我们输入数据后在循环条件里面就会自己进入下一个分支，当num == 1时循环就会结束，也就是没有其他的分支时那就会结束，所以我们就不要过于死板，这里就在for循环的下面加上递归结束的配套代码即可。这里主要时一开始没有思考，不知道start的作用。这个start的作用就是让子支大于等于主支，并且在循环过程中会自动更新num的值。
int DFS(int num,int loadnum, int start)
{//loadnum记录我们输入的数，因为再递归时num会变化
for (int i = start; i <= num / 2; i++)//这里就是找不到分支的时候结束循环
{//所以就不需要另加结束条件，但是要删除一个num = 4
Load[t] = i;
t++;
DFS(num - i,loadnum, i);
t--;
}
if (num == loadnum)
{
return 0;//这样也结束
}
cnt++;
Load[t] = num;
print(Load);
return 0;// 递归结束条件就是不满足上述关系
}
接下来就是我们的打印函数了，这里就只需要注意一下打印的格式就好了
void print(int* Load)
{
for (int i = 0; i < t; i++)
{
printf("%d+", Load[i]);
}
printf("%d\n", Load[t]);
}
之后的主函数当然就不需要解释了，但是为了代码的完整性，我还是也上传一下
int cnt = 0;
int Load[10];
int t = 0;
············
int main()
{
int num;
int loadnum;
cin >> num;
loadnum = num;
DFS(num,loadnum, 1);
//printf("%d", cnt);//这个可以记录一共有多少种拆法
}
这里我定义了几个全局变量，其实是可以变成非全局变量的，这里以减少全局变量t为例，我们可以在主函数里定义一个t，然后在DFS函数与print函数里都加一个变量，这样其范围就减少很多了，但是我们需要注意这是值传递，t的值本身没有变化。
|