6 条题解
-
17
拿走不谢
#include <iostream> #include <cmath> using namespace std; int n, a[15],cnt; void dfs(int sum,int x) { if (sum == 0) { if(cnt==1) return; for (int i = 1; i < cnt; i++) cout << a[i] << "+"; cout << a[cnt] << endl; return; } for (int i = x; i <= sum; i++) { cnt++; a[cnt] = i; dfs(sum-i,i); cnt--; } } int main() { cin >> n; cnt=0; dfs(n,1); return 0; }-
hetao2934713
@ 2023-11-12 17:41:47
谢谢大佬
-
hetao1394742
@ 2024-3-9 14:06:24
xd，加了注释，拿走不谢
#include <iostream> //原作者：hetao8510344 #include <cmath> //注释添加：洋葱头 using namespace std; int n, a[15],cnt; void dfs(int sum,int x) //核心思路：用深度优先搜索找出每一种情况并输出 { if (sum == 0) { if(cnt==1) return; //递归边界 for (int i = 1; i < cnt; i++) cout << a[i] << "+"; //输出 cout << a[cnt] << endl; //换行 return; } for (int i = x; i <= sum; i++) { cnt++; a[cnt] = i; //设定状态 dfs(sum-i,i); cnt--; //消除影响 } } int main() { cin >> n; cnt=0; dfs(n,1); return 0; }
-
-
6
思路
考虑dfs(sum)表示需要对sum进行拆分成若干数的和，使用数组a储存拆分结果，cnt储存数组a的长度。 但又由于要求要字典序顺序输出，所以需要保证每次后面的加数比前面的加数大，所以可以给dfs函数增加一个维度x，记录上一个加数。 $\\$初始时，由于需要拆分的数时n，第一个加数最小是1，所以dfs(n,1); $\\$dfs函数中，当sum为0时说明不需要继续拆分了，直接输出结果，注意最后输出的数不需要加号，需要特殊处理。 $\\$否则，下一个加数i可以从x到sum，将a数组长度++,并且记录为i，继续dfs(sum-i,i);之后记得回溯,cnt--。代码
#include <iostream> #include <cmath> using namespace std; int n, a[15],cnt; void dfs(int sum,int x) { if (sum == 0) { if(cnt==1) return; for (int i = 1; i < cnt; i++) cout << a[i] << "+"; cout << a[cnt] << endl; return; } for (int i = x; i <= sum; i++) { cnt++; a[cnt] = i; dfs(sum-i,i); cnt--; } } int main() { cin >> n; cnt=0; dfs(n,1); return 0; } -
2
hetao4582353 LV 8 @ 2024-2-5 13:47:39
这道题的关键在于记录上一个加数并保证比它大 然后便采用这节课所学知识解题，注意回溯便OK
#include <bits/stdc++.h> using namespace std; int n,sum,x; int a[10]; void dfs(int x,int before) { if (sum == n) { for (int i = 1;i <= n;i++) { if (a[i]) { cout << a[i]; if (a[i+1] == 0) { break; } cout << "+"; } } cout << endl; return; } for (int i = 1;i < n;i++) { if (sum + i <= n && i >= before) { sum += i; a[x] = i; dfs(x+1,i); a[x] = 0; sum -= i; } } } int main() { cin >> n; dfs(1,0); return 0; }//已AC，别忘点赞呃，代码有些头重脚轻，改成这样或许会好一点
#include <bits/stdc++.h> using namespace std; int n,sum,x; int a[10]; void dfs(int x,int before); int main() { cin >> n; dfs(1,0); return 0; } void dfs(int x,int before) { if (sum == n) { for (int i = 1;i <= n;i++) { if (a[i]) { cout << a[i]; if (a[i+1] == 0) { break; } cout << "+"; } } cout << endl; return; } for (int i = 1;i < n;i++) { if (sum + i <= n && i >= before) { sum += i; a[x] = i; dfs(x+1,i); a[x] = 0; sum -= i; } } }大家觉得呢？
-
0
hetao5487227
LV 8
@ 2024-5-26 21:25:53
输入在29以下，不然算不完
-
0
hetao6091164 LV 7 @ 2024-4-26 21:06:40
#include <iostream> #include <cmath> using namespace std; int n, a[15],cnt; void dfs(int sum,int x) { if (sum == 0) { if(cnt==1) return; for (int i = 1; i < cnt; i++) cout << a[i] << "+"; cout << a[cnt] << endl; return; } for (int i = x; i <= sum; i++) { cnt++; a[cnt] = i; dfs(sum-i,i); cnt--; } } int main() { cin >> n; cnt=0; dfs(n,1); return 0; }已AC😄 😄 😄
-
0
hetao1590980 LV 8 @ 2024-2-12 17:54:47
#include <iostream> #include <cmath> using namespace std; int n, a[15],cnt; void dfs(int sum,int x) { if (sum == 0) { if(cnt==1) return; for (int i = 1; i < cnt; i++) cout << a[i] << "+"; cout << a[cnt] << endl; return; } for (int i = x; i <= sum; i++) { cnt++; a[cnt] = i; dfs(sum-i,i); cnt--; } } int main() { cin >> n; cnt=0; dfs(n,1); return 0; }-
hetao3449355 @ 2024-2-23 17:35:18
不是......咱复制别人的总得改改吧......😕
-
hetao8510344
LV 9
@ 2023-9-12 12:16:29
- 1