当前位置: 首页 > 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…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...