函数难题:排列

2023-12-17 04:54:39

给定一个整数?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语句是这个递归函数里面的终止条件。当u>n时,就依次输出每一位上的数字,
    然后组合在一起,得到我们想要的排列结果。
    */
    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,意思是我从第一位开始执行这个函数。对应着上面
    的u,u表示的是第几位,假设n=3的话,那么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)回溯的作用是什么。

? 回溯的主要作用是在求解问题时,通过穷举搜索的方式找到所有可能的解或最优解。

具体来说,回溯算法的作用包括:

  1. 枚举所有可能的解:回溯算法通过递归调用和回溯的方式,在问题的解空间中穷举所有可能的解。它会尝试每一种可能的选择,并继续向下搜索,直到找到满足问题条件的解或搜索完整个解空间。

  2. 剪枝和优化:在搜索过程中,回溯算法会根据问题的约束条件进行剪枝和优化。当发现当前路径已经无法满足问题的条件时,回溯算法会及时返回上一层,撤销之前的选择,避免继续无效的搜索。这样可以减少不必要的计算和时间复杂度。

  3. 还原状态和回退:回溯算法在搜索过程中会记录选择和状态信息,使得在回溯时能够还原状态和回退到上一层。这样可以保证每次选择都是基于之前的选择和状态,并且不会重复选取相同的元素或进入死循环。

  4. 解决组合、排列、子集等问题:回溯算法特别适用于求解组合、排列、子集等问题,这些问题通常具有多个选择和约束条件。回溯算法可以通过穷举搜索的方式,逐步构建候选解,并在搜索过程中进行剪枝,找到满足问题条件的解。

? 总而言之,回溯的作用是通过穷举搜索的方式,寻找所有可能的解或最优解。它通过剪枝和优化策略,减少不必要的搜索,提高算法的效率。回溯算法广泛应用于组合优化、图搜索、布尔满足问题等领域。

2、布尔数组的使用与初始化。

代码中对应的语句:bool st[N] = {0};

? 在C++中,可以使用大括号 {} 初始化数组。对于布尔类型的数组,0代表false,非0值代表true。因此,bool st[N] = {0};表示将数组st的所有元素初始化为false

? 具体地说,st是一个布尔类型的数组,长度为N。通过{0}进行初始化,会将数组的所有元素都设置为false这样做的目的是确保在开始搜索之前,所有数字都被标记为未使用状态。

? 这个语句的作用是创建一个长度为N的布尔数组st,并将所有元素初始化为false,以便在后续的搜索中通过修改数组元素的值来标记数字的使用状态。

这就是所有的总结了,其中递归与回溯涉及的高级算法我还未去涉及,等学习完了以后再回来补充。

文章来源:https://blog.csdn.net/admin_zbn/article/details/135039986
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。