自然数的拆分

题目链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1318

方法一：DFS

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int ans[21];      //用于存放答案 
 4 int n, total;    //总方案数
 5 void pr(int d){   //按照要求打印答案 
 6     total+=1;
 7     cout<<n<<"=";
 8     for(int i=1; i<=d-1; i++)cout<<ans[i]<<"+";
 9     cout<<ans[d]<<endl;
10 }
11 void dfs(int dep, int rest){
12     if(rest==0){
13         if(dep>2){   //避免单独值的出现 
14             pr(dep-1);    
15             return;
16         }
17     }
18     for(int i=ans[dep-1]; i<=rest; i++){
19         ans[dep]=i;
20         dfs(dep+1, rest-i);
21     }
22 }
23 int main()
24 {
25     cin>>n;
26     ans[0]=1;//初始化拆，18行循环语句的初始值 
27     dfs(1, n);
28     //cout<<total;
29     return 0;
30 }

方法二：回溯法

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int ans[21];      //用于存放答案
 4 int n, total;    //总方案数
 5 void pr(int d){   //按照要求打印答案
 6     total+=1;
 7     cout<<n<<"=";
 8     for(int i=1; i<=d-1; i++)cout<<ans[i]<<"+";
 9     cout<<ans[d]<<endl;
10 }
11 void dfs(int dep, int rest){
12     if(rest==0){
13         if(dep>2){   //避免单独值的出现
14             pr(dep-1);
15             return;
16         }
17     }
18     for(int i=ans[dep-1]; i<=rest; i++){
19         ans[dep]=i;
20         rest=rest-i;
21         dfs(dep+1, rest);
22         rest=rest+i;
23     }
24 }
25 int main()
26 {
27     cin>>n;
28     ans[0]=1;//初始化拆，18行循环语句的初始值
29     dfs(1, n);
30     //cout<<total;
31     return 0;
32 }

回溯法与深度优先搜索的关系
原文链接: https://www.cnblogs.com/tflsnoi/p/13689306.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