基础算法--枚举

枚举算法是一种简单而有效的算法,它通过枚举所有可能的情况来解决问题。它通常用于解决问题规模比较小的问题,因为它的时间复杂度很高,随着问题的规模增加,算法的效率会急剧下降。

枚举算法的基本思路是通过循环遍历所有可能的情况,找到最优解或满足条件的解。它的步骤通常包括:

1.选择一个变量作为枚举变量,并确定它的取值范围。

2.在循环过程中遍历所有可能的取值,并执行某种操作。

3.检查每个可能的解是否符合要求,如果符合要求就记录下来。

4.在所有可能的解中,选择最优解或满足特定条件的解。

枚举作为一个基础的算法,除了与模拟算法有着密不可分的关系,还对解决一些线性表的问题有很大帮助。在解决线性表的问题中,枚举分为:线性枚举、二分枚举、三分枚举。在算法中,又可以分为暴力枚举(穷举法)、排列组合枚举、状压DP。这些算法都有其特定的适用场景和优缺点,需要根据具体的情况选择合适的算法。

叽里咕噜一大堆,今天带你认识一下各种词汇,别被它的名字给吓到,也许有些知识你学过但是你并不知道它的官方叫法而已。


一、线性枚举

简介:

线性枚举指的是遍历某一个一维数组(顺序表)的所有元素,找到满足条件的那个元素并且返回,返回的可以是下标,也可以是元素本身。由于是遍历的,穷举了所有情况,所以一定是可以找到解的,除非问题本身无解。一些资料上也称之为暴力算法(Brute Force)

练习:

给出一个数组:int* arr[10]={3,6,2,5,8,9,7,4,1,0};要求找到7所在位置的下标是多少。

int fuc(int* arr,int n,int targ){//arr={......};n=10;targ=7for(int i=0;i<n;i++){if(arr[i]==targ)return i;}return NULL;
}

总结: 

线性模拟就是循环遍历的一种叫法,时间复杂度O(n),认识即可。ok~技能树成功点亮了一叶。

二、二分枚举

简介:

如果在顺序表是有序的情况下,我们可以采取折半的方法去查找,这种方法称为二分枚举。

二分传送门:查找算法--二分查找-CSDN博客

练习:

洛谷2440-木材加工(这道题在上面传送的那个文章中讲过)

木材厂有 𝑛 根原木,现在想把这些木头切割成 𝑘k段长度为 𝑙的小段木头(木头有可能有剩余)。当然,我们希望得到的小段木头越长越好,请求出 𝑙的最大值。木头长度的单位是 cm,原木的长度都是正整数,我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为 11和 21,要求切割成等长的 6 段,很明显能切割出来的小段木头长度最长为 5。

#include<vector>
#include<algorithm>
#include<iostream>using namespace std;
int maxLength(vector<int> v, int k)
{//二分的前提是顺序表有序sort(v.begin(), v.end());int m = v[v.size()-1];int left = 0;int right = m;int mid = (right - left) / 2 + left;while (left < right){if (right-left == 1) {//如果木段差==1,就该考虑返回left还是返回rightint s = 0; for (auto e : v) {s += (e / right);}if (s >= k)return right;//如果总段数大于k说明至少能截成k个right.return left;//没能进入返回}int sum = 0;//段数和for (auto e : v) {//每根原木的长度÷估计的最大段长->可截段数//每根原木的可截段数 求总和sum += (e / mid);}//二分if (sum >= k) {//根据中值求总段数,可以获得比标准数量更多的小木段//那么可以试着大一点,更新左值left = mid;}else if (sum < k) {//根据中值不能获取足够的小木段//那么可以试着小一点,更新右值right = mid-1;}mid = (right - left) / 2 + left;//中值--更新mid}//时间复杂度O(nlogn),此时n为最短元素大小return mid;//结果理论为:left==mid==right
}
int main()
{int N, K; //N原木个数,K目标段数cin >> N >> K;vector<int> v(N);for (int i = 0; i < N; i++)cin >> v[i];//每根原木长度cout << maxLength(v, K) << endl;return 0;
}

总结:

这就是我们的二分法,时间复杂度为O(logn)。是不是又是一个熟悉的知识点。掌握了就在这个知识点的后面打上√吧。

三、三分枚举

简介:

三分枚举是一种用于求解单峰(单谷)函数极值的算法。它的基本原理是利用函数的单峰(单谷)性质,通过迭代的方式逐步缩小搜索范围,最终找到极值点。具体来说:对于形如y=ax²+bx+c的二次函数,其极值点位于x=-b/2a。如果给定一个包含极值点的区间,可以通过三分法逐步缩小区间范围,直到找到极值点。

