(
课件网) 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 ... ...
