河北建设厅网站6,汕头建设网站的公司,怎样做代刷网站长,led灯网站建设案例#x1f63d;PREFACE#x1f381;欢迎各位→点赞#x1f44d; 收藏⭐ 评论#x1f4dd;#x1f4e2;系列专栏#xff1a;算法经典题集#x1f50a;本专栏涉及到的知识点或者题目是算法专栏的补充与应用#x1f4aa;种一棵树最好是十年前其次是现在1.递归1.1 递归实现…PREFACE欢迎各位→点赞 收藏⭐ 评论系列专栏算法经典题集本专栏涉及到的知识点或者题目是算法专栏的补充与应用种一棵树最好是十年前其次是现在1.递归1.1 递归实现指数型枚举下面给出原理分析过程图本质就是数学里面的全排列#include iostream
using namespace std;
const int N 16;
int n;
int st[N];//表示状态0代表考虑1代表选择2代表不选择void dfs(int u)
{if (u n){for (int i 1; i n; i){if (st[i] 1){printf(%d , i);}}puts();return;}else{st[u] 1;//选择dfs(u 1);st[u] 0;//回溯st[u] 2;//不选择dfs(u 1);st[u] 0;//回溯}
}int main()
{cin n;dfs(1);return 0;
}我们也可以优化一下不用三个状态去表示采用bool#include iostream
using namespace std;
const int N 16;
int n;
bool vis[N];void dfs(int u)
{if (u n){for (int i 1; i n; i){if (vis[i]){printf(%d , i);}}puts();return;}else{vis[u] true;dfs(u 1);vis[u] false;dfs(u 1);}
}int main()
{cin n;dfs(1);return 0;
}其实不然递归顾名思义先递下去还要归回来针对这里的代码可能有些人认为不会执行下面的falsedfs(u1)运行之后不是还有个return吗这时候就会返回上一级函数执行下面的false子任务回到递归树上对应的父亲节点接着遍历父亲的其他儿子。他在这颗子树的遍历中父亲节点选过的打上标记子节点才不会选。dfs完相当于把这颗树遍历完了所以这个树又可以选了。1.2 递归实现排列型枚举下面给出图解分析过程#include iostream
using namespace std;
const int N 10;
int path[N];//保存序列
int state[N];//数字是否被使用过
int n;void dfs(int u)
{if(un)//数字填完了输出 {for(int i1;in;i)//输出方案 {coutpath[i] ;}coutendl;return ;}else{for(int i1;in;i){if(!state[i])//如果数字i没有被用过 {path[u]i;//放入空位 state[i]1;//数字被用修改状态 dfs(u1);//填下一位 state[i]0;//回溯取出i }}}
}int main()
{cinn;dfs(1);return 0;
}另外需要注意的是本题的时间复杂度是下面给出简易的证明1.3 递归实现组合型枚举下面给出图解分析过程#include iostream
using namespace std;
const int N 30;
int n, m;
int path[N];void dfs(int u, int s)//u代表当前枚举到哪个位置s代表当前最小可以从哪个数枚举
{if (u n - s m) return;//剪枝就算将剩下的数全部选中也凑不齐m个数所以一定没有答案所以减掉if (u m 1){for (int i 1; i m; i) cout path[i] ;puts();return;}else{for (int i s; i n; i){path[u] i;dfs(u 1, i 1);path[u] 0;//回溯}}
}int main()
{cin n m;dfs(1, 1);return 0;
}1.4 带分数分析过程#include iostream
using namespace std;
const int N 10;
int target;//题目条件给的数
int num[N];//用来保存全排列的结果
bool used[N];//生成全排列的过程中标记是否被使用过
int cnt;//计数最后的输出结果int calc(int l, int r)//计算num数组中一段的数是多少
{int res 0;for (int i l; i r; i){res res * 10 num[i];//小学数学的加法进位}return res;
}void dfs(int u)//生成全排列
{if (u 9){//要把全排列分成三段for (int i 0; i 7; i)//这里的i是位置跟else里面的i不同{for (int j i 1; j 8; j){int a calc(0, i);int b calc(i 1, j);int c calc(j 1, 8);//这里一定要把除法变成乘法因为c里面除法是整除写成除法的形式容易出错if (c * target a * c b){cnt;}}}return;}else{for (int i 1; i 9; i)//这里的i是数字{if (!used[i]){used[i] true;//只要进if里面来就是标记使用num[u] i;dfs(u 1);used[i] false;//回溯还原现场}}}
}int main()
{cin target;dfs(0);cout cnt endl;return 0;
}本题是蓝桥杯某年省赛的原题下面再给出一个直接调用 next_permutation() 函数的做法可以代替手写暴搜来枚举全排列蓝桥杯是可以使用这个函数的#include iostream
#include algorithm
using namespace std;const int N 10;int target;
int num[N];int calc(int l, int r)
{int res 0;for (int i l; i r; i){res res * 10 num[i];}return res;
}int main()
{cin target;for (int i 0; i 9; i) {num[i] i 1;}int res 0;do{for (int i 0; i 9; i) {for (int j i 1; j 9; j) {int a calc(0, i);int b calc(i 1, j);int c calc(j 1, 8);if (a 0 || b 0 || c 0)//特殊情况需要单独讨论一下{continue;}if (a * c b c * target) {res;}}}// 调用函数生成全排列} while (next_permutation(num, num 9));cout res \n;return 0;
}为什么 next_permutation() 函数选用do-while循环结构因为你初始化的时候数组是一种情况直接全排列的话第一种情况直接就少掉了。这也是 next_permutation() 的一个固定方式。补充 next_permutation() 函数另外补充一下 next_permutation() 函数的用法对于next_permutation函数其函数原型为#include algorithm
bool next_permutation(iterator start,iterator end)如果当前序列不存在下一个排列时函数返回false否则返回true例将12345进行全排列#include iostream
#include algorithm
using namespace std;
int main()
{int num[5] { 1,2,3,4,5 };do{cout num[0] num[1] num[2] num[3] num[4] endl;} while (next_permutation(num, num 5));return 0;
}如果将5改为2#include iostream
#include algorithm
using namespace std;
int main()
{int num[5] { 1,2,3,4,5 };do{cout num[0] num[1] num[2] num[3] num[4] endl;} while (next_permutation(num, num 2));return 0;
}由此可以看出next_permutation(num,numn)函数是对数组num中的前n个元素进行全排列同时并改变num数组的值。此外需要强调的是next_permutation在使用前需要对欲排列数组按升序排序否则只能找出该序列之后的全排列数。
