2.4.2基于枚举算法的问题解决课件人教-中图版高中信息技术必修1

分析问题分析出已知条件、求解目标和已知与未知的关系。设计算法然后推导构建出解析式。编程调试最后将数学解析式转换成程序表达式，进行编程实现并调试。解析算法基于解析算法的问题解决课堂小结2.4常见算法的程序实现1.基于解析算法的问题解决2.基于枚举算法的问题解决体验探索鸡兔同笼问题描述：一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有残疾的），上有35个头，下有94只足，问笼子里面有多少只鸡，有多少只兔子。解析算法1）分析问题已知条件：假设鸡有x只,兔子有y只，头a有35个，足b有94足求解：x,y值二者之间的关系：x+y=a2x+4y=b2）设计算法

解析式x=2a-b//2y=b//2-a3）编程测试a=35b=94x=2*a-b//2y=b//2-aprint("鸡有：",x,"只")print("兔子有：",y,"只")鸡兔头的数量脚的数量111+1=21*2+1*4=6121+2=31*2+2*4=10131+3=41*2+3*4=14……………………34134+1=3534*2+1*4=72穷举法（枚举法）解决鸡兔同笼问题一一列举可能的解，即枚举范围是多少？比如鸡是1~34只逐一检测可能的解，判定条件是什么？比如头的数量1+3=4脚的数量1*2+1*4=61.分析问题2.设计算法一一列举

循环逐一检测

分支开始鸡从1-34序列中依次取数兔子的数量=35-鸡2*鸡+兔子*4==94输出鸡和兔子的数量结束FalseFalseTrueTrueforchickeninrange(1,35):forrabbitinrange(1,35):if(chicken+rabbit==35and2*chicken+4*rabbit==94):print("鸡有",chicken,"只。")print("兔子有",rabbit,"只。")3.编程调试优化程序forchickeninrange(1,35):forrabbitinrange(1,24):if(chicken+rabbit==35and2*chicken+4*rabbit==94):print("鸡有",chicken,"只。")print("兔子有",rabbit,"只。")枚举算法，也称枚举法是依据问题的已知条件，确定答案的大致范围，在此范围内逐一列举出它所有可能的情况的方法。在列举过程中，既不能遗漏，也不能重复，通过逐一判断，验证哪些情况满足问题的条件，从而得到问题的答案。2.4.2基于枚举算法的问题解决１.基本概念枚举算法解题的基本思路：（1）确定枚举对象、范围和判定条件。（2）逐一枚举可能的情况并验证每个情况是否符合条件。枚举算法的思想：一一列举逐一检验开始枚举值在给定范围吗？取下一个枚举值枚举值符合条件吗？输出该枚举值结束FalseFalseTrueTrue循环分支问题：票据上有一个4位数字组成的编号，甲说：数字编号的前两位数字相同，但都不是零；乙说：数字编号的后两位数字是相同的，但与前两位不同；丙说：数字编号是一个整数的平方。根据以上线索推断出编号。例1票据中模糊数字推断问题假设四个数字应是AABB，其中A≠0，A≠B，且AABB是一个整数的二次方。已知条件求解目标二者的关系票据中的数字。要求解的4位数字的编号必须同时满足所有的已知条件。分析问题设计算法根据问题分析，只要一一列举出4位数字AABB中A与B的所有可以组合，保证A≠B且A≠0,再验证二次方问题，就可以得到问题的解。因此，该问题可使用枚举算法求解完成，其算法的流程图如右所示：结束开始A=1A<10K=1000A+100A+10B+BC=sqrt(k)的整数部分A≠Bc*c=k输出票据编号kB=B+1B=0B<10A=A+1FalseFalseFalseFalseTrueTrueTrue编程实现与调试importmathA=1whileA<10:B=0whileB<10:ifA!=B:k=A*1000+A*100+B*10+Bc=int(math.sqrt(k))ifc*c==k:print("票据编号是：",k)B=B+1A=A+1保存文件，调试程序枚举算法要注意的问题：题解的可能范围，不重不漏考虑优化算法，缩小枚举范围，提高解决问题的效率。寻找1000以内的所有素数实践活动编程求解1000以内的所有素数。素数是在大于1的自然数中，除了1和它本身以外不再有其他因数的数，如2，3，5，7，11，……1.分析该问题的枚举范围和验证条件。2.用流程图描述问题求解的算法，并编程实现。（详见P75页内容或学习单）练习提升2.韩信是汉初著名军事家，传说他统计士兵数目有个独特的方法。例如，先令士兵排成5列纵队，结果余1人；接着，命令士兵排成6列纵队，结果余5人；再命令士兵排成7列纵队，结果余4人；最后，命令士兵排成11列纵队，结果余10人。这样他便知道士兵的总人数了。这种计数的方法被后人称为“韩信点兵”。试编写程序计算士兵的数目。结合学习单中的程序代码绘