Dotcpp  >  编程教程  >  Python算法  >  Python枚举算法

Python枚举算法

点击打开在线编译器,边学边练

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

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

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



本文固定URL:https://www.dotcpp.com/course/311

下一课:

Python递归算法

Python教程
第一章 Python入门
第二章 Python基础语法
第三章 Python入门语法
第四章 Python核心语法
第五章 Python函数
第六章 Python面向对象编程
第七章 Python模块
第八章 Python异常处理和程序调试
第九章 Python文件及目录操作
第十章 PythonGUI编程
第十一章 Python进程和线程
第十二章 Python数据库管理
第十三章 Python算法
第十四章 Python爬虫
第十五章 Python实战项目
第十六章 后记
Dotcpp在线编译      (登录可减少运行等待时间)