当前位置: 首页 > news >正文

C++算法——回溯

回溯算法

实现思想

先看一个实例:

//暴力枚举的算法
int n = 5;
for (int a = 1; i <= n; i++)
{for (int b = 1; b <= n; b++){for (int c = 1; c <= n; c++){for (int d = 1; d <= n; d++){for (int e = 1; e <= n; e++){//判断 abcde 是否互补相同if (a != b && a != c && a != d && a != e && b != c && b != d && b != e && c != d && c != e && d != e){//输出一下cout << a << " " << b << " " << c << " " << d << " " << e << endl;}}}}}
}

这段代码应该很好理解
就是利用暴力枚举的方法来实现对1-5的全排列
我们可以加上数组的判断,这样就形成了回溯

//暴力枚举的算法
int n = 5;
bool mark[10];
for (int a = 1; i <= n; i++)
{mark[i] = true;for (int b = 1; b <= n; b++) if(!mark[b]){mark[b] = true;for (int c = 1; c <= n; c++) if(!mark[c]){mark[c] = true;for (int d = 1; d <= n; d++) if(!mark[d]){mark[d] = true;for (int e = 1; e <= n; e++) if(!mark[e]){cout << a << " " << b << " " << c << " " << d << " " << e << endl;}mark[d] = false;//回溯来了}mark[c] = false;//回溯来了}mark[b] = false;//回溯来了}mark[a] = false;//回溯来了
}

但是这道题如果这样写思路就太狭小了,我们可以合理利用递归来实现这种回溯

#include <bits/stdc++.h>
using namespace std;
int n, a[10000], mark[10000];
void dfs(int dep)
{if (dep == n + 1){for (int i = 0; i < n; i++){cout << a[i];}cout << "\n";return;}for (int i = 1; i <= n; i++){if (!mark[i]){mark[i] = 1;a[dep] = i;dfs(dep + 1);mark[i] = 0;//回溯来了[Doge不怀好意]}}
}
int main()
{cin >> n;dfs(1);return 0;
}

思路也很好想
dep其实就是枚举的第i层

只不过这种写法可以控制枚举的层数(没学过递归的时间复杂度估算,不知道这样写时间复杂度会不会增加,求大佬点评)

可爱(╹▽╹)的总结

我们可以发现
回溯的思路起始就是 回溯 这两个字本身的意思

所以我们就可以得出结论:
综合的代码:

mark[i] = 1;//我方发送核弹一枚
dfs(dep + 1);//发送中
mark[i] = 0;//撤回发送

大概得意思就是上面的注释(抽象了壹点,但是意思确实是如此)

思路就是反复的尝试,直到尝试出来正确的

相关文章:

C++算法——回溯

回溯算法 实现思想 先看一个实例&#xff1a; //暴力枚举的算法 int n 5; for (int a 1; i < n; i) {for (int b 1; b < n; b){for (int c 1; c < n; c){for (int d 1; d < n; d){for (int e 1; e < n; e){//判断 abcde 是否互补相同if (a ! b &&a…...

java的深拷贝和浅拷贝

总结&#xff1a; 深拷贝&#xff1a;无论是基本类型还是引用类型都会创建新的实例。 浅拷贝&#xff1a;对于基本类型就是复制其值&#xff0c;对于引用类型则是复制了指向这些数据类型的内存地址。 浅拷贝&#xff08;Shallow Copy&#xff09; 浅拷贝是指在创建新对象时&am…...

AI产品经理,应掌握哪些技术?

美国的麻省理工学院&#xff08;Massachusetts Institute of Technology&#xff09;专门负责科技成果转化商用的部门研究表明&#xff1a; 每一块钱的科研投入&#xff0c;需要100块钱与之配套的投资&#xff08;人、财、物&#xff09;&#xff0c;才能把思想转化为产品&…...

同三维T80004EHL-W-4K30 4K HDMI编码器,支持WEBRTC协议

输入&#xff1a;1路HDMI1路3.5音频&#xff0c;1路HDMI环出1路3.5音频解嵌输出 4K30超高清,支持U盘/移动硬盘/TF卡录制&#xff0c;支持WEBRTC协议&#xff0c;超低延时&#xff0c;支持3个点外网访问 1个主流1个副流输出&#xff0c;可定制选配POE供电模块&#xff0c;WEBR…...

Hi3861 OpenHarmony嵌入式应用入门--点灯

本篇实现对gpio的控制&#xff0c;通过控制输出进行gpio的点灯操作。 硬件 我们来操作IO2&#xff0c;控制绿色的灯。 软件 GPIO API API名称 说明 hi_u32 hi_gpio_deinit(hi_void); GPIO模块初始化 hi_u32 hi_io_set_pull(hi_io_name id, hi_io_pull val); 设置某个IO…...

SaaS案例分享:成功构建销售渠道的实战经验

面对SaaS产品推广的难题&#xff0c;你是否曾感到迷茫&#xff0c;不知如何选择有效的销售渠道&#xff1f;Shopify独立站联盟营销或许能为你提供新的思路。Shopify作为领先的电商解决方案提供商&#xff0c;其独立站功能为众多商家提供了强大的在线销售平台。而联盟营销&#…...

密钥管理简介

首先我们要知道什么是密钥管理&#xff1f; 密钥管理是一种涉及生成、存储、使用和更新密钥的过程。 密钥的种类 我们知道&#xff0c;对称密码主要包括分组密码和序列密码。但有时也可以将杂凑函数和消息认证码划分为这一类&#xff0c;将它们的密钥称为对称密钥&#xff1b;…...

2024中国应急(消防)品牌巡展成都站成功召开!

汇聚品牌力量&#xff0c;共同相聚成都。6月14日&#xff0c;由中国安全产业协会指导&#xff0c;中国安全产业协会应急创新分会、应急救援产业网联合主办&#xff0c;四川省消防协会协办的“一切为了安全”2024年中国应急(消防)品牌巡展-成都站成功举办。该巡展旨在展示中国应…...

ansible-Role角色批量按照node_export节点,并追加信息到Prometheus文件中

文章目录 剧本功能 inventory.yaml文件定义deploy.yaml角色定义node_exporter_lock角色定义任务角色main.yamlnode_exporter_tasks.yml角色触发任务notifyextra_tasks.yml角色prometheus_node_config.j2模板文件 执行命令查看变量 剧本功能 功能1&#xff1a; 批量执行node_ex…...

求最小公倍数 、小球走过路程计算 题目

题目 JAVA11 求最小公倍数分析&#xff1a;代码&#xff1a;大佬代码&#xff1a; JAVA12 小球走过路程计算分析&#xff1a;代码&#xff1a; JAVA11 求最小公倍数 描述 编写一个方法&#xff0c;该方法的返回值是两个不大于100的正整数的最小公倍数。 输入描述&#xff1a;…...

【Android面试八股文】你能说一说为什么IO是耗时操作?

IO(输入/输出)操作之所以是耗时操作,主要是由于以下几个原因: 1. 物理设备的限制 机械动作:传统的硬盘驱动器(HDD)包含旋转的磁盘和移动的磁头,以读取或写入数据。这些机械动作需要时间完成。虽然固态硬盘(SSD)没有机械部件,但它们仍然受到电子信号传输速度的限制。…...

怎样增强 CLike 游戏的社交功能,促进玩家之间的互动和交流?

要增强CLike游戏的社交功能&#xff0c;以促进玩家之间的互动和交流&#xff0c;可以考虑以下几个方面&#xff1a; 添加聊天功能&#xff1a;在游戏中加入实时聊天功能&#xff0c;让玩家可以在游戏内互相交流。可以通过文本聊天或者语音聊天来实现。 社交平台集成&#xff1…...

12_YouOnlyLookOnce(YOLOv3)新一代实时目标检测技术

1.1 回顾V1和V2 V1&#xff1a;05_YouOnlyLookOnce(YOLOV1)目标检测领域的革命性突破-CSDN博客 V2&#xff1a;07_YouOnlyLookOnce(YOLOv2)Better&#xff0c;Faster&#xff0c;Stronger-CSDN博客 1.2 简介 YOLOv3&#xff08;You Only Look Once version 3&#xff09;是…...

安装 Nuxt.js 的步骤和注意事项

title: 安装 Nuxt.js 的步骤和注意事项 date: 2024/6/17 updated: 2024/6/17 author: cmdragon excerpt: Nuxt.js在Vue.js基础上提供的服务器端渲染框架优势&#xff0c;包括提高开发效率、代码维护性和应用性能。指南详细说明了从环境准备、Nuxt.js安装配置到进阶部署技巧&…...

【perl】环境搭建

1、Vscode Strawberry Perl 此过程与tcl环境搭建很类似&#xff0c;请参考我的这篇文章&#xff1a; 【vscode】 与 【tclsh】 联合搭建tcl开发环境_tclsh软件-CSDN博客 perl语言的解释器可以选择&#xff0c;strawberry perl。Strawberry Perl for Windows - Releases。 …...

【车载音视频AI电脑】全国产海事船载视频监控系统解决方案

海事船载视频监控系统解决方案针对我国快速发展的内河航运、沿海航运和远洋航运中存在的航行安全和航运监管难题&#xff0c;为船舶运营方、政府监管部门提供一套集视频采集、存储、回放调阅为一体的视频监控系统&#xff0c;对中大型船舶运行中的内部重要部位情况和外部环境进…...

Centos SFTP搭建

SFTP配置、连接及挂载教程_sftp连接-CSDN博客1、确认是否安装yum list installed | grep openssh-server 2、创建用户和组 sudo groupadd tksftpgroup sudo useradd -g tksftpgroup -d /home/www/tk_data -s /sbin/nologin tksftp01 sudo passwd tksftp013. 配置SFTP注意&a…...

【中学教资科目二】01教育基础

01教育基础 前言第一节 教育的产生与发展1.1 教育的起源 第二节 教育学的产生和发展2.1 中国教育学的发展2.2 西方教育学的发展2.3 独立及多样化阶段2.4 马克思教育学2.5 现代教育发展 第三节 教育与社会的发展3.1 教育与文化的关系 第四节 教育与人的发展、4.1 个体身心发展的…...

设计模式-享元模式Flyweight(结构型)

享元模式(Flyweight) 享元模式是一种结构型模式&#xff0c;它主要用于减少创建对象的数量&#xff0c;减少内存占用。通过重用现有对象的方式&#xff0c;如果未找到匹配对象则新建对象。线程池、数据库连接池、常量池等池化的思想就是享元模式的一种应用。 图解 角色 享元工…...

【刷题】LeetCode刷题汇总

目录 一、刷题题号1&#xff1a;两数之和 二、解法总结1. 嵌套循环2. 双指针 一、刷题 记录LeetCode力扣刷题 题号1&#xff1a;两数之和 双循环&#xff08;暴力解法&#xff09;&#xff1a; class Solution {public int[] twoSum(int[] nums, int target) {int[] listne…...

树莓派pico入坑笔记,快捷键键盘制作

使用usb_hid功能制作快捷键小键盘&#xff0c;定义了6个键&#xff0c;分别是 ctrlz ctrlv ctrlc ctrla ctrlw ctrln 对应引脚 board.GP4, board.GP8, board.GP13 board.GP28, board.GP20, board.GP17 需要用到的库&#xff0c;记得复制进单片机存储里面 然后是main主程…...

华为鲲鹏应用开发基础:鲲鹏处理器及关键硬件特性介绍(二)

1. 鲲鹏简介 1.1 鲲鹏处理器简介 鲲鹏处理器是华为自研的基于ARMv8指令集开发的数据中心级处理器 1.2 基于鲲鹏主板的多样化计算产品 1.3 基于鲲鹏920的华为TaiShan(泰山) 200服务器 1.3.1 TaiShan 2280服务器内部视图 1.3.2 TaiShan 2280服务器物理结构 1.3.3 TaiShan 2280服…...

Vue.js结合ASP.NET Core构建用户登录与权限验证系统

1. 环境准备2. 创建项目3. Vue配置步骤一: 安装包步骤二: 配置文件步骤三: 页面文件 4. 后台配置 在本教程中&#xff0c;我将利用Visual Studio 2022的强大集成开发环境&#xff0c;结合Vue.js前端框架和ASP.NET Core后端框架&#xff0c;从头开始创建一个具备用户登录与权限验…...

【html】如何利用id选择器实现主题切换

今天给大家介绍一种方法来实现主题切换的效果 效果图&#xff1a; 源码&#xff1a; <!DOCTYPE html> <html lang"zh"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initia…...

服务器添加TLS域名证书核子之PKCS编解码

PKCS PKCS(Public Key Cryptography Standards)是一系列的标准,用于定义在公钥密码体系中涉及的一些基本结构和算法。PKCS#1 和 PKCS#8 是两个不同的标准,分别定义了不同的公钥私钥编码和封装格式。 PKCS#1 和PKCS#8区别 PKCS#1 PKCS#1 定义了一种用于RSA算法的公钥和私…...

使用 Selenium 自动化获取 CSDN 博客资源列表

使用 Selenium 自动化获取 CSDN 博客资源列表 在这篇博客中,我将向大家展示如何使用 Selenium 自动化工具来滚动并获取 CSDN 博客资源列表的全部数据。这篇文章的目标是通过模拟用户的滚动操作,加载所有的资源列表项,并提取它们的信息。 项目准备 首先,我们需要安装一些…...

智能制造全闪解决方案,八大痛点,一网打尽

当今&#xff0c;全球制造业面临多重大考验&#xff0c;如个性化需求剧增、成本上升、劳动力短缺及激烈竞争。应对这些挑战&#xff0c;智能制造成为转型关键&#xff0c;借助云技术、大数据、AI等前沿科技推动生产智能化&#xff0c;增强企业竞争力。 中国大力扶持智能制造&am…...

Python学习从0开始——Kaggle深度学习002

Python学习从0开始——Kaggle深度学习002 一、单个神经元1.深度学习2.线性单元示例 - 线性单元作为模型多个输入 3.Keras中的线性单元 二、深度神经网络1.层多种类型的层 2.激活函数3.堆叠密集层4.构建Sequential模型 三、随机梯度下降1.介绍2.损失函数3.梯度下降法1.梯度下降法…...

比利时海外媒体宣发,发稿促进媒体通稿发布新形势-大舍传媒

引言 随着全球化的推进&#xff0c;海外媒体的影响力也日益增强。在这一背景下&#xff0c;比利时海外媒体的宣发工作成为了媒体通稿发布的新形势。大舍传媒作为一家专注于宣传推广的公司&#xff0c;一直致力于与比利时博伊克邮报&#xff08;boicpost&#xff09;合作&#…...

摄影构图:人像摄影和风景摄影的一些建议

写在前面 博文内容涉及摄影中人像摄影和风景摄影的简单介绍《高品质摄影全流程解析》 读书笔记整理理解不足小伙伴帮忙指正 &#x1f603; 生活加油 不必太纠结于当下&#xff0c;也不必太忧虑未来&#xff0c;当你经历过一些事情的时候&#xff0c;眼前的风景已经和从前不一样…...

零食网站制作的建设大纲/百度关键词优化公司

一、源码安装首先安装开发工具包yum groupinstall -y "Development tools"安装依赖软件包yum -y install gcc gcc-c zlib-devel bzip2-devel openssl-devel sqlite-devel readline-devel libffi-devel wget上Python 官网 找源码包的下载地址wget https://www.python.…...

淘宝式网站建设/软文推广文案范文

微信h5端 外部浏览器中支付&#xff1a; 后端写一个接口去访问微信的接口&#xff0c;微信会返回一段链接&#xff0c;直接回调给前端&#xff0c;前端处理代码如下 后端返的值 orderString&#xff1a;‘https://wx.tenpay.com/cgi-bin/mmpayweb-bin/checkmweb?prepay_idwx…...

wordpress如何更改页脚背景颜色/百度灰色关键词代做

MariaDB数据库的创建语法,和MySQL数据库的语法是一样的 此文章是为了快速想起语法,不包含授权 MariaDB数据库创建用户 首先要知道一个事情,就是用户是 “用户名主机地址(网段)” 这样才算是一个用户 主机地址授权的范围大致如下: % – 表示:任意主机都可以连接到数据库(这很不…...

深圳网站建设服务便宜/企业推广方式有哪些

regex 元字符^&#xff0c;用于匹配行首&#xff0c;如:^first&#xff0c;匹配以first开头的行&#xff1b;元字符$&#xff0c;用于匹配行尾&#xff0c;如:end$&#xff0c;匹配以end结尾的行&#xff1b;元字符“.”&#xff0c;用于匹配换行符以外的任意字符&#xff1b;\…...

ui网上接单网站/北京网站优化服务

对于文本链接&#xff0c;我有&#xff1a;CSS&#xff1a;a:link {color: #3366a9; text-decoration: none}a:hover {border-bottom: 1px solid; color: black}但是&#xff0c;这也增加了对我不希望联IMGS黑色下划线。如何去除border-bottom使用CSS徘徊时&#xff0c;在联IMG…...

重庆九龙坡区哪里有做网站的/公司网络推广该怎么做

方法一&#xff1a; 我们可以使用提供的ccmclean工具删除SMS 高级客户端。&#xff08;ccmclean下载地址http://technet.microsoft.com/zh-cn/sms/bb676787%28en-us%29.aspx&#xff09;现在为大家介绍一下使用方法。首先看一下perth这台机器上已经是SMS 高级客户端了。接下来…...