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++算法——回溯
回溯算法 实现思想 先看一个实例: //暴力枚举的算法 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的深拷贝和浅拷贝
总结: 深拷贝:无论是基本类型还是引用类型都会创建新的实例。 浅拷贝:对于基本类型就是复制其值,对于引用类型则是复制了指向这些数据类型的内存地址。 浅拷贝(Shallow Copy) 浅拷贝是指在创建新对象时&am…...

AI产品经理,应掌握哪些技术?
美国的麻省理工学院(Massachusetts Institute of Technology)专门负责科技成果转化商用的部门研究表明: 每一块钱的科研投入,需要100块钱与之配套的投资(人、财、物),才能把思想转化为产品&…...

同三维T80004EHL-W-4K30 4K HDMI编码器,支持WEBRTC协议
输入:1路HDMI1路3.5音频,1路HDMI环出1路3.5音频解嵌输出 4K30超高清,支持U盘/移动硬盘/TF卡录制,支持WEBRTC协议,超低延时,支持3个点外网访问 1个主流1个副流输出,可定制选配POE供电模块,WEBR…...

Hi3861 OpenHarmony嵌入式应用入门--点灯
本篇实现对gpio的控制,通过控制输出进行gpio的点灯操作。 硬件 我们来操作IO2,控制绿色的灯。 软件 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产品推广的难题,你是否曾感到迷茫,不知如何选择有效的销售渠道?Shopify独立站联盟营销或许能为你提供新的思路。Shopify作为领先的电商解决方案提供商,其独立站功能为众多商家提供了强大的在线销售平台。而联盟营销&#…...

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

2024中国应急(消防)品牌巡展成都站成功召开!
汇聚品牌力量,共同相聚成都。6月14日,由中国安全产业协会指导,中国安全产业协会应急创新分会、应急救援产业网联合主办,四川省消防协会协办的“一切为了安全”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: 批量执行node_ex…...
求最小公倍数 、小球走过路程计算 题目
题目 JAVA11 求最小公倍数分析:代码:大佬代码: JAVA12 小球走过路程计算分析:代码: JAVA11 求最小公倍数 描述 编写一个方法,该方法的返回值是两个不大于100的正整数的最小公倍数。 输入描述:…...
【Android面试八股文】你能说一说为什么IO是耗时操作?
IO(输入/输出)操作之所以是耗时操作,主要是由于以下几个原因: 1. 物理设备的限制 机械动作:传统的硬盘驱动器(HDD)包含旋转的磁盘和移动的磁头,以读取或写入数据。这些机械动作需要时间完成。虽然固态硬盘(SSD)没有机械部件,但它们仍然受到电子信号传输速度的限制。…...
怎样增强 CLike 游戏的社交功能,促进玩家之间的互动和交流?
要增强CLike游戏的社交功能,以促进玩家之间的互动和交流,可以考虑以下几个方面: 添加聊天功能:在游戏中加入实时聊天功能,让玩家可以在游戏内互相交流。可以通过文本聊天或者语音聊天来实现。 社交平台集成࿱…...

12_YouOnlyLookOnce(YOLOv3)新一代实时目标检测技术
1.1 回顾V1和V2 V1:05_YouOnlyLookOnce(YOLOV1)目标检测领域的革命性突破-CSDN博客 V2:07_YouOnlyLookOnce(YOLOv2)Better,Faster,Stronger-CSDN博客 1.2 简介 YOLOv3(You Only Look Once version 3)是…...

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

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

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

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

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

7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...

STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...

【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...