力扣P1706全排列问题 很好的引入暴力 递归 回溯 dfs

 代码思路是受一个洛谷题解里面大佬的启发。应该算是一个dfs和回溯的入门题目，很好的入门题目了下面我会先给我原题解思路我想可以很快了解这个思路。下面是我自己根据力扣大佬写的。

我会进行详细讲解并配上图辅助理解大家请往下看

#include<iostream>
#include<iomanip>
using namespace std;
int n,k;
int a[100], b[100];
void print(int n)
{for (int i = 1; i <= n; i++) {cout <<setw(5)<< a[i];}cout << endl;return;
}
void dfs(int k) {if (k == n) {print(n);return;}for (int i = 1; i <= n; i++) {if (!b[i]) {b[i] = 1;a[k + 1] = i;dfs(k + 1);b[i] = 0;}}
}
int main()
{cin >> n;dfs(0);return 0;
}

这是原题解的原代码

#include<bits/stdc++.h>
using namespace std;
int n,pd[100],used[100];//pd是判断是否用过这个数
void print()//输出函数
{int i;for(i=1;i<=n;i++)printf("%5d",used[i]);//保留五位常宽cout<<endl;
}
void dfs(int k)//深搜函数，当前是第k格
{int i;if(k==n) //填满了的时候{print();//输出当前解return;}for(i=1;i<=n;i++)//1-n循环填数{if(!pd[i])//如果当前数没有用过{pd[i]=1;//标记一下used[k+1]=i;//把这个数填入数组dfs(k+1);//填下一个pd[i]=0;//回溯}}
}
int main()
{cin>>n;dfs(0);//注意，这里是从第0格开始的！return 0;
}

我一开始卡住的点是这里也是代码最最最核心的地方。我非常迷糊这里面有回溯

pd[i]=0;//回溯

然后又是for循环，之后又是dfs（k+1）很明显这是递归。我不知道程序运行的顺序是什么给我绕懵逼了，昨天晚上想了一晚上。咪咪咪咪咪。

for(i=1;i<=n;i++)//1-n循环填数{if(!pd[i])//如果当前数没有用过{pd[i]=1;//标记一下used[k+1]=i;//把这个数填入数组dfs(k+1);//填下一个pd[i]=0;//回溯}}
}

重点思路总结：递归这个顺序比for循环的优先级高。通过dfs不断增加就是层数增加并且在dfs（k+1）同时进行了标记和used【K+1】计入数组，避免重复和数组填入类似剪枝和遍历，并且到达最大层数时返回并print输入结果之后回溯dfs（）应为刚开始不是加到最大层数吗执行完后返回当初的dfs（2）（这里回溯其实是函数递归调用）继续循环。直到遍历所有。很巧妙，会用就行。

思路来源和思考过程

刚开始我困惑于递归这个顺序和for循环的优先级。

我用gtp作图然后又去北理工acmb站视频看了看。之后就是递归就是递推加回溯但是这个应该是计算机原理导致的。理解的话就是机器就是这样运作的，有什么调用帧啥玩意的。

如果打比方就是你可以想一想这个猴子偷桃问题，原题就是有10天每天吃二分之一+1（真能吃啊）问原来多少桃子。你把递归式子列出来然后计算机就会一个递推（形容一下你能知道我在说什么就行）到第1天吧好像是然后在回溯一直回溯然后算出结果。

其实讲到这里会的早就能听懂了。然后为了更直观大家理解我放几个图大家自行观看哈。

上面这个照片大家主要看图还有上面那几段话我觉得很好嗯说的就很好 

上面这个图看看图就行我截的片段

下面的两个图是gpt辅助理解的流程大家可自行阅读理解

