搜索
简帛阁>技术文章>递归实现排列型枚举 AcWing 94.题解

递归实现排列型枚举 AcWing 94.题解

 题目:

把 1∼n这 n个整数排成一行后随机打乱顺序,输出所有可能的次序。

输入格式

一个整数 n。

输出格式

按照从小到大的顺序输出所有方案,每行 1 个。

首先,同一行相邻两个数用一个空格隔开。

其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。

数据范围:

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;
int st[N]; //挖坑,存储数据的坑
int zt[N]; //ture代表这个数已经放了,false代表还没放进去

void dfs(int u)
{
    while(u > n) // 到了边界,输出
    {
        for(int i = 1; i <= n; i++) 
        printf("%d ",st[i]);
        puts("");
        return;
    }
    for (int i = 1; i <= n; i ++ ) // 依次枚举判断是否已经放了这个数
    {
        if(!zt[i]) // 如果为零(false)即没放进去过
        {
            st[u] = i; // 就把这个数存进坑位
            zt[i] = 1; // 更改这个数的状态
            dfs(u + 1); // 然后进行下一个坑位的填补
            zt[i] = 0;  //回溯时归零
        }
    }
}

int main()
{
    cin >> n;
    dfs(1);
    return 0;
}

如有问题,请在评论区留言———— 

如果对你有帮助,请点个赞吧! 

题目:把1∼n这n个整数排成一行后随机打乱顺序,输出所有可能的次序。输入格式一个整数n。输出格式按照从小到大的顺序输出所有方案,每行1个。首先,同一行相邻两个数用一个空格隔开。其次,对于两个不同的行,
AcWing94递归实现排列枚举题目描述把1∼n1∼n1∼n这nnn个整数排成一行后随机打乱顺序,输出所有可能的次序。输入格式一个整数nnn。输出格式按照从小到大的顺序输出所有方案,每行111个。
AcWing94递归实现排列枚举写在前面:AcWing是由北大一神级人物——“大雪菜”创办的算法交流社区,里面除了正常oj网站的功能之外,还提供单人训练、双人匹配、云端操作系统等模式,除此之外不定期
递归实现排列枚举题目把1~n这n个整数排成一行后随机打乱顺序,输出所有可能的次序。输入格式一个整数n。输出格式按照从小到大的顺序输出所有方案,每行1个。首先,同一行相邻两个数用一个空格隔开。其次,
题目:从1∼n这n个整数中随机选出m个,输出所有可能的选择方案。输入格式:两个整数n,m,在同一行用空格隔开。输出格式:按照从小到大的顺序输出所有方案,每行1个。首先,同一行内的数升序排列,相邻两个数
题目:从1∼n这nn个整数中随机选取任意多个,输出所有可能的选择方案。输入格式输入一个整数nn。输出格式每行输出一种方案。同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。对于没有选任何数的方案
题目链接题目描述从1∼n这n个整数中随机选出m个,输出所有可能的选择方案。输入格式两个整数n,m,在同一行用空格隔开。输出格式按照从小到大的顺序输出所有方案,每行1个。首先,同一行内的数升序排列,相邻
AcWing92递归实现指数枚举题目描述从1∼n1∼n1∼n这nnn个整数中随机选取任意多个,输出所有可能的选择方案。输入格式输入一个整数nnn。输出格式每行输出一种方案。同一行内的数必须升序排列
AcWing93递归实现组合枚举题目描述从1∼n1∼n1∼n这nnn个整数中随机选出mmm个,输出所有可能的选择方案。输入格式两个整数n,mn,mn,m,在同一行用空格隔开。输出格式按照从小到大的
这个系列是蓝桥杯的训练,为了蓝桥杯,同时也是日常的算法训练。第一题是递归,有点类似递归的全排列的做法,复习基本的递归模板。ProblemimportjavaioBufferedReader;impor