兖州市做网站,企业网站优化培训,爱网址,做的网站百度搜索不出来给定一个整数 n#xff0c;将数字 1∼n 排成一排#xff0c;将会有很多种排列方法。
现在#xff0c;请你按照字典序将所有的排列方法输出。
输入格式
共一行#xff0c;包含一个整数 n。
输出格式
按字典序输出所有排列方案#xff0c;每个方案占一行。
数据范围
…给定一个整数 n将数字 1∼n 排成一排将会有很多种排列方法。
现在请你按照字典序将所有的排列方法输出。
输入格式
共一行包含一个整数 n。
输出格式
按字典序输出所有排列方案每个方案占一行。
数据范围
1≤n≤9
输入样例
3输出样例
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1 #include iostream
#include cstdio
using namespace std;const int N 10;
int n;
void dfs(int u, int nums[], bool st[])
{if (u n){for (int i 1; i n; i)printf(%d , nums[i]);/*这里用printf和前面输入的时候用scanf是有原因的。因为scanf和printf输入输出比cin和cout运行时间更快会节省大量的运行时间*/puts();}/*这个if语句是这个递归函数里面的终止条件。当un时就依次输出每一位上的数字然后组合在一起得到我们想要的排列结果。*/else{for (int i 1; i n; i)/*不管你要做什么都是在遍历数字的基础上面操作的然后再筛选数字那些所以这个for循环是必要的。*/{//下面的语句我一句一句说。if (!st[i])/*这个判断条件的意思时如果数字没有被使用过的话就可以进入这个if语句。*/{st[i] true;nums[u] i;dfs(u 1, nums, st);/*这里先说上面那三句语句。我们还是老样子按照逻辑来写代码按照自己的思路来走而且我们只需要利用一个结果来推全部这样写和理解起来都要容易些。首先是要没被使用过的数字才能进这个if语句。然后我们观察示例结果1 2 3我们发现这第一个排列的结果1 2 3 他每一位上的数字是没有重复的。那么我们就以这个为思路去写。*//*首先1是没有被用过的因为刚开始初始化的时候1是false状态所以可以进入if语句然后呢我要把这个数字1放在第一位那么这个数字肯定首先会被使用所以首先用st[i] true;这个语句来标记1这个数字已经被使用。然后让第一位上的数字为1所以有nums[u] i;这个语句我第一位上的是数字1以后我想继续接着给下面的位置赋上数字把剩下的2和3给放在剩下的两个位置上。所以直接用递归所以就有dfs(u 1, nums, st);这个语句。用这个语句不断地调用自己这个函数不断地为每个位置上赋数字。*/st[i] false;/*这是回溯的语句是关键语句没这个语句是无法正确的得到结果的*/}}}
}int main()
{int nums[N];/*这个数组表示的是每一位上的数字就是1——n中的某一个数字根据布尔数组标记的每个数的状态来决定是否取数字该取哪些数字。*/bool st[N] {0};/*这个是定义的一个布尔数组用这个布尔数组来标记每一位上数字是否被使用过是用来判断数字的使用状态的一个量。 这里刚开始把布尔数组初始化为0意思是这个时候的数字都没有被使用都是false状态。*/scanf(%d, n);//这里是输入数字n就是题中说的给定整数n。dfs(1, nums, st);/*这里注意哈我是从第一位开始的所以我这里第一位写的是1意思是我从第一位开始执行这个函数。对应着上面的uu表示的是第几位假设n3的话那么u就依次为1 2 3。*/return 0;
}
这代码中蕴藏的知识十分多让我一一来解释与总结。 一、其中的代码语句的深刻理解。
1、st[i] false; 该语句会将当前选择的元素标记为未使用从而恢复现场回溯到之前的状态。这个过程是在dfs函数中进行的当搜索到一个合法的方案时dfs函数会向上回溯并且撤销之前做出的选择重新搜索其他的可能性。这样就可以保证每次选择都基于之前的选择和状态并且不会重复选取相同的元素或进入死循环。
2、dfs(1, nums, st); 在这段代码中dfs(1, nums, st);语句的作用是调用dfs函数开始进行深度优先搜索。 具体地说dfs(1, nums, st);表示从第一位开始搜索排列结果。在dfs函数内部它会遍历数字1到n并检查每个数字是否已经被使用过。如果一个数字没有被使用过那么将其标记为已使用并将其放置在当前位置上即nums[u] i;。然后递归调用dfs函数继续向下一位数字进行搜索即dfs(u 1, nums, st);。
通过递归调用的方式程序会不断地尝试不同的数字组合直到所有位置都被填满即u n。在这种情况下会输出当前得到的一种排列结果。
最后回溯的过程会将之前标记为已使用的数字重新标记为未使用即st[i] false;以便在后续的搜索中可以重新选择这些数字。总体来说dfs(1, nums, st);语句的作用是启动深度优先搜索算法找到所有可能的数字排列结果并输出。 二、代码中的知识点。
1、回溯。
(1)什么是回溯 回溯Backtracking是一种经典的算法解决方法用于在问题的解空间中搜索所有可能的解。回溯算法通过穷举搜索的方式逐步构建候选解并在搜索过程中进行剪枝从而避免无效的搜索。 回溯算法的基本思想是从问题的起始状态开始通过一系列的选择和约束条件逐步构建候选解每次都进行尝试并在遇到无效选择时及时回溯撤销当前选择继续探索其他可能的选择直到找到满足所有条件的解或搜索完整个解空间。 回溯算法通常使用递归来实现通过递归函数的参数传递状态信息并通过递归的深入和回溯的返回来实现搜索的过程。在每一层递归中根据问题的约束条件进行选择、处理和撤销操作直到达到终止条件。 回溯算法适用于求解组合、排列、子集、棋盘类等问题这些问题通常具有多个选择和约束条件。在搜索过程中回溯算法通过剪枝和优化策略可以有效地减少不必要的搜索空间提高算法的效率。 需要注意的是回溯算法的复杂度通常较高因为它会涉及到大量的搜索和尝试。在实际应用中可以通过合理设计剪枝条件、优化算法逻辑等方式来提高回溯算法的效率。 (2)回溯的作用是什么。 回溯的主要作用是在求解问题时通过穷举搜索的方式找到所有可能的解或最优解。
具体来说回溯算法的作用包括 枚举所有可能的解回溯算法通过递归调用和回溯的方式在问题的解空间中穷举所有可能的解。它会尝试每一种可能的选择并继续向下搜索直到找到满足问题条件的解或搜索完整个解空间。 剪枝和优化在搜索过程中回溯算法会根据问题的约束条件进行剪枝和优化。当发现当前路径已经无法满足问题的条件时回溯算法会及时返回上一层撤销之前的选择避免继续无效的搜索。这样可以减少不必要的计算和时间复杂度。 还原状态和回退回溯算法在搜索过程中会记录选择和状态信息使得在回溯时能够还原状态和回退到上一层。这样可以保证每次选择都是基于之前的选择和状态并且不会重复选取相同的元素或进入死循环。 解决组合、排列、子集等问题回溯算法特别适用于求解组合、排列、子集等问题这些问题通常具有多个选择和约束条件。回溯算法可以通过穷举搜索的方式逐步构建候选解并在搜索过程中进行剪枝找到满足问题条件的解。 总而言之回溯的作用是通过穷举搜索的方式寻找所有可能的解或最优解。它通过剪枝和优化策略减少不必要的搜索提高算法的效率。回溯算法广泛应用于组合优化、图搜索、布尔满足问题等领域。 2、布尔数组的使用与初始化。
代码中对应的语句bool st[N] {0}; 在C中可以使用大括号 {} 初始化数组。对于布尔类型的数组0代表false非0值代表true。因此bool st[N] {0};表示将数组st的所有元素初始化为false。 具体地说st是一个布尔类型的数组长度为N。通过{0}进行初始化会将数组的所有元素都设置为false。这样做的目的是确保在开始搜索之前所有数字都被标记为未使用状态。 这个语句的作用是创建一个长度为N的布尔数组st并将所有元素初始化为false以便在后续的搜索中通过修改数组元素的值来标记数字的使用状态。
这就是所有的总结了其中递归与回溯涉及的高级算法我还未去涉及等学习完了以后再回来补充。
