首页>少儿编程>假设有n个整数,分别是1~n,现在将这n个数进行排列

假设有n个整数,分别是1~n,现在将这n个数进行排列

深度优先搜索的例题

假设有n个整数,分别是1~n,现在将这n个数进行排列,每个整数只能且一定要出现一次,且它们的全排列。

程序

www.noi.cn培训视频《深度优先搜索及其应用》里的例题。dfs(看见缩写总忍不住去猜一下涵义,deep-first-search)是一个递归的函数,其中利用book[11]做了一个标记,当有某个数被使用时,将对应的book数字中的值置为1,以避免数字重复。比如1被使用时,book[1]置1,2被使用时,book[2]置1。这里后面的book[i]=0;有点儿抽象,刚设了1怎么又置0了能,原因是其上方是一个递归函数,实际的执行顺序是等程序出结果后才后被置0。

#include<iostream>
using namespace std;

int a[11],book[11],n,sum=0;

void dfs(int t){
    if(t==n+1){
        sum++;
        for(int i=1;i<=n;i++)cout << a[i];
        cout << endl;
        return;
    }
    for(int i=1;i<=n;i++){
        if(book[i]==0){
            a[t]=i;
            book[i]=1;
            dfs(t+1);
            book[i]=0;
            //cout<<book[1] << " " << book[2] << " " << book[3] <<endl;
        }
    }
}

图解程序逻辑

arrange_n_numbers_with_cpp

简单画了张图帮助理解,程序的上半部分仅供输出结果,主逻辑在for循环内,当n=3的时候,for循环会产生3个分支,即a[1]分别等于1,2,3的时候,这3种情况又各自产生分支,我们来看一下头部的一个分支。

for(int i=1;i<=n;i++){
    if(book[i]==0){
    a[t]=i;
    book[i]=1;
    dfs(t+1);
    book[i]=0;
    //cout<<book[1] << " " << book[2] << " " << book[3] <<endl;
    }
}

dfs(2)的时候,前置book[1]=1,所以,i=1的时候if块内语句不会被执行,也就没有了后续递归,所以到这一步只会产生两路分支,分别是a[2]等于2,或者3的情况。依此类推,book[i]的可用值被逐一打标一直到dfs(4)输出该支线的结果,此时递归回溯,book[3]清零,book[2]清零,执行a[2]=3的分支。

标签: c++

移动端可扫我直达哦~

推荐阅读

cpp 2024-11-03

小鸟数据个人洛谷练习极简题解

P11242碧树:叶子越远,枝干越长,已有的枝干再长一片叶子不影响枝干长度,最终就是枝干的长度加上叶子的总数。枝干总长取决于最远的那片叶子,叶子的总数题目中已经提供。

少儿编程 c++

cpp 2024-10-26

宁波地区选手csp-j复赛一日游

2024年的CSP-J/S复赛依旧没有杭州以外的考点,全省的OIER齐聚杭州,也是盛况空前。我们家是被分到了杭州师范大学的下沙校区,全程约140+公里,高德导航显示2小时能到。考虑考试当天可能拥堵,过早起床也怕孩子考场犯困,所以订了前...

少儿编程 c++

cpp 2024-09-27

2024年 csp-j 以及 csp-s 初赛复赛分数查询接口

链接只是跳转到noi官网,并不是什么第三方的数据库,所以需要预先登陆noi官方网站哦。2024年复赛(2024年10月27日)成绩还没有出,仅尝试放链接备用。复赛接口csp-j复赛查分接口csp-s复赛查分接口2024年初赛(2024...

少儿编程 c++

cpp 2024-09-24

图解动态规划(一)-01背包和变体

在oiwiki学习01背包,虽然完成并通过了题目(洛谷P2871),但总感觉似懂非懂,干脆在画图软件上推演了一下,于是就有了这篇笔记。所谓01背包,一般是给定一个固定容量的容器(背包),并提供固定件数的物品,每件物品有各自的体积(或称...

少儿编程 c++

cpp 2024-09-17

c++中相爱相杀的cin与getline

在洛谷刷题,会遇到各种各种的输入情况,有的时候需要按个输入,而有时则需要按行输入,偶尔也有前一行按个输入,后一行按行输入这样的需求。Windows系统中,换行是由两个字符\r\n组成的。 \r为回车,其ASCII码是13,作用是回到当...

少儿编程 c++

cpp 2024-08-23

c++中的集合----set的使用方法

在C++中,set 是一个容器,用于存储唯一元素,且按特定顺序排序。其具备自动排序,快速查找,去重,插入效率高的特点。以下是定义和使用 set 的基本方法:#include<iostream> #include<se...

少儿编程 c++

cpp 2024-08-23

c++中的map库与它的遍历方式

map与unordered_mapC+提供 map 与unordered_map 两种关联容器,可以将key与value关联起来。 map 与unordered_map 区别:1.底层实现原理map:map内部实现了一个红黑树,该结构...

少儿编程 c++

cpp 2024-08-23

C++利用递归求全排列的笔记

这是一篇洛谷题号P1157题目的题解笔记,该题解的作者是feecle6418,自己写了一大段程序之后看到这么简洁的方式求组合,感觉还是挺挫败的。关键是,看完了题解还看不太懂......#include<bits/stdc++.h...

少儿编程 c++

cpp 2024-07-22

C++位运算的习题解析与若干技巧

洛谷刷题的时候遇到了一些位运算的题目,看得一头雾水,于是临时起意,单独开一篇习题集,用来记录刷题过程中遇到的位运算相关习题。文章准备分为两部分,前半部分为一些常用技巧,后半部分为习题记录,随时补充。位运算的若干技巧位运算的习题集习题部...

少儿编程 c++