当前位置: 首页 > 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;//撤回发送

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

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

http://www.lryc.cn/news/374886.html

相关文章:

  • java的深拷贝和浅拷贝
  • AI产品经理,应掌握哪些技术?
  • 同三维T80004EHL-W-4K30 4K HDMI编码器,支持WEBRTC协议
  • Hi3861 OpenHarmony嵌入式应用入门--点灯
  • SaaS案例分享:成功构建销售渠道的实战经验
  • 密钥管理简介
  • 2024中国应急(消防)品牌巡展成都站成功召开!
  • ansible-Role角色批量按照node_export节点,并追加信息到Prometheus文件中
  • 求最小公倍数 、小球走过路程计算 题目
  • 【Android面试八股文】你能说一说为什么IO是耗时操作?
  • 怎样增强 CLike 游戏的社交功能,促进玩家之间的互动和交流?
  • 12_YouOnlyLookOnce(YOLOv3)新一代实时目标检测技术
  • 安装 Nuxt.js 的步骤和注意事项
  • 【perl】环境搭建
  • 【车载音视频AI电脑】全国产海事船载视频监控系统解决方案
  • Centos SFTP搭建
  • 【中学教资科目二】01教育基础
  • 设计模式-享元模式Flyweight(结构型)
  • 【刷题】LeetCode刷题汇总
  • 树莓派pico入坑笔记,快捷键键盘制作
  • 华为鲲鹏应用开发基础:鲲鹏处理器及关键硬件特性介绍(二)
  • Vue.js结合ASP.NET Core构建用户登录与权限验证系统
  • 【html】如何利用id选择器实现主题切换
  • 服务器添加TLS域名证书核子之PKCS编解码
  • 使用 Selenium 自动化获取 CSDN 博客资源列表
  • 智能制造全闪解决方案,八大痛点,一网打尽
  • Python学习从0开始——Kaggle深度学习002
  • 比利时海外媒体宣发,发稿促进媒体通稿发布新形势-大舍传媒
  • 摄影构图:人像摄影和风景摄影的一些建议
  • 安卓实现输入快递单号生成二维码,摄像头扫描快递单号生成的二维码,可以得到快递信息