1.1.2用递归实现指数型枚举
-
eg：
-
首先看数据范围：1≤n≤15，推断应该是2^n（指数级别）的复杂度
2^0~2^12: 1 2 4 6 8 16 32 64 128 256 512 1024 2048
2^20大概为10^6(一百万)；2^16为65536；2^15为32768;
2^63大致为10^18
-
复杂度推断过程为15x2^15→15x32768→4.5x10^5
-
1~n个数，每个数有“选"和”不选“两种情况，所以总的方案数为2^n。将每个方案进行输出，每一种情况的数据长度为n，即（2^n）*n。
【注】：#include<bits/stdc++.h>包含了目前c++所包含的所有头文件
-
思维过程：计划开一个长度为n的数组进行记录
首先要判断边界，之后从前往后遍历每一位判断是否有被选。
之后是一个分支的过程，在某个分支做完以后还要进行回溯。
如何将方案记录下来：开辟一个二维数组进行记录。
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
?
const int N=16; /*定义数据范围*/
?
int n;
int st[N];//记录每个位置目前的状态，0为未考虑，1为选，2为不选。
?
void dfs(int u)/*u表示当前在做第几位*/
{
? if(u>n)/*n-1为枚举的最后一位*/
? {
? ? ? for(int i=1;i<=n;i++)//从前往后进行遍历判断。
? ? ? ? ? if(st[i]==1) printf("%d",i);
? ? ? printf("\n");
? ? ? return;
? }
? st[u]=2;
? dfs(u+1);//第一个分支，不选
? st[u]=0;//恢复现场
?
? st[u]=1;
? dfs(u+1);//第二个分支，选
? st[u]=0;
?
}
int main()
{
? scanf("%d",&n);
? dfs(1);/*从0开始进行深度搜索*/
?
? return 0;
}
?
元宵节快乐！！