枚举算法

枚

举

算

法

甚么是隐式演算法？

  隐式法，又称作波尔兹曼，是依照难题的未知前提，确认标准答案的大体覆盖范围，在此覆盖范围内列出它大部份可能将情形的方式。 

在列出的操作过程中，既无法陈述，又无法重复，通过逐一判断，验证哪些情形满足难题的前提，从而得到难题的标准答案。

固定布局                                                        

隐式演算法的基本思路

（1）确认隐式对象、隐式覆盖范围和验证前提；

（2）借助循环和前提语句，枚举大部份可能将的解，验证是否是难题的解。

姹紫嫣红

春风拂面

固定布局                                                        

练习1

编程找出1000以内大部份质数。

在线题库，368题

固定布局

隐式演算法，思路：

隐式1000以内大部份的数，是质数则输出。

分析：

隐式覆盖范围：for n in range(2,1000)

验证前提：n是否是质数

如何判断n是否是质数？

思路：隐式2~ √n ，如果有一个能整除n，则n不是质数；都无法整除n，那么n是质数

循环嵌套

  一个循环结构里包含另一个循环结构，称作循环嵌套，也称多重循环； 

常用的是二重循环，分别称外循环和内循环。

循环嵌套的具体写法：

一定要注意搞清楚是哪个循环的语句

内循环的语句要空8格

外循环的语句只要空4格

练习1，增加一项：还要输出素数的总个数

参考代码

练习2

水仙花数

在线题库，357题

固定布局                                                        

原思路：隐式大部份的三位数，每个数都拆解开试试看，满足前提，则输出。

第二种思路：用多重循环，分别隐式个位、十位和百位数字，看每个数字的3次幂之和是否等于它们合成的三位数，满足前提则输出。

循环嵌套

注意：

外循环每执行一次，内循环就从初值到终值完整的执行一遍。

难题：上面的循环体被执行了多少次？

n*m次

隐式演算法

要优化，要提高效率

多重循环不是越多越好，要优化，尽可能将减少循环的次数

也就是尽量分析出难题的隐含前提，缩小隐式覆盖范围。

练习3

我国古代数学家张丘建在《算经》一书中提出的数学难题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？

固定布局                                                        

数学方式

设公鸡x只，母鸡y只，小鸡z只

三个未知量，两个方程

说明解不是唯一的，有多组解

隐式演算法

思路：分别隐式公鸡、母鸡和小鸡的数目，然后验证是否满足百钱买百鸡的前提，满足前提则输出

分析：

公鸡覆盖范围：range(0,21)

母鸡覆盖范围：range(0,34)

小鸡覆盖范围：range(0,101)

验证前提：是否满足百钱和百鸡两个前提

提示：要尽可能将减少循环次数

参考代码：

继续优化

1、当公鸡和母鸡数目确认的时候，小鸡的数目只有一种可能将，100-x-y，其他数都是不可能将的，不满足百鸡这个前提。

2、验证前提，也就不用验证百鸡，只验证是否满足百钱就可以了。

参考代码：

隐式演算法要优化，要提高效率

我们计算一下三种思路的循环次数：

直接穷举：   100*100*100=1000000次

减少循环次数：21*34*100=71400次

减少一次循环：21*34=714次

思考一下，练习1，是否还能继续优化，减少一些循环的次数？

•我的优化的思路：大部份偶数都不需要判断，2单独输出即可

这样可以由原来的1000次减少500次。

你还有甚么优化的思路？

课后练习：

在线题库的370、371、372题

任选两个完成