悉知网站建设,网站管理办法制度,传媒网站如何设计,色彩设计网站问题描述
给定一个整数 n#xff0c;将数字 1∼n 排成一排#xff0c;将会有很多种排列方法。
现在#xff0c;请你按照字典序将所有的排列方法输出。
输入格式 共一行#xff0c;包含一个整数 n。
输出格式 按字典序输出所有排列方案#xff0c;每个方案占一行。
数…问题描述
给定一个整数 n将数字 1∼n 排成一排将会有很多种排列方法。
现在请你按照字典序将所有的排列方法输出。
输入格式 共一行包含一个整数 n。
输出格式 按字典序输出所有排列方案每个方案占一行。
数据范围 1≤n≤7
问题求解
搜素方法DFS(一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止)
搜索过程如下图所示 path数组记录每一位的数值 state数组记录每个数字的使用状态初始为0表示未被使用
搜索过程 从第1层u1) 开始搜索 可以使用的数字1——3循环 若 state[1] 0 即表示没有使用过 把数字1放到第一层的位置上 path[u]i 把state[1]1 表示关闭数字1的使用权 dfs(u1) 进入下一层搜索 此时u2: 数字i从1——3循环 state[1]1 不能用 state[2]0 可用 把数字2放到第2层的位置上 path[u]i 把state[2]1 表示关闭数字2的使用权 dfs(u1) 进入下一层搜索 此时 u 3 数字i循环 i12不可用 state[3] 0可用 把数字3放到第3层 把state[3]1 表示关闭数字3的使用权 dfs(u1) 进入下一层搜索 输出path数组 代码实现
#include iostreamusing namespace std;int path[10];
bool state[10];
int n;void dfs(int u){if(un){for(int i 1; in ; i){coutpath[i] ;}coutendl;return;}for(int i 1; in; i){if(!state[i]){path[u] i;state[i] true;dfs(u1);state[i] false;}}return;
}int main(){cinn;dfs(1);}
