资源简介

(共16张PPT)
分析问题
分析出已知条件、求解目标和已知与未知的关系。
设计算法
然后推导构建出解析式。
编程调试
最后将数学解析式转换成程序表达式，进行编程实现并调试。
解析算法
基于解析算法的问题解决
课堂小结
2.4 常见算法的程序实现
1.基于解析算法的问题解决
2.基于枚举算法的问题解决
体验探索
鸡兔同笼
问题描述 ：一个笼子里面关了鸡和兔子（鸡有 2 只脚，兔子有 4 只脚，没有残疾的），上有35个头，下有94只足，问笼子里面有多少只鸡，有多少只兔子。
解析算法
1）分析问题
已知条件：假设鸡有x只,兔子有y只，头a有35个，足b有94足
求解 ：x,y值
二者之间的关系：x+y=a 2x+4y=b
2）设计算法
解析式x=2a-b//2 y=b//2-a
3）编程测试
a=35
b=94
x=2*a-b//2
y=b//2-a
print("鸡有：",x,"只")
print("兔子有：",y,"只")
鸡 兔 头的数量 脚的数量
1 1 1+1=2 1*2+1*4=6
1 2 1+2=3 1*2+2*4=10
1 3 1+3=4 1*2+3*4=14
…… …… …… ……
34 1 34+1=35 34*2+1*4=72
穷举法（枚举法）解决鸡兔同笼问题
一一列举可能的解，即枚举范围是多少？比如鸡是1~34只
逐一检测可能的解，判定条件是什么？比如头的数量1+3=4 脚的数量 1*2+1*4=6
1.分析问题
2.设计算法
一一列举 循环
逐一检测 分支
开始
鸡从1-34序列中依次取数
兔子的数量=35-鸡
2*鸡+兔子*4==94
输出鸡和兔子的数量
结束
False
False
True
True
for chicken in range(1,35):
for rabbit in range(1,35):
if (chicken+rabbit==35 and 2*chicken+4*rabbit==94):
print("鸡有",chicken,"只。")
print("兔子有",rabbit,"只。")
3.编程调试
优化程序
for chicken in range(1,35):
for rabbit in range(1,24):
if (chicken+rabbit==35 and 2*chicken+4*rabbit==94):
print("鸡有",chicken,"只。")
print("兔子有",rabbit,"只。")
　　枚举算法，也称枚举法是依据问题的已知条件，确定答案的大致范围，在此范围内逐一列举出它所有可能的情况的方法。在列举过程中，既不能遗漏，也不能重复，通过逐一判断，验证哪些情况满足问题的条件，从而得到问题的答案。
2.4.2 基于枚举算法的问题解决
１.基本概念
枚举算法解题的基本思路：
（1）确定枚举对象、范围和判定条件。
（2）逐一枚举可能的情况并验证每个情况是否符合条件。
枚举算法的思想：
一一列举
逐一检验
开始
枚举值在给定范围吗？
取下一个枚举值
枚举值符合条件吗？
输出该枚举值
结束
False
False
True
True
循环
分支
问题：票据上有一个4位数字组成的编号，甲说：数字编号的前两位数字相同，但都不是零；乙说：数字编号的后两位数字是相同的，但与前两位不同；丙说：数字编号是一个整数的平方。根据以上线索推断出编号。
例1 票据中模糊数字推断问题
假设四个数字应是AABB，其中A≠ 0，A≠B，且AABB是一个整数的二次方。
已知条件
求解目标
二者的关系
票据中的数字。
要求解的4位数字的编号必须同时满足所有的已知条件。
分析问题
设计算法
根据问题分析，只要一一列举出4位数字AABB中A与B的所有可以组合，保证A≠B且A ≠0,再验证二次方问题，就可以得到问题的解。因此，该问题可使用枚举算法求解完成，其算法的流程图如右所示：
结束
开始
A=1
A<10
K=1000A+100A+10B+B
C=sqrt(k)的整数部分
A ≠B
c*c=k
输出票据编号k
B=B+1
B=0
B<10
A=A+1
False
False
False
False
True
True
True
编程实现与调试
import math
A=1
while A<10:
B=0
while B<10:
if A!=B:
k=A*1000+A*100+B*10+B
c=int(math.sqrt(k))
if c*c==k:
print("票据编号是：",k)
B=B+1
A=A+1
保存文件，调试程序
枚举算法要注意的问题：
题解的可能范围，不重不漏
考虑优化算法，缩小枚举范围，提高解决问题的效率。
寻找1000以内的所有素数
实践活动
编程求解1000以内的所有素数。素数是在大于1的自然数中，除了1和它本身以外不再有其他因数的数，如2，3，5，7，11，……
1.分析该问题的枚举范围和验证条件。
2.用流程图描述问题求解的算法，并编程实现。
3.教学资源平台中提供了本题的两种不同的算法方案（算法A和算法B）,任选一中自己设计的算法进行对比分析，完成表2.4.1。思考其中哪种算法能更高效地解决问题，为什么？
（详见P75页内容或学习单）
练习提升
2.韩信是汉初著名军事家，传说他统计士兵数目有个独特的方法。例如，先令士兵排成5列纵队，结果余1人；接着，命令士兵排成6列纵队，结果余5人；再命令士兵排成7列纵队，结果余4人；最后，命令士兵排成11列纵队，结果余10人。这样他便知道士兵的总人数了。这种计数的方法被后人称为“韩信点兵”。试编写程序计算士兵的数目。
结合学习单中的程序代码绘制流程图
如何避免？
思考两个问题：
　　1.能不能运用今天所学知识任意破解别人的密码？
　　2.如何保护自己的密码安全？
课堂总结
枚举算法思想在生活中解决问题的适用情况及特点：
　　1.求解的答案数量有限。
　　2.所有的可能情况都符合一定的规则。

展开更多......

收起↑