python算法学习:枚举算法

2022-08-0710:23:25数据结构与算法Comments2,615 views字数 1698阅读模式

通过比较经典的例题去讲解一些常用的算法思想,常用的算法思想包括:枚举、递归、分治、贪心、试探、动态迭代和模拟等,本节我们来学习一下枚举算法。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

1. 枚举思想文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

枚举算法我们也称之为穷举算法,这种算法就是在解决问题的时候去使用所有的方式去解决这个问题,会通过推理去考虑事件发生的每一种可能,最后得出结论。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

Python中,我们一般会通过while语句或者if语句去实现枚举算法,具体思路如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

首先分析问题的对象、范围和判断条件,然后逐一列出所有满足条件的解。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

枚举算法的流程图如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

python算法学习:枚举算法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

先判断值是否在范围内,然后判断是否符合条件,最后输出或者取下一个值,直到结束,下面通过例题来学习一下这种算法思想。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

2. 判断水仙花数文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

首先我们来了解一下什么是水仙花数,所谓"水仙花数"是指一个三位数,其各位数字立方和等于该本身。例如:153是一个水仙花数,因为153=1^3+5^3+3^3。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

那么这道题的取值范围即100-999,条件限制为各位数字的立方和等于该本身,那么我们来看一下代码:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

1
2
3
4
5
6
7
8
9
count = 0
for in range(100,1000):  
  count += 1
  = int(i / 100)
  = int(i / 10 % 10)    
  = int((i % 10))    
  if pow(a,3)+pow(b,3)+pow(c,3)==i:        
      print('水仙花数:',i)
print('枚举次数:',count)

输出结果为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

1
2
3
4
5
水仙花数: 153
水仙花数: 370
水仙花数: 371
水仙花数: 407
枚举次数: 900

这道题中我们首先规定了枚举的数值范围为100-999,然后再通过判断数值是否满足条件来输出,最后再输出一下枚举的次数,这就是一个比较简单的枚举问题。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

3.百元买百鸡文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

公鸡每只5元,母鸡每只3元,三只小鸡1元,用100元买100只鸡,问公鸡、母鸡、小鸡各多少只?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

我们首先来分析一下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

如果这一百元只买公鸡能买20只,只买母鸡最多能买33只,买小鸡为300只。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

我们通过枚举的思想来解决这个问题可以通过两层循环,一层判断来完成。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

代码如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

1
2
3
4
5
 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))

输出结果为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

1
2
3
4
公鸡0+母鸡25+小鸡75=100只鸡。
公鸡4+母鸡18+小鸡78=100只鸡。
公鸡8+母鸡11+小鸡81=100只鸡。
公鸡12+母鸡4+小鸡84=100只鸡。

这道题我们首先对鸡存在的可能性进行分析,因为公鸡的价格为五元,所以我们最多也就买20只,母鸡价格为3元,最多也就买33只,然后我们先通过一层循环来遍历母鸡的个数,从1到20,然后再通过一层循环来判断母鸡的个数,此时,一百减去母鸡此时的个数和公鸡的个数和即为小鸡的数量,然后通过一个if语句来判断当前三种鸡的数量相加是否等于一百,如果满足条件则输出。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

4.总结文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26672.html

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

  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/26672.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定