程序技术好文:算法与数据结构

简介: 程序技术好文:算法与数据结构

算法与数据结构---2、枚举打赏


目录


一、总结一句话总结:1、枚举法的代码结构?2、枚举算法的常用优化?3、枚举法敲代码技巧?二、枚举一、枚举法的基本思想二、枚举法的框架结构三、枚举法的优缺点四、枚举算法的优化 五、枚举法敲代码技巧(注意)三、百钱买百鸡问题及优化1、问题2、分析及代码实现3、优化一:缩小枚举范围4、优化二:减少枚举变量5、优化三:根据题目关系,进一步减少枚举变量


回到顶部一、总结


一句话总结:


枚举法又称穷举法,它是根据题意,枚举所有可能状态,并用问题给定的条件来约束状态,检验哪些是需要的,哪些是不需要的。


1、枚举法的代码结构?


循环+判断语句,枚举几个变量就循环几次


设ai1—状态元素ai的最小值;aik—状态元素ai的最大值(1≤i≤n),即a11≤a1≤a1k,a21≤a2≤a2k, ai1≤ai≤aik,


……,an1≤an≤ank


for(a1=a11;a1<=a1k;a1++)


for(a2=a21;a2<=a2k;a2++)


.....


for(ai=ai1;ai<=aik;ai++)


.....


for(an=an1;an<=ank;an++)


if(状态(a1,...,ai...,an)满足检验条件)


输出问题的解;


2、枚举算法的常用优化?


a、缩小枚举范围


b、减少枚举变量


c、使用其它算法


3、枚举法敲代码技巧?


弄清楚枚举变量、枚举范围、枚举判断条件,敲代码就非常简单,而且不容易出错了


枚举变量:


枚举范围:


枚举判断条件:


1 /


2


3 枚举变量:公鸡


4 枚举范围:公鸡1-14,总计算次数14


5 枚举判断条件:


6 钱数=100:5公鸡+3母鸡+1/3小鸡 = 100


7 小鸡%3==0


8 (100-7x)%4==0


9


10


11 /


12 #include


13 int main()


14 {


15 for (int i = 1; i <= 14; i++)


16 {


17 if ((100 - 7 i) % 4 == 0)


18 {


19 int y = (100 - 7 i) / 4;


20 int z = 100 - i - y;


21 if (5 i + 3 y + z / 3 == 100 && z % 3 == 0)


22 {


23 printf("公鸡 %2d 只,母鸡 %2d 只,小鸡 %2d 只\n", i, y, z);


24 }


25 }


26 }


27


28 return 0;


29 }


回到顶部二、枚举


博客对应课程的视频位置:2、枚举

//代码效果参考: http://www.jhylw.com.cn/551020853.html


一、枚举法的基本思想


枚举法又称穷举法,它是根据题意,枚举所有可能状态,并用问题给定的条件来约束状态,


检验哪些是需要的,哪些是不需要的。


枚举结构:循环+判断语句。


二、枚举法的框架结构


设ai1—状态元素ai的最小值;aik—状态元素ai的最大值(1≤i≤n),即a11≤a1≤a1k,a21≤a2≤a2k, ai1≤ai≤aik,


……,an1≤an≤ank


for(a1=a11;a1<=a1k;a1++)


for(a2=a21;a2<=a2k;a2++)


.....


for(ai=ai1;ai<=aik;ai++)


.....


for(an=an1;an<=ank;an++)


if(状态(a1,...,ai...,an)满足检验条件)


输出问题的解;


三、枚举法的优缺点


用枚举法解题的最大的缺点是运算量比较大,解题效率不高,如果枚举范围太大(一般以不超过两百万次为限),在时间上就难以承受。


但枚举算法的思路简单,程序编写和调试方便,比赛时也容易想到,在比赛中,时间是有限的,我们比赛的最终目标是求出问题解,


因此,如果题目的规模不是很大,在规定的时间与空间限制内能够求出解,那么最好是采用枚举法。


四、枚举算法的优化


a、缩小枚举范围


b、减少枚举变量


c、使用其它算法


五、枚举法敲代码技巧(注意)


