本章我们进入算法的学习,我们会通过比较经典的例题去讲解一些常用的算法思想,常用的算法思想包括:枚举、递归、分治、贪心、试探、动态迭代和模拟等,本节我们来学习一下枚举算法。
1. 枚举思想
枚举算法我们也称之为穷举算法,这种算法就是在解决问题的时候去使用所有的方式去解决这个问题,会通过推理去考虑事件发生的每一种可能,最后得出结论。
在Python中,我们一般会通过while语句或者if语句去实现枚举算法,具体思路如下:
首先分析问题的对象、范围和判断条件,然后逐一列出所有满足条件的解。
枚举算法的流程图如下:
先判断值是否在范围内,然后判断是否符合条件,最后输出或者取下一个值,直到结束,下面通过例题来学习一下这种算法思想。
2. 判断水仙花数
首先我们来了解一下什么是水仙花数,所谓"水仙花数"是指一个三位数,其各位数字立方和等于该本身。例如:153是一个水仙花数,因为153=1^3+5^3+3^3。
那么这道题的取值范围即100-999,条件限制为各位数字的立方和等于该本身,那么我们来看一下代码:
count = 0 for i in range(100,1000): count += 1 a = int(i / 100) b = int(i / 10 % 10) c = int((i % 10)) if pow(a,3)+pow(b,3)+pow(c,3)==i: print('水仙花数:',i) print('枚举次数:',count)
输出结果为:
水仙花数: 153 水仙花数: 370 水仙花数: 371 水仙花数: 407 枚举次数: 900
这道题中我们首先规定了枚举的数值范围为100-999,然后再通过判断数值是否满足条件来输出,最后再输出一下枚举的次数,这就是一个比较简单的枚举问题。
3. 百元买百鸡
公鸡每只5元,母鸡每只3元,三只小鸡1元,用100元买100只鸡,问公鸡、母鸡、小鸡各多少只?
我们首先来分析一下:
如果这一百元只买公鸡能买20只,只买母鸡最多能买33只,买小鸡为300只。
我们通过枚举的思想来解决这个问题可以通过两层循环,一层判断来完成。
代码如下:
for rooster in range(20): for hen in range(33): chicken = 100 - rooster - hen if rooster * 5 + hen * 3 + chicken/3 == 100: print('公鸡%d只+母鸡%d只+小鸡%d只=100只鸡。'%(rooster,hen,chicken))
输出结果为:
公鸡0只+母鸡25只+小鸡75只=100只鸡。 公鸡4只+母鸡18只+小鸡78只=100只鸡。 公鸡8只+母鸡11只+小鸡81只=100只鸡。 公鸡12只+母鸡4只+小鸡84只=100只鸡。
这道题我们首先对鸡存在的可能性进行分析,因为公鸡的价格为五元,所以我们最多也就买20只,母鸡价格为3元,最多也就买33只,然后我们先通过一层循环来遍历母鸡的个数,从1到20,然后再通过一层循环来判断母鸡的个数,此时,一百减去母鸡此时的个数和公鸡的个数和即为小鸡的数量,然后通过一个if语句来判断当前三种鸡的数量相加是否等于一百,如果满足条件则输出。
4. 总结
关于枚举算法,它的优点在于枚举法一般是现实生活中问题的“直译”,因此比较直观,易于理解;枚举法建立在考察大量状态、甚至是穷举所有状态的基础上,所以算法的正确性比较容易证明,当然它的缺点也比较明显,用枚举法解题的最大的缺点是运算量比较大,解题效率不高,如果枚举范围太大(一般以不超过两百万次为限),在时间上就难以承受。但枚举算法的思路简单,程序编写和调试方便,比赛时也容易想到,在竞赛中,时间是有限的,我们竞赛的最终目标就是求出问题解,因此,如果题目的规模不是很大,在规定的时间与空间限制内能够求出解,那么我们最好是采用枚举法,而不需太在意是否还有更快的算法,这样可以使你有更多的时间去解答其他难题。
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程