• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

整数划分,并按字典序(递减)输出

开发技术 开发技术 5天前 4次浏览

1、  一个整数n(n <=30)可以有多种分划,分划的整数之和为n,在不区分分划出各整数的次序时,字典序递减输出n 的各详细分划方案和分划总数。

例如n = 6,程序输出为:

6

5  1

4  2

4  1  1

3  3

3  2  1

3  1  1  1

2  2  2

2  2  1  1

2  1  1  1  1

1  1  1  1  1  1

total = 11

似乎只能利用DFS,dp也可以求出total,但是按照字典序输出似乎有些难办。没想到其他解决方案。

利用DFS,直接从n到1循环,当sum小于n时,继续从小于当前的i往后扩展,直到等于n时,输出结果。

整数划分,并按字典序(递减)输出整数划分,并按字典序(递减)输出

 1 #include <iostream>
 2 #include <deque>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int sum = 0, nn = 0, ans = 0;
 7 deque<int> dq;    // 便于删除插入遍历
 8 
 9 void dfs(int n) {    // 深度优先搜索,从 nn -> 1
10     for (int i = n; i >= 1; i--) {    // 从nn往下遍历
11         dq.push_back(i);
12         sum += i;    
13         if (sum > nn) {        // 剪枝
14             sum -= i;
15             dq.pop_back();
16         }
17         else if (sum == nn) {    // 输出
18             deque<int>::iterator it;
19             for (it = dq.begin(); it != dq.end(); it++)
20                 if (it == dq.begin())
21                     cout << *it;
22                 else
23                     cout << " + " << *it;
24             cout << endl;
25             sum -= i;
26             ans++;
27             dq.pop_back();
28         } else {    // 深度搜索
29             dfs(i);
30             sum -= i;
31             dq.pop_back();
32         }
33     }
34 }
35 
36 int main() {
37     cout << "please input nn : ";
38     cin >> nn;
39     dfs(nn);
40     cout << "total = " << ans << endl;
41     return 0;
42 }

View Code

整数划分,并按字典序(递减)输出

2021-04-30


程序员灯塔
转载请注明原文链接:整数划分,并按字典序(递减)输出
喜欢 (0)