资源简介

(共17张PPT)
2.4.2基于枚举算法的问题解决
xxxx学校 xxxx老师
生活中的枚举
导入
在一筐水果中找出坏掉的水果扔掉
在一串相同的钥匙中找出所有能打开这把锁的钥匙
忘记了三位数密码箱的密码
一个一个查看，然后去除坏的水果
一把一把地试，找到然后取出
从000开始，001，002…………找到正确密码后记下来
共同点？
枚举算法
2.4
一一列举
逐一检验
概念：枚举法是依据问题的已知条件，确定答案的大致范围，在此范围内列举出它所有可能情况的方法。(P73)
不遗漏
不重复
检验条件
（一）枚举算法的概念及特征
枚举算法
2.4
1.找出能同时被7和11整除的1000以内的整数。
枚举范围：
检验条件：
如何用代码写出检验条件：
1—1000之间的整数
能同时被7、11整除
①x%7==0 and x%11==0
②x%77==0
③x/7==x//7 and x/11==x//11
任务一
枚举算法
2.4
一一列举
循环结构（for语句、while语句）
逐一检验
分支结构（if判断语句）
（二）枚举算法实现方法
枚举算法
2.4
for（列举所有可能解）:
if(判断条件）：
输出解
也可以使用while语句实现
（二）枚举算法实现方法
枚举算法基本框架：
枚举算法
2.4
例：票据中模糊数字推断问题。
一张票据上有一个由4位数字组成的编号，甲说数字编号的前两位数字相同，但都不是零；乙说数字编号的后两位数字是相同的，但与前两位不同；丙说数字编号是一个整数的二次方。试根据以上线索推断出编号。
（三）如何设计枚举算法
枚举算法
2.4
1. 分析问题
已知条件：假设4位数字的编号是AABB，其中A≠0，A≠B，且AABB是一个整数的二次方；
求解目标：票据中的数字
变量A
变量B
变量k
变量c
枚举对象 枚举范围 检验条件
A
B 1—9之间的整数
0—9之间的整数
A≠B
c*c=k
（三）如何设计枚举算法
一一列举
逐一检验
枚举对象 枚举范围 检验条件
A
B 1—9之间的整数
0—9之间的整数
A≠B
c*c=k
枚举算法
2.4
2. 设计算法
import math
for A in range(1, 10):
for B in range (0, 10):
if A != B:
k = A * 1000 + A * 100 + B * 10 + B
c = int(math.sqrt(k)) # 求票据中数字的平方根并取其整数部分
if c * c == k: # 若k是完全平方数，则找到该票据编号
print("票据编号是：", k)
枚举算法
2.4
3. 编程调试
（三）如何设计枚举算法
4. 保存文件，运行程序
枚举算法
2.4
（四）枚举算法应用
百钱买百鸡问题：
公元6世纪，中国的《张丘建算经》有一道著名的百鸡问题：“今有鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一，凡百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？”
枚举算法
2.4
（四）枚举算法应用
已知条件：公鸡5文一只，母鸡3文一只，小鸡3只一文钱
变量x
变量y
变量z
求解目标：x，y，z 可能的值
分析问题
设计算法
编程调试
保存运行
枚举算法
2.4
（四）枚举算法应用
枚举对象 枚举范围 检验条件
x 1-20 x+y+z=100
x*5+y*3+z/3=100
y 1-33 z 1-100 分析问题
设计算法
编程调试
保存运行
枚举算法
2.4
（四）枚举算法应用
money=100 #一共100文钱
num=100 #一共100只鸡
for x in range(1,21): #列举条件一：公鸡只数可能为1-20
for y in range(1,【1】): #删除语句中的“【1】”，母鸡只数可能为1-33
for z in range(1,【2】): #删除语句中的“【2】”，（3小鸡）只数可能为1-100
money1=x*5+y*3+z/3
num1=x+y+z
if money1==money and num1==num: #检验条件：100文钱是否用完了，买的鸡数量是否有100只
print (x,y,【3】) #删除语句中的“【3】”，输出公鸡、母鸡、小鸡的数量
input("运行完毕，请按回车键退出...")
分析问题
设计算法
编程调试
保存运行
可以用枚举算法解决吗
破解密码
求方程2x+y =9的整数解
寻找1000以内的所有素数
求方程2x+y =9的正整数解
求方程2x+y =9的实数解
枚举算法
2.4
（五）小结
枚举算法
2.4
谢谢聆听

展开更多......

收起↑