今天写了一下acwing的题目，感觉自己之前对递归没有一个很好的理解，现在写了这几题就有了更好的理解了。

就我而言，递归就是一层一层的调用自己，也就是将层数减少，到最少就不能调用自己了，也就是结束了调用。

 

 

解法一：

　　用二进制枚举每一位。从1到2的n次方，将其转化为二进制，二进制上的第i位是1，就代表着i在序列中，看代码：

 1 #include <bits/stdc++.h>
 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 << n;i++)
10   {
11     bool f = 0;
12     for(int j = 1;j <= n;j++)
13     {
14       if(i & (1 << (j - 1)))
15         cout<<j<<" ",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 <bits/stdc++.h>
 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 <= len;i++)
14             cout<<num[i]<<" ";
15         puts("");
16         return ;
17     }
18     for(int i = start;i <= n;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 <= n;i++)
33     {
34         dfs(1,1,i);
35     }
36     puts("");
37     return 0;
38 }

View Code

 

93. 递归实现组合型枚举

 

 

　　这题是多加了两个条件，一是只取m个数字，二是输出必须是字典序较小的排在前面。

　　这题很明显也是用递归。并且跟上面的很像.其实上面的输出就是按照要求那样输出的。因为我们每次都是从最小的那个数字开始递归的。

　　所以我们只需要讲主函数的循环变成一句语句就可以了。

　　

 1 #include <bits/stdc++.h>
 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 <= m;i++)
14       cout<<num[i]<<" ";
15     puts("");
16     return ;
17   }
18   for(int i = start;i <= n;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 <bits/stdc++.h>
 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 <= n;i++)
14       cout<<num[i]<<" ";
15     puts("");
16     return ;
17   }
18   for(int i = 1;i <= n;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