弄清楚枚举变量、枚举范围、枚举判断条件,敲代码就非常简单,而且不容易出错了


枚举变量:


枚举范围:


枚举判断条件:


回到顶部三、百钱买百鸡问题及优化


博客对应课程的视频位置:2、枚举


1、问题


百钱买百鸡


公鸡一只五块钱,母鸡一只三块钱,小鸡一块钱三只,


现在要用一百块钱买一百只鸡,每种鸡最少一只,问公鸡、母鸡、小鸡各多少只?


2、分析及代码实现


枚举变量:公鸡、母鸡、小鸡


枚举范围:公鸡、母鸡、小鸡都是1-100次,总计算次数100100100


枚举判断条件:


钱数=100:5公鸡+3母鸡+1/3小鸡 = 100


总鸡数=100:公鸡+母鸡+小鸡 = 100


小鸡%3==0


1 /


2


3 百钱买百鸡


4 公鸡一只五块钱,母鸡一只三块钱,小鸡一块钱三只,


5 现在要用一百块钱买一百只鸡,每种鸡最少一只,问公鸡、母鸡、小鸡各多少只?


6


7


8 枚举变量:公鸡、母鸡、小鸡


9 枚举范围:公鸡、母鸡、小鸡都是1-100次,总计算次数100100100


10 枚举判断条件:


11 钱数=100:5公鸡+3母鸡+1/3小鸡 = 100


12 总鸡数=100:公鸡+母鸡+小鸡 = 100


13 小鸡%3==0


14


15 /


16


17 #include


18 int main()


19 {


20 for (int i = 1; i <= 100; i++)


21 for (int j = 1; j <= 100; j++)


22 for (int k = 1; k <= 100; k++)


23 {


24 if (5 i + 3 j + k / 3 == 100 && k % 3 == 0 && i + j + k == 100)


25 {


26 printf("公鸡 %2d 只,母鸡 %2d 只,小鸡 %2d 只\n", i, j, k);


27 }


28 }


29 return 0;


30 }


3、优化一:缩小枚举范围


百钱百鸡问题优化一:


5公鸡+3母鸡+1/3小鸡 = 100


公鸡+母鸡+小鸡 = 100


缩小枚举范围


枚举变量:公鸡、母鸡、小鸡


枚举范围:公鸡1-18,母鸡1-32 ,小鸡1-98次,总计算次数183298


枚举判断条件:


钱数=100:5公鸡+3母鸡+1/3小鸡 = 100


总鸡数=100:公鸡+母鸡+小鸡 = 100


小鸡%3==0


1 /


2


3 百钱百鸡问题优化一:


4


5 5公鸡+3母鸡+1/3小鸡 = 100


6 公鸡+母鸡+小鸡 = 100


7


8 缩小枚举范围


9


10 枚举变量:公鸡、母鸡、小鸡


11 枚举范围:公鸡1-18,母鸡1-32 ,小鸡1-98次,总计算次数183298


12 枚举判断条件:


13 钱数=100:5公鸡+3母鸡+1/3小鸡 = 100


14 总鸡数=100:公鸡+母鸡+小鸡 = 100


15 小鸡%3==0


16


17


18 /


19


20 #include


21 int main()


22 {


23 for (int i = 1; i <= 18; i++)


24 for (int j = 1; j <= 32; j++)


25 for (int k = 1; k <= 98; k++)


26 {


27 if (5 i + 3 j + k / 3 == 100 && k % 3 == 0 && i + j + k == 100)


28 {


29 printf("公鸡 %2d 只,母鸡 %2d 只,小鸡 %2d 只\n", i, j, k);


30 }


31 }


32 return 0;


33 }


4、优化二:减少枚举变量


1 /


2


3 钱数=100:5公鸡+3母鸡+1/3小鸡 = 100


4 总鸡数=100:公鸡+母鸡+小鸡 = 100


5


6 设公鸡 x 只,母鸡 y 只,小鸡 z 只


7


8 5x+3y+1/3z = 100


9 x+y+z = 100


10


11 枚举了x和y之后,z的值是固定的,z=100-x-y


12 所以这个时候,z就不用枚举了


