AcWing 92.93，94
标签：判断 不能 bit namespace idt 组合 使用 长度 ima
今天写了一下acwing的题目，感觉自己之前对递归没有一个很好的理解，现在写了这几题就有了更好的理解了。
就我而言，递归就是一层一层的调用自己，也就是将层数减少，到最少就不能调用自己了，也就是结束了调用。
解法一：
用二进制枚举每一位。从1到2的n次方，将其转化为二进制，二进制上的第i位是1，就代表着i在序列中，看代码：
1 #include 2 typedef long long ll;
3 using namespace std;
4 int n;
5
6 int main()
7 {
8 scanf("%d",&n);
9 for(int i = 1;i 1 )
10 {
11 bool f = 0;
12 for(int j = 1;j )
13 {
14 if(i & (1 1)))
15 cout" ",f = 1;
16 }
17 if(f)
18 puts("");
19 }
20 puts("");
21 return 0;
22 }
View Code
第一个循环是枚举1到2的n次方的数字，第二个循环是从第0位开始该位上是不是1，如果是的话，输出这一位。
解法二：
就是使用递归了，我们可以以当前位pos，开始的位置start、总长度len（也就是判断终止条件）作为参数传下去。那么就是在当前我要位数组选择第pos位，我必须要从start开始选，因为这样才可以保证是升序排序，如果当前位是len + 1的话，就说明到了终止条件了。这里加了vis是因为一个数字在数组之中了，就不能在出现了，所以必须标价一下。
1 #include 2 typedef long long ll;
3 using namespace std;
4
5 const int ma = 1e5 + 7;
6 int n,m,num[ma];
7 bool vis[ma];
8
9 void dfs(int pos,int start,int len)
10 {
11 if(pos == len + 1)
12 {
13 for(int i = 1;i )
14 cout" ";
15 puts("");
16 return ;
17 }
18 for(int i = start;i )
19 {
20 if(!vis[i])
21 {
22 num[pos] = i,vis[i] = 1;
23 dfs(pos + 1,i + 1,len);
24 vis[i] = 0;
25 }
26 }
27 return ;
28 }
29 int main()
30 {
31 scanf("%d",&n);
32 for(int i = 1;i )
33 {
34 dfs(1,1,i);
35 }
36 puts("");
37 return 0;
38 }
View Code
93. 递归实现组合型枚举
这题是多加了两个条件，一是只取m个数字，二是输出必须是字典序较小的排在前面。
这题很明显也是用递归。并且跟上面的很像.其实上面的输出就是按照要求那样输出的。因为我们每次都是从最小的那个数字开始递归的。
所以我们只需要讲主函数的循环变成一句语句就可以了。
1 #include 2 typedef long long ll;
3 using namespace std;
4
5 const int ma = 1e5 + 7;
6 int n,m,num[ma];
7 bool vis[ma];
8
9 void dfs(int pos,int start,int len)
10 {
11 if(pos == len + 1)
12 {
13 for(int i = 1;i )
14 cout" ";
15 puts("");
16 return ;
17 }
18 for(int i = start;i )
19 {
20 if(!vis[i])
21 {
22 vis[i] = 1,num[pos] = i;
23 dfs(pos + 1,i + 1,len);
24 vis[i] = 0;
25 }
26 }
27 }
28
29 int main()
30 {
31 scanf("%d%d",&n,&m);
32 dfs(1,1,m);
33 return 0;
34 }
View Code
这一题就更简单了，这就是讲上面的m变成了固定的n了，也就是只有n个数字。
1 #include 2 typedef long long ll;
3 using namespace std;
4
5 const int ma = 1e5 + 7;
6 int n,m,num[ma];
7 bool vis[ma];
8
9 void dfs(int pos,int len)
10 {
11 if(pos == len + 1)
12 {
13 for(int i = 1;i )
14 cout" ";
15 puts("");
16 return ;
17 }
18 for(int i = 1;i )
19 {
20 if(!vis[i])
21 {
22 vis[i] = 1,num[pos] = i;
23 dfs(pos + 1,len);
24 vis[i] = 0;
25 }
26 }
27 }
28 int main()
29 {
30 scanf("%d",&n);
31 dfs(1,n);
32 return 0;
33 }
View Code
AcWing 92.93，94
标签：判断 不能 bit namespace idt 组合 使用 长度 ima
原文地址：https://www.cnblogs.com/d1s2y3/p/14610980.html
评论