集团网站群,图虫网官网入口,免费模板网站推荐,北京工作室网站建设穿越隧道 递归枚举、位运算 方法① 从1到n#xff0c;顺序访问每位数#xff0c;是否选择#xff0c;每位数有两种状态#xff0c;选1或不选0. AC代码如下#xff1a; #include iostream
using namespace std;const int N 100;
// bool st[N];
int n;void dfs(in…穿越隧道 递归枚举、位运算 方法① 从1到n顺序访问每位数是否选择每位数有两种状态选1或不选0. AC代码如下 #include iostream
using namespace std;const int N 100;
// bool st[N];
int n;void dfs(int u, int state){if (u n) {for (int i 0; i n; i) {if (state i 1) { // 将state移到当前第i位判断第i位的数是否被选被选则为1否则为0.cout i 1 ;}}puts();return ;}dfs(u 1, state);dfs(u 1, state | 1 u); // 1.先执行 1 u; 将1左移u位,假如u2移完后的值为100;然后将100和state进行或运算。表明在第u为的值为1选这个数
}int main(){cin n;dfs(0, 0);return 0;
}方法② 递归搜索数的方式 (手动模拟) 从1开始顺序访问每位数是否选择每位数有两种状态选1或不选0. 当从1开始不选1的时候。此时的根节点就为下一个数2以此下去。 AC代码如下 #include iostream
using namespace std;const int N 20;
int n;
bool st[N]; void dfs(int u){if (u n 1) {for (int i 1; i n; i){if(st[i]){cout i ;}}puts();return ;}st[u] true; // 选做当前u的这个分支dfs(u 1);st[u] false; // 不选当前u的这个分支dfs(u 1);
}int main(){cin n;dfs(1);return 0;
}方法③ 稍微复杂版。 AC代码如下 #include iostream
#include cstdio
#include algorithmusing namespace std;
const int N 5e5 10;
int path[N];
bool st[N];
int n;
void dfs(int u, int start, int depth){if (u depth 1) {for (int i 1; i u; i) {cout path[i] ;}puts();return ;}for (int i start; i n; i) { // i 从start开始为了保证升序。if (!st[i]) {st[i] true;path[u] i;dfs(u 1, i, depth);st[i] false;}}
}int main(){cin n;for (int i 0; i n; i) {dfs(1,1,i); // 第一位数树的深度表明树深为1;第二位数表明从1开始选第三位数表明树的实际深度。}return 0;
}
