本文主要是介绍洛谷P2404 自然数的拆分问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
弱鸡上路，刷搜索题的第一天。
传送门：https://www.luogu.com.cn/problem/P2404
这是一道比较简单的搜索题（但我还是不会做qwq）题目没有什么要分析的，但是最好把题目的例子看完再自己举个例子算一算，完了之后不会再看题解。代码段里的注释很清楚（应该吧），直接上代码
#include<iostream>
using namespace std;
int Array[10] = { 0 }, n = 0;
//Array数组用来存放拆出来的数，n是要拆的自然数
//用全局变量是为了简化下面自定义函数的参数表
void Print(int step)
{for (int i = 1; i <= step; i++){if (i == 1)printf("%d", Array[i]);else printf("+%d", Array[i]);}printf("\n");
}
//自定义一个Print函数来打印答案
void DFS(int number, int cursum, int step)
{//number指当前要拆出的数，cursum指当前拆数总和，step为第几个数if (number == n)return;//当拆出的数为n时直接退出，防止单输出nif (cursum == n){Print(step - 1);return;}//当总和等于n时找到答案直接输出//这边Print的参数为step-1是因为当满足if的条件时//step的数值比实际要输出的step大一，所以要减掉for (int i = number; i <= n - cursum; i++){//写循环是为了枚举拆出的数的各种可能性//例如4=1+1+1+1，4=1+1+2，第三个拆数可能等于1也可能等于2//因此用循环来实现第三个拆数第一次进循环是1，第二次进变成2Array[step] = i;//第step个拆数为i，保存在数组里DFS(i, cursum + i, step + 1);//继续向下搜索，由于拆出来的数要按字典序，且可以重复//所以下一个拆数的第一选择为上一个拆数，即i//例如5=1+1+1+1+1和5=1+2+2//cursum增加i，step++（下一个数）}//如果这一段循环看不懂的话可以把代码拿去编译器上运行//用监视窗口观察每个数值的变化或者在纸上模拟运行以便于理解
}
int main(void)
{scanf("%d", &n);DFS(1, 0, 1);//除了0任何自然数第一个拆出来的都是1，所以number参数为1//cursum初始值为0，step初始值为1//我没有考虑n等于0的情况，不然应该加上一个是否为0的判定return 0;//完结撒花
}除了直接DFS外，我看到一位大佬考虑到了一旦数的规模太大，递归会爆栈，就直接用手写栈模拟递归工作栈orz，给了我很大启发，于是我这边用栈再写一次。
当然，最好在DFS已经看懂的情况下再看栈实现（注释写得不是很清晰）。
#include<iostream>
using namespace std;
int Stack[10] = { 0 }, step = 0;
//还是全局变量，方便后面书写
void Print(int step)
{if (step == 1)return;//防止输出单个nfor (int i = 1; i <= step; i++){if (i == 1)printf("%d", Stack[i]);else printf("+%d", Stack[i]);}printf("\n");
}
//Print函数输出
int main(void)
{int n = 0, sum = 1, top = 1;//sum为栈内数之和,初始化为1的原因在下面，top为栈顶指针Stack[1] = 1;//这个初始化是为了后面计算的方便//这个栈已经压入了一个值等于1的元素了//因此总和sum的初始化值为1scanf("%d", &n);while (top >= 1) {//这个栈的栈顶指针直接指向栈顶元素if (sum < n) {Stack[top+1] = Stack[top];sum += Stack[top++];}//当目前栈内总和小于n时，就进栈//同时栈内总和增加else {if (sum == n)Print(top);//相等时直接打印sum -= Stack[top--];Stack[top]++;sum++;/*不管是大于还是等于n，栈顶元素都要弹出并且把弹出后的栈顶元素加一*/}}return 0;//完结撒花
}这篇关于洛谷P2404 自然数的拆分问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
