python枚举算法_Python教程

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

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

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