资源简介

(共17张PPT)
枚举算法
寻找开门的钥匙
一把钥匙开一把锁
枚举算法的生活实例
有限个解
变量
判断条件
结果
枚举算法的生活实例
《孙子算经》
“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”
一个数除以3余2，除以5余3，除以7余2，求这个数。
i%3==2 and i%5==3 and i%7==2
三个条件必须同时满足
= 判断 == 等于
分析问题
依次输出符合单个条件的前10个解。
A
B
满足除以3余2的解：2，5，8，11，14，17，20，23，26，29
C
满足除以5余3的解：3，8，13，18，23，28，33，38，43，48
E
同时满足三个条件的值：23
列出符合的解
D
满足除以7余2的解：2，9，16，23，30，37，44，51，58，65
range( )函数
格式：range([start,]stop[,step])
功能：创建一个整数列表。
参数：起始值，终值，步长。
注意：终值不包括。
任务一：找出1-300之内符合条件的数
在1-300之内循环
同时满足
枚举算法的思想和步骤
逐一列举
（循环结构）
逐一判断
（分支结构）
易于理解
容易证明
既不遗漏
也不重复
确定枚举对象、范围和判定条件。
逐一枚举可能的解，并验证每个解是否为正确的解。
百钱买百鸡
枚举算法的生活实例
我国古代数学家张丘建在他的《算经》中提出了著名的“百钱买百鸡”问题：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，问翁、母、雏几何？
数量条件：母鸡数量+公鸡数量+小鸡数量=100只
价格条件：3*母鸡数量+5*公鸡数量+1/3*小鸡数量=100元
百钱买百鸡
确定枚举对象 确定枚举范围 确定判断条件
公鸡（5元） 0≤x≤20 ① x+y+z=100
② 5x+3y+ z=100
母鸡（3元） 0≤y≤33 小鸡（1/3元） 0≤z≤100 全部买小鸡,则最多可以买100×3只,但鸡总共只有100只,因此z的取值范围为0全部买母鸡,则最多可以买100/3只,因此y的取值范围为0≤y33;
注意解需满足判断条件，同时符合实际生活！
任务二
循环了几次呢？
初始计数为0
计数+1
输出循环计数
枚举出符合条件的解
循环次数多
为什么步长设置为3？
答案与步长为1是否一致？
买一支小鸡花费，
钱以整数值增加较好
任务三
z=100-x-y
任务三
z=100-x-y
循环次数大大减少
枚举对象：公鸡、母鸡、小鸡
枚举范围: 公鸡0-20只
母鸡0-33只
小鸡0-100只
判断条件枚举范围
VS
提高算法效率
本课总结
本课总结
确定枚举对象、范围和判定条件
1
逐一枚举可能的解——循环结构
2
逐一验证是否为正确的解——分支结构
3
减少枚举对象和枚举范围，提高算法效率
4
拓展任务
将一张100元面额的纸币兑换成零钱（5元、10元、20元中任意多个面额），编写程序计算有多少种换法。

展开更多......

收起↑