练习:

牛客练习赛59-C.装备合成

牛牛有x件材料a和y件材料b,用2件材料a和3件材料b可以合成一件装备,用4件材料a和1件材料b也可以合成一件装备。牛牛想要最大化合成的装备的数量,于是牛牛找来了你帮忙。


输入包含t组数据
第一行一个整数t
接下来t行每行两个整数x,y

每组数据输出一行一个整数表示答案。

假设方案一做了m件装备,方案二做了n件装备,我们遍历m来求n,n=min((x-2m)/4, y-3m),三分m,求n+m的最大值

由于三分时返回的m+n是整数,注意下面的情况时check(mid1)==check(mid2)&&check(mid1)<check(R) ,L=mid1+1,而不是R=mid2-1

#include <bits/stdc++.h>
using namespace std;int x, y;
int check(int m){return m+min((x-2*m)/4, y-3*m);
}
int main(){   int T;cin>>T;while(T--){cin>>x>>y;int L=0, R = min(x/2, y/3);int ans = 0;while(L<=R){int mid1 = L+(R-L)/3, mid2 = R-(R-L)/3;int res1 = check(mid1), res2 = check(mid2);ans = max(res1, res2);if(res1<res2||(res1==res2&&res1<check(R))) L = mid1+1;else R = mid2-1;}cout<<ans;}return 0;
}

 总结:

三分枚举算法常用于求解优化问题,特别是在没有明显规律可循的环境中。例如,在处理山峰高度调整问题时,可以通过三分枚举算法来最小化山峰之间的最大高度差。具体应用场景包括但不限于调整山峰高度、优化资源配置等。

三分枚举算法的优点在于其简单易懂,适用于求解单峰(或单谷)函数的极值问题。然而,它的缺点也很明显,即效率较低,特别是在处理大规模数据时,可能会消耗较多的计算资源。此外,三分枚举算法依赖于函数的单峰(或单谷)性质,如果函数不满足这一性质,算法将无法正确工作。


四、暴力枚举

简介:

暴力枚举,顾名思义,就是将问题的所有可能解逐一列举出来,然后一一验证,直到找到正确解。这种方法虽然看似粗暴,但对于规模较小的问题或者没有更优解法的情况下,往往是最直接有效的方法。数组的线性枚举就是暴力枚举的一种。

练习:

X星系的机器人可以自动复制自己。它们用1年的时间可以复制出2个自己,然后就失去复制能力。
每年X星系都会选出1个新出生的机器人发往太空。也就是说,如果X星系原有机器人5个,
1年后总数是:5 + 9 = 14
2年后总数是:5 + 9 + 17 = 31
如果已经探测经过n年后的机器人总数s,你能算出最初有多少机器人吗?


输入:输入一行两个数字n和s,用空格分开,含义如上。n不大于100,s位数不超过50位。
输出:要求输出一行,一个整数,表示最初有机器人多少个。

从有一个开始试,试到n年,看此时的结果是不是输入的总人数。是就输出并退出,不是的话就继续。今年能产生的机器人数量=去年的*2-1。然后把今年产生的加在总count里。判断count和输入的一不一样。