13


14 枚举变量:公鸡,母鸡


15 枚举范围:公鸡1-18,母鸡1-32,总计算次数 1832


16 枚举判断条件:


17 钱数=100:5公鸡+3母鸡+1/3小鸡 = 100


18 小鸡%3==0


19


20 优化:减少了枚举的变量


21 减少枚举的变量之后,枚举的次数大幅减少


22


23 /


24 #include


25 int main()


26 {


27 for (int i = 1; i <= 18; i++)


28 for (int j = 1; j <= 32; j++)


29 {


30 int z = 100 - i - j;


31 if (5 i + 3 j + z / 3 == 100 && z % 3 == 0)


32 {


33 printf("公鸡 %2d 只,母鸡 %2d 只,小鸡 %2d 只\n", i, j, z);


34 }


35 }


36


37 return 0;


38 }


5、优化三:根据题目关系,进一步减少枚举变量


1 /


2


3 钱数=100:5公鸡+3母鸡+1/3小鸡 = 100


4 总鸡数=100:公鸡+母鸡+小鸡 = 100


5


6 设公鸡 x 只,母鸡 y 只,小鸡 z 只


7


8 5x+3y+1/3z = 100


9 x+y+z = 100


10


11 第一个式子*3


12 15x+9y+z = 300


13 x+y+z = 100


14


15 得:


16 14x+8y=200


17 即


18 7x+4y=100


19 y=(100-7x)/4


20 z=100-x-(100-7x)/4


21


22 根据这个式子,有x之后,我们就可以得到y,从而得到z


23 这里7x小于等于96,x取值为1-14


24


25 枚举变量:公鸡


26 枚举范围:公鸡1-14,总计算次数14


27 枚举判断条件:


28 钱数=100:5公鸡+3母鸡+1/3小鸡 = 100


29 小鸡%3==0


相关文章
|
16天前
|
存储 算法 生物认证
基于Zhang-Suen算法的图像细化处理FPGA实现,包含testbench和matlab验证程序
本项目基于Zhang-Suen算法实现图像细化处理,支持FPGA与MATLAB双平台验证。通过对比,FPGA细化效果与MATLAB一致,可有效减少图像数据量,便于后续识别与矢量化处理。算法适用于字符识别、指纹识别等领域,配套完整仿真代码及操作说明。
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
74 1
|
2月前
|
运维 监控 算法
基于 Java 滑动窗口算法的局域网内部监控软件流量异常检测技术研究
本文探讨了滑动窗口算法在局域网流量监控中的应用,分析其在实时性、资源控制和多维分析等方面的优势,并提出优化策略,结合Java编程实现高效流量异常检测。
64 0
|
3月前
|
监控 算法 安全
基于 C# 基数树算法的网络屏幕监控敏感词检测技术研究
随着数字化办公和网络交互迅猛发展,网络屏幕监控成为信息安全的关键。基数树(Trie Tree)凭借高效的字符串处理能力,在敏感词检测中表现出色。结合C#语言,可构建高时效、高准确率的敏感词识别模块,提升网络安全防护能力。
81 2
|
4月前
|
PyTorch 算法框架/工具 C++
人工智能算法python程序运行环境安装步骤整理
本教程详细介绍Python与AI开发环境的配置步骤,涵盖软件下载、VS2017安装、Anaconda配置、PyCharm设置及组件安装等内容,适用于Windows系统,助你快速搭建开发环境。
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
84 0
|
5月前
|
监控 算法 JavaScript
基于 JavaScript 图算法的局域网网络访问控制模型构建及局域网禁止上网软件的技术实现路径研究
本文探讨局域网网络访问控制软件的技术框架,将其核心功能映射为图论模型,通过节点与边表示终端设备及访问关系。以JavaScript实现DFS算法,模拟访问权限判断,优化动态策略更新与多层级访问控制。结合流量监控数据,提升网络安全响应能力,为企业自主研发提供理论支持,推动智能化演进,助力数字化管理。
118 4
|
11月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
224 59
|
4月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
52 0
栈区的非法访问导致的死循环(x64)

热门文章

最新文章