import pandas as pd# Data for each step of dfs for n = 3
data = [{"Step": "dfs(0)", "k": 0, "used": [None, None, None], "pd": [0, 0, 0], "Action": "Start dfs(0)"},{"Step": "dfs(0)", "k": 0, "used": [1, None, None], "pd": [1, 0, 0], "Action": "i=1, place 1, recurse dfs(1)"},{"Step": "dfs(1)", "k": 1, "used": [1, 2, None], "pd": [1, 1, 0], "Action": "i=2, place 2, recurse dfs(2)"},{"Step": "dfs(2)", "k": 2, "used": [1, 2, 3], "pd": [1, 1, 1], "Action": "i=3, place 3, recurse dfs(3)"},{"Step": "dfs(3)", "k": 3, "used": [1, 2, 3], "pd": [1, 1, 1], "Action": "Print {1, 2, 3}, backtrack to dfs(2)"},{"Step": "dfs(2)", "k": 2, "used": [1, 2, None], "pd": [1, 1, 0], "Action": "Unmark i=3, backtrack to dfs(1)"},{"Step": "dfs(1)", "k": 1, "used": [1, None, None], "pd": [1, 0, 0], "Action": "Unmark i=2, try i=3"},{"Step": "dfs(1)", "k": 1, "used": [1, 3, None], "pd": [1, 0, 1], "Action": "i=3, place 3, recurse dfs(2)"},{"Step": "dfs(2)", "k": 2, "used": [1, 3, 2], "pd": [1, 1, 1], "Action": "i=2, place 2, recurse dfs(3)"},{"Step": "dfs(3)", "k": 3, "used": [1, 3, 2], "pd": [1, 1, 1], "Action": "Print {1, 3, 2}, backtrack to dfs(2)"},{"Step": "dfs(2)", "k": 2, "used": [1, 3, None], "pd": [1, 0, 1], "Action": "Unmark i=2, backtrack to dfs(1)"},{"Step": "dfs(1)", "k": 1, "used": [1, None, None], "pd": [1, 0, 0], "Action": "Unmark i=3, backtrack to dfs(0)"},{"Step": "dfs(0)", "k": 0, "used": [None, None, None], "pd": [0, 0, 0], "Action": "Unmark i=1, try i=2"},{"Step": "dfs(0)", "k": 0, "used": [2, None, None], "pd": [0, 1, 0], "Action": "i=2, place 2, recurse dfs(1)"},{"Step": "dfs(1)", "k": 1, "used": [2, 1, None], "pd": [1, 1, 0], "Action": "i=1, place 1, recurse dfs(2)"},{"Step": "dfs(2)", "k": 2, "used": [2, 1, 3], "pd": [1, 1, 1], "Action": "i=3, place 3, recurse dfs(3)"},{"Step": "dfs(3)", "k": 3, "used": [2, 1, 3], "pd": [1, 1, 1], "Action": "Print {2, 1, 3}, backtrack to dfs(2)"},{"Step": "dfs(2)", "k": 2, "used": [2, 1, None], "pd": [1, 1, 0], "Action": "Unmark i=3, backtrack to dfs(1)"},{"Step": "dfs(1)", "k": 1, "used": [2, None, None], "pd": [0, 1, 0], "Action": "Unmark i=1, try i=3"},{"Step": "dfs(1)", "k": 1, "used": [2, 3, None], "pd": [0, 1, 1], "Action": "i=3, place 3, recurse dfs(2)"},{"Step": "dfs(2)", "k": 2, "used": [2, 3, 1], "pd": [1, 1, 1], "Action": "i=1, place 1, recurse dfs(3)"},{"Step": "dfs(3)", "k": 3, "used": [2, 3, 1], "pd": [1, 1, 1], "Action": "Print {2, 3, 1}, backtrack to dfs(2)"},{"Step": "dfs(2)", "k": 2, "used": [2, 3, None], "pd": [0, 1, 1], "Action": "Unmark i=1, backtrack to dfs(1)"},{"Step": "dfs(1)", "k": 1, "used": [2, None, None], "pd": [0, 1, 0], "Action": "Unmark i=3, backtrack to dfs(0)"},{"Step": "dfs(0)", "k": 0, "used": [None, None, None], "pd": [0, 0, 0], "Action": "Unmark i=2, try i=3"},{"Step": "dfs(0)", "k": 0, "used": [3, None, None], "pd": [0, 0, 1], "Action": "i=3, place 3, recurse dfs(1)"},{"Step": "dfs(1)", "k": 1, "used": [3, 1, None], "pd": [1, 0, 1], "Action": "i=1, place 1, recurse dfs(2)"},{"Step": "dfs(2)", "k": 2, "used": [3, 1, 2], "pd": [1, 1, 1], "Action": "i=2, place 2, recurse dfs(3)"},{"Step": "dfs(3)", "k": 3, "used": [3, 1, 2], "pd": [1, 1, 1], "Action": "Print {3, 1, 2}, backtrack to dfs(2)"},{"Step": "dfs(2)", "k": 2, "used": [3, 1, None], "pd": [1, 0, 1], "Action": "Unmark i=2, backtrack to dfs(1)"},{"Step": "dfs(1)", "k": 1, "used": [3, None, None], "pd": [0, 0, 1], "Action": "Unmark i=1, try i=2"},{"Step": "dfs(1)", "k": 1, "used": [3, 2, None], "pd": [0, 1, 1], "Action": "i=2, place 2, recurse dfs(2)"},{"Step": "dfs(2)", "k": 2

感谢观看谢谢谢谢么么么么~

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/431974.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【机器学习】Flux.jl 生态

【机器学习】Flux.jl 生态

官方API https://fluxml.ai/Flux.jl/stable/ecosystem/ 官网给出了 Flux’s model-zoo&#xff0c; 是一个庞大的案例库&#xff0c; 可以提供直观的参考&#xff0c; 并且还列举了基于 Flux.jl 开发的第三方库。 机器视觉 ObjectDetector.jl YOLO 抓取的“预备跑” 图像Met…
阅读更多...
使用vite+react+ts+Ant Design开发后台管理项目（一）

使用vite+react+ts+Ant Design开发后台管理项目（一）

前言 本文将引导开发者从零基础开始&#xff0c;运用vite、react、react-router、react-redux、Ant Design、less、tailwindcss、axios等前沿技术栈&#xff0c;构建一个高效、响应式的后台管理系统。通过详细的步骤和实践指导&#xff0c;文章旨在为开发者揭示如何利用这些技…
阅读更多...
SpringCloud Alibaba之Seata处理分布式事务

SpringCloud Alibaba之Seata处理分布式事务

&#xff08;学习笔记&#xff0c;必用必考&#xff09; 问题&#xff1a;Transactional 的9种失效场景&#xff1f; 1、介绍 1.1、简介 官网地址&#xff1a;Apache Seata 源码地址&#xff1a;Releases apache/incubator-seata GitHub Seata是一款开源的分布式事务解决…
阅读更多...
Thinkphp5x远程命令执行 靶场攻略

Thinkphp5x远程命令执行 靶场攻略

环境配置 靶场&#xff1a;vulhub/thinkphp/5-rce docker-compose up -d #启动环境 漏洞复现 1.访问靶场&#xff1a;http://172.16.1.198:8080/ 2.远程命令执⾏ POC&#xff1a; ?sindex/think\app/invokefunction&functioncall_user_func_array&vars[0]system…
阅读更多...
【VUE_ruoyi-vue】基于ruoyi-vue框架实现简单的系统通用文件模块

【VUE_ruoyi-vue】基于ruoyi-vue框架实现简单的系统通用文件模块

基于ruoyi-vue框架&#xff0c;新增一个简单的系统通用文件模块&#xff0c;服务与各个模块涉及到文件上传信息的记录和相关展示 运行sql,创建数据库表 DROP TABLE IF EXISTS sys_file_info; CREATE TABLE sys_file_info (id int(11) NOT NULL AUTO_INCREMENT COMMENT id,lin…
阅读更多...
在虚幻引擎中实时显示帧率

在虚幻引擎中实时显示帧率

引擎自带了显示帧率的功能 但是只能在编辑器中显示 , 在游戏发布后就没有了 , 所以我们要自己做一个 创建一个控件蓝图 创建画布和文本 , 修改文本 文本绑定函数 , 点击创建绑定 添加一个名为 FPS 的变量 格式化文本 用大括号把变量包起来 {FPS Int} FPS 然后转到事件图表…
阅读更多...
机器学习算法与Python实战 | 三万字详解！GPT-5：你需要知道的一切（下）建议收藏！

机器学习算法与Python实战 | 三万字详解！GPT-5：你需要知道的一切（下）建议收藏！

本文来源公众号“机器学习算法与Python实战”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;三万字详解&#xff01;GPT-5&#xff1a;你需要知道的一切 作者&#xff1a;Alberto Romero &#xff08;青稞AI整理&#xff09; 原…
阅读更多...
Go语言基础学习01-Liunx下Go开发环境配置；源码组织方式；go build/install/get详解

Go语言基础学习01-Liunx下Go开发环境配置；源码组织方式；go build/install/get详解

目录 Linux环境下配置安装VScode并配置Go语言开发环境Go语言源码的组织方式Go语言源码安装后的结果Go程序构建和安装的过程go build扩展go get 命令详解 之前学习过Go语言&#xff0c;学习的时候没有记录笔记&#xff0c;最近找了个极客时间的Go语言36讲&#xff0c;打算时间学…
阅读更多...
第 1 章：Vue 核心

第 1 章：Vue 核心

1. Vue 简介 1.1. 官网 英文官网: https://vuejs.org/中文官网: https://cn.vuejs.org/&#xff1a;中文官网里面【教程】和【API】是比较重要的。用到api就去查询&#xff0c;实践当中记忆更牢靠。 风格指南&#xff1a;官方推荐写的一个代码风格cookbook&#xff1a;编写v…
阅读更多...
QT窗口无法激活弹出问题排查记录

QT窗口无法激活弹出问题排查记录

问题背景 问题环境 操作系统: 银河麒麟V10SP1qt版本 : 5.12.12 碰见了一个问题应用最小化,然后激活程序窗口无法弹出 这里描述一下代码的逻辑,使用QLocalServer实现一个单例进程,具体的功能就是在已存在一个程序A进程时,再启动这个程序A,新的程序A进程会被杀死,然后激活已存…
阅读更多...
视频汇聚EasyCVR视频监控平台调取接口提示“认证过期”是什么原因？

视频汇聚EasyCVR视频监控平台调取接口提示“认证过期”是什么原因？

视频汇聚EasyCVR视频监控平台&#xff0c;作为一款智能视频监控综合管理平台&#xff0c;凭借其强大的视频融合汇聚能力和灵活的视频能力&#xff0c;在各行各业的应用中发挥着越来越重要的作用。EasyCVR平台具备强大的拓展性和灵活性&#xff0c;支持多种视频流的外部分发&…
阅读更多...
Kolmogorov-Arnold——代替 MLP以提高模型的代表性和性能

Kolmogorov-Arnold——代替 MLP以提高模型的代表性和性能

前言 论文地址&#xff1a;https://arxiv.org/abs/2409.10594 源码地址&#xff1a;https://github.com/Adamdad/kat.git 传统的变压器模型使用多层感知器&#xff08;MLP&#xff09;来混合通道间的信息&#xff0c;而本文则使用了科尔莫哥罗德网络&#xff08;KAN&#xff0…
阅读更多...
golang操作mysql利器-gorm

golang操作mysql利器-gorm

1、傻瓜示例 GORM通过将数据库表中的数据映射到面向对象的模型中&#xff0c;简化了数据库操作&#xff0c;使得开发者可以很方便的使用代码来操作数据库&#xff0c;而无需编写SQL语句。 目前有个mysql表&#xff1a;miniprogram_orders&#xff0c;其存储了所有用户对应的订…
阅读更多...
Go容器化微服务系统实战

Go容器化微服务系统实战

1-1 本课的go微服务有什么不同&#xff1f; 聚焦于容器化可观测的购物微服务系统实战&#xff0c;通过介绍Go语言的应用趋势、容器化优势及微服务适用性&#xff0c;旨在解决学习微服务过程中遇到的难点。课程内容涵盖微服务整体架构、技术工具框架及容器平台等关键技术&#…
阅读更多...
GPT-4o在matlab编程中性能较好，与智谱清言相比

GPT-4o在matlab编程中性能较好，与智谱清言相比

边标签由矩阵给出 s [1 2 3 3 3 3 4 5 6 7 8 9 9 9 10]; t [7 6 1 5 6 8 2 4 4 3 7 1 6 8 2]; G graph(s,t); plot(G) ------------------- GPT-4o给出的代码可用&#xff0c; clc;clear; % 定义边的起点和终点 s [1 2 3 3 3 3 4 5 6 7 8 9 9 9 10]; t [7 6 1 5 6 8 2 …
阅读更多...
百度amis框架经验分享

百度amis框架经验分享

百度amis框架经验分享 官方文档 amis - 低代码前端框架 这篇文章讲了amis的设计 为什么说百度AMIS框架是一个优秀的设计_百度前端框架-CSDN博客 学习方法&#xff1a; 最好的学习方法就是GPT官方文档 不要去很大力气通读官方文档&#xff0c;大概浏览一遍就行&#xff0c; 以你…
阅读更多...
JS面试真题 part6

JS面试真题 part6

JS面试真题 part6 26、如何判断一个元素是否在可视区域中27、什么是单点登录&#xff1f;如何实现28、 如何实现上拉加载&#xff0c;下拉刷新29、说说你对正则表达式的理解&#xff1f;应用场景&#xff1f;30、说说你对函数式编程的理解&#xff1f;优缺点 26、如何判断一个元…
阅读更多...
MySQL 主从复制部署与优化

MySQL 主从复制部署与优化

文章目录 前言 在现代数据库管理中&#xff0c;MySQL 主从复制是一种关键技术&#xff0c;用于提高数据的可用性和性能。随着 Docker 容器技术的普及&#xff0c;利用 Docker 搭建 MySQL 主从复制环境已成为一种趋势&#xff0c;它提供了一种简便、高效且可扩展的解决方案。本…
阅读更多...
某建筑市场爬虫数据采集逆向分析

某建筑市场爬虫数据采集逆向分析

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言 目标网站 aHR0cHM6Ly9qenNjLm1vaHVyZC5nb3YuY24vZGF0YS9jb21wYW55P2NvbXBsZXhuYW1lPSVFNiVCMCVCNA 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面…
阅读更多...
应用层 I（C/S模型、P2P模型、域名系统DNS）【★★】

应用层 I（C/S模型、P2P模型、域名系统DNS）【★★】

&#xff08;★★&#xff09;代表非常重要的知识点&#xff0c;&#xff08;★&#xff09;代表重要的知识点。 一、网络应用模型 在网络边缘的端系统之间的通信方式通常可划分为两大类&#xff1a;客户 - 服务器方式&#xff08;C/S 方式 [Client/Server] &#xff09;和对等…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023