本章我们进入算法的学习,我们会通过比较经典的例题去讲解一些常用的算法思想,常用的算法思想包括:枚举、递归、分治、贪心、试探、动态迭代和模拟等,本节我们来学习一下枚举算法。

1. 枚举思想

        枚举算法我们也称之为穷举算法,这种算法就是在解决问题的时候去使用所有的方式去解决这个问题,会通过推理去考虑事件发生的每一种可能,最后得出结论。

        在Python中,我们一般会通过while语句或者if语句去实现枚举算法,具体思路如下:

        首先分析问题的对象、范围和判断条件,然后逐一列出所有满足条件的解。

        枚举算法的流程图如下:

         

python算法1

        先判断值是否在范围内,然后判断是否符合条件,最后输出或者取下一个值,直到结束,下面通过例题来学习一下这种算法思想。

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. 总结

        关于枚举算法,它的优点在于枚举法一般是现实生活中问题的“直译”,因此比较直观,易于理解;枚举法建立在考察大量状态、甚至是穷举所有状态的基础上,所以算法的正确性比较容易证明,当然它的缺点也比较明显,用枚举法解题的最大的缺点是运算量比较大,解题效率不高,如果枚举范围太大(一般以不超过两百万次为限),在时间上就难以承受。但枚举算法的思路简单,程序编写和调试方便,比赛时也容易想到,在竞赛中,时间是有限的,我们竞赛的最终目标就是求出问题解,因此,如果题目的规模不是很大,在规定的时间与空间限制内能够求出解,那么我们最好是采用枚举法,而不需太在意是否还有更快的算法,这样可以使你有更多的时间去解答其他难题。


点赞(2)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

Dotcpp在线编译      (登录可减少运行等待时间)