#include <iostream>
using namespace std;#define Long long long
int main() {int n;Long total,count = 0;Long thisYear=0,lastYear=0 ;cin >> n >>total;for (int i = 1; i < total; ++i) {count = thisYear = i;for (int j = 0; j < n; ++j) {lastYear = thisYear;thisYear = lastYear*2-1;count += thisYear;}if (count == total) {cout << i;return 0;} //else continue;}
}

 五、排列组合枚举

简介:

1. 排列枚举:给定 n 个元素,枚举其所有的 r 元素排列可以使用递归或回溯的方法。

2. 组合枚举:同样地,组合的枚举也可以使用递归的方式来实现。

递归传送门:基础算法--递归算法【难点、重点】-CSDN博客

练习:

生成给定数组的所有排列组合:

#include <iostream>  
#include <vector>  
#include <algorithm>  
using namespace std;void permute(vector<int>& nums, int start) {  if (start == nums.size() - 1) {  // 输出当前排列  for (int num : nums) {  cout << num << " ";  }  cout << endl;  } else {  for (int i = start; i < nums.size(); ++i) {  swap(nums[start], nums[i]); // 交换  permute(nums, start + 1);        // 递归  swap(nums[start], nums[i]); // 撤销交换  }  }  
}  void combine(const vector<int>& nums, int r, int start, vector<int>& path) {  if (path.size() == r) {  // 输出当前组合  for (int num : path) {  cout << num << " ";  }  cout << endl;  return;  }  for (int i = start; i < nums.size(); ++i) {  path.push_back(nums[i]); // 添加当前元素  combine(nums, r, i + 1, path); // 递归  path.pop_back(); // 撤销添加  }  
}  int main() {  vector<int> vec = {1, 2, 3};  permute(vec, 0);  vector<int> nums = {1, 2, 3};  int r = 2; // 组合的大小  vector<int> path;  combine(nums, r, 0, path);  return 0;  
}
  • 排列枚举: 这个程序通过交换当前元素和其他元素的位置,然后递归处理下一个位置,最终列出所有可能的排列。
  • 组合枚举: 这个程序通过递归构建组合,每次选择当前元素并继续下一次迭代。通过 path 存储当前组合,达到组合大小后输出结果。

六、状压DP

em,我还没学,不太会,就不讲了。谅解谅解,嘻嘻。


感谢观看!

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

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

相关文章

Rust和Go谁会更胜一筹

在国内&#xff0c;我认为Go语言会成为未来的主流&#xff0c;因为国内程序员号称码农&#xff0c;比较适合搬砖&#xff0c;而Rust对心智要求太高了&#xff0c;不适合搬砖。 就个人经验来看&#xff0c;Go语言简单&#xff0c;下限低&#xff0c;没有什么心智成本&#xff0c…

使用MTVerseXR SDK实现VR串流

1、概述​ MTVerseXR SDK 是摩尔线程GPU加速的虚拟现实&#xff08;VR&#xff09;流媒体平台&#xff0c;专门用于从远程服务器流式传输基于标准OpenXR的应用程序。MTVerseXR可以通过Wi-Fi和USB流式将VR内容从Windows服务器流式传输到XR客户端设备, 使相对性能低的VR客户端可…

【CSS in Depth 2 精译_043】6.5 CSS 中的粘性定位技术 + 本章小结

当前内容所在位置&#xff08;可进入专栏查看其他译好的章节内容&#xff09; 第一章 层叠、优先级与继承&#xff08;已完结&#xff09;第二章 相对单位&#xff08;已完结&#xff09;第三章 文档流与盒模型&#xff08;已完结&#xff09;第四章 Flexbox 布局&#xff08;已…

【2022工业3D异常检测文献】AST: 基于归一化流的双射性产生不对称学生-教师异常检测方法

Asymmetric Student-Teacher Networks for Industrial Anomaly Detection 1、Background 所谓的学生-教师网络&#xff0c;首先&#xff0c;对教师进行训练&#xff0c;以学习语义嵌入的辅助性训练任务&#xff1b;其次&#xff0c;训练学生以匹配教师的输出。主要目的是让学生…

SpringBoot日志打印实践

背景 在项目当中&#xff0c;我们经常需要打印一些日志埋点信息&#xff0c;这些日志埋点信息&#xff0c;在后续软件的运维、稳定性建设中发挥了巨大的作用&#xff1a; 问题追踪&#xff1a;通过埋点日志中的关键信息&#xff0c;帮助定位系统异常原因系统监控&#xff1a;…

移动硬盘传输中断后无法识别:问题解析与数据恢复策略

一、移动硬盘传输中断后的无法识别现象 在日常的数据传输过程中&#xff0c;移动硬盘作为便携式的存储介质&#xff0c;扮演着举足轻重的角色。然而&#xff0c;当传输过程被意外中断&#xff0c;且移动硬盘随后无法被系统识别时&#xff0c;这无疑会给用户带来极大的困扰。你…

Stable Diffusion绘画 | 插件-Deforum:动态视频生成(上篇)

Deforum 与 AnimateDiff 不太一样&#xff0c; AnimateDiff 是生成丝滑变化视频的&#xff0c;而 Deforum 的丝滑程度远远没有 AnimateDiff 好。 它是根据对比前面一帧的画面&#xff0c;然后不断生成新的相似图片&#xff0c;来组合成一个完整的视频。 Deforum 的优点在于可…

Pikachu-Sql Inject-宽字节注入

基本概念 宽字节是相对于ascII这样单字节而言的&#xff1b;像 GB2312、GBK、GB18030、BIG5、Shift_JIS 等这些都是常说的宽字节&#xff0c;实际上只有两字节 GBK 是一种多字符的编码&#xff0c;通常来说&#xff0c;一个 gbk 编码汉字&#xff0c;占用2个字节。一个…

【一文理解】conda install pip install 区别

大部分情况下&#xff0c;conda install & pip install 二者安装的package都可以正常work&#xff0c;但是混装多种package后容易版本冲突&#xff0c;出现各种报错。 目录 检查机制 支持语言 库的位置 环境隔离 编译情况 检查机制 conda有严格的检查机制&#xff0c…

【C++】模拟实现红黑树

&#x1f984;个人主页:修修修也 &#x1f38f;所属专栏:实战项目集 ⚙️操作环境:Visual Studio 2022 目录 一.了解项目功能 二.逐步实现项目功能模块及其逻辑详解 &#x1f4cc;实现RBTreeNode类模板 &#x1f38f;构造RBTreeNode类成员变量 &#x1f38f;实现RBTreeNode类构…

图解C#高级教程(二):事件

在现实生活当中&#xff0c;有一些事情发生时&#xff0c;会连带另一些事情的发生。例如&#xff0c;当某国的总统发生换届时&#xff0c;不同党派会表现出不同的行为。两者构成了“因果”关系&#xff0c;因为发生了A&#xff0c;所以发生了B。在编程语言当中&#xff0c;具有…

Android问题笔记五十:构建错误-AAPT2 aapt2-7.0.2-7396180-windows Daemon

Unity3D特效百例案例项目实战源码Android-Unity实战问题汇总游戏脚本-辅助自动化Android控件全解手册再战Android系列Scratch编程案例软考全系列Unity3D学习专栏蓝桥系列ChatGPT和AIGC &#x1f449;关于作者 专注于Android/Unity和各种游戏开发技巧&#xff0c;以及各种资源分…

Visual Studio 字体与主题推荐

个人推荐&#xff0c;仅供参考&#xff1a; 主题&#xff1a;One Monokai VS Theme 链接&#xff1a;One Monokai VS Theme - Visual Studio Marketplacehttps://marketplace.visualstudio.com/items?itemNameazemoh.onemonokai 效果&#xff1a; 字体&#xff1a;JetBrain…

SpringBoot项目请求不中断动态更新代码

在开发中&#xff0c;有时候不停机动态更新代码热部署是一项至关重要的功能&#xff0c;它可以在请求不中断的情况下下更新代码。这种方式不仅提高了开发效率&#xff0c;还能加速测试和调试过程。本文将详细介绍如何在 Spring Boot 项目在Linux系统中实现热部署&#xff0c;特…

《业务三板斧:定目标、抓过程、拿结果》读书笔记1

这个书是24年新书&#xff0c;来自阿里系的人的作品&#xff0c;还可以。今天先看前沿部分的精彩部分&#xff1a; 我们在服务企业的过程中&#xff0c;发现了一个常见的管理现象&#xff1a;管理者自 己承担了团队里重要的项目&#xff0c;把风险和压力都集中在自己身上。因 此…

报刊订阅系统小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;报刊类型管理&#xff0c;报刊信息管理&#xff0c;报刊订阅管理&#xff0c;订阅发送管理&#xff0c;系统管理 微信端账号功能包括&#xff1a;系统首页&#xff0c;报刊信息&a…

<<迷雾>> 第7章 会变魔术的触发器(1)--连着两个按键开关的逻辑电路 示例电路

info::操作说明 鼠标单击开关切换开合状态 A 能使灯点亮并保持; B 则点亮的灯熄灭. 注: 此处使用的是 按钮开关, 松开鼠标后开关会自己断开, 类似于手机和电脑上的电源按钮 因系统原因, 此类开关与普通开关在外观上并无差别. primary::在线交互操作链接 https://cc.xiaogd.net/…

【Android】获取备案所需的公钥以及签名MD5值

目录 重要前提 获取签名MD5值 获取公钥 重要前提 生成jks文件以及gradle配置应用该文件。具体步骤请参考我这篇文章&#xff1a;【Android】配置Gradle打包apk的环境_generate signed bundle or apk-CSDN博客 你只需要从头看到该文章的配置build.gradle&#xff08;app&…

HTML流光爱心

文章目录 序号目录1HTML满屏跳动的爱心&#xff08;可写字&#xff09;2HTML五彩缤纷的爱心3HTML满屏漂浮爱心4HTML情人节快乐5HTML蓝色爱心射线6HTML跳动的爱心&#xff08;简易版&#xff09;7HTML粒子爱心8HTML蓝色动态爱心9HTML跳动的爱心&#xff08;双心版&#xff09;1…

回归预测 | Matlab基于POA-SVR鹈鹕算法优化支持向量机的数据多输入单输出回归预测

回归预测 | Matlab基于POA-SVR鹈鹕算法优化支持向量机的数据多输入单输出回归预测 目录 回归预测 | Matlab基于POA-SVR鹈鹕算法优化支持向量机的数据多输入单输出回归预测预测效果基本描述程序设计参考资料 预测效果 基本描述 1.Matlab基于POA-SVR鹈鹕算法优化支持向量机的数据…