4.1 算法及其特征——枚举法 课件 2022—2023学年教科版（2019）高中信息技术必修1

算法——枚举法 /循环+判断/有穷性 /确定性/可行性/ 4. 1 讲课人： 时间：2022.9.12 1 学习目标 03 02 01 掌握枚举算法的一般流程，学会编写简单的程序实现枚举法。 理解枚举法的含义及特点，归纳枚举法的思维方式。 学习枚举法算法，加深对算法及算法的特征的理解。 2 共有7个鸡蛋，每天至少吃2个，吃完为止，共有几种不同的吃法？ 2+2+3 2+3+2 2+5 3+2+2 3+4 4+3 5+2 7 3 什么是枚举？ 枚举法解决问题的一般结构：循环+判断 优点：相对简单，易于理解。 只要时间足够，并且结果可能的情况是确定的、有限的，我们就能编写一个程序将所有结果都找到,它利用的是计算运行速度快，精确度高的特点。 枚举法（穷举法）：把所有可能情况一一列举，符合条件就保留，不符合条件就丢弃，直至找到所有符合条件的结果。 4 任务二 求解 “谁是冠军” 在一场精彩的赛车比赛中，冠军是A、B、C、D中的一位。A说:“不是我。”B说:“是C。”C说:“是D。”D说:“C说的不对。” 已知四个人中，有一个人说了假话，你能判断到底谁是冠军吗？ A B C D C说的不对 是D 是C 不是我 5 利用枚举法解决问题 逐一假设A、B、C、D是冠军，判断是否正确。 冠军 A说:“不是我。” B说:“是C。” C说:“是D。” D说：“C说的不对。” 说真话的人数 A × × × √ 1 B √ × × √ 2 C √ √ × √ 3 D √ × √ × 2 6 如何用计算机程序求谁是冠军？ 1.假设冠军人员 2.判断说真话人数 3.如果说真话的人数为3人，输出冠军编号 4.重复以上步骤，直到A、B、C、D都假设完成 实现方法: 7 算法实现(函数设计) 我们需要把每个人说的话转换成计算机能够执行的表达式。 如：A说：“不是我。” 可以表示为“ i !=‘A’ ”，其中i为枚举的冠军选手编号。 champion=['A','B','C', 'D’] #设置选手列表 for i in champion: # cond=(i!='A')+(i=='C')+(i=='D')+(i!=‘D’) # if cond==3: # print(“冠军是：”，i) # 输出冠军编号 枚举每一个选手是冠军 cond用来记录说真话的人数 如果说真话的人是3位 8 枚举的适用条件 1.要枚举的可能的情况是有限的，否则计算机在有效的时间内是无法完成计算的（有穷性） 2.要枚举的可能情况必须是确定的（确定性） 3.要枚举的可能情况是能够转换成计算机可计算的（可行性） 9 课后练习——拓展练习 10 课堂小结 11 枚举算法 分析问题，确定枚举对象和范围 一一列举，逐一检验 （不遗漏，不重复） 注意枚举法的使用限制条件（有穷性/确定性/可行性） 时代是思想之母，实践是理论之源。 12 $