1、算法算法枚举法枚举法/循 环+判 断/有 穷 性 /确 定 性/可 行 性/4.1 讲课人:讲课人:时间:时间:2022.9.122022.9.12 学习目标学习目标030201掌握枚举算法的一般流程,学会编写简单的程序实现枚举掌握枚举算法的一般流程,学会编写简单的程序实现枚举法。法。理解枚举法的含义及特点,归纳枚举法的思维方式。理解枚举法的含义及特点,归纳枚举法的思维方式。学习枚举法算法,加深对算法及算法的特征的理解。学习枚举法算法,加深对算法及算法的特征的理解。共有7个鸡蛋,每天至少吃2个,吃完为止,共有几种不同的吃法?2+2+32+3+22+53+2+23+44+35+27什么是枚举?什
2、么是枚举?枚举法解决问题的一般结构:循环+判断优点:相对简单,易于理解。只要时间足够,并且结果可能的情况是确定的、有限的,我们就能编写一个程序将所有结果都找到,它利用的是计算运行速度快,精确度高的特点。枚举法(穷举法):把所有可能情况一一列举,符合条件就保留,不符合条件就丢弃,直至找到所有符合条件的结果。任务二任务二 求解求解“谁是冠军谁是冠军”在一场精彩的赛车比赛中,冠军是A、B、C、D中的一位。A说:“不是我。”B说:“是C。”C说:“是D。”D说:“C说的不对。”已知四个人中,有一个人说了假话,你能判断到底谁是冠军吗?A AB BC CD DC C说的说的不对不对是是D D是是C C不是
3、我不是我利用枚举法解决问题利用枚举法解决问题逐一假设A、B、C、D是冠军,判断是否正确。冠军冠军A A说说:“:“不是我。不是我。”B B说说:“:“是是C C。”C C说说:“:“是是D D。”D D说说:“C“C说的不对。说的不对。”说真说真话话的的人人数数A1B2C3 3D2如何用计算机程序求谁是冠军?如何用计算机程序求谁是冠军?1.假设冠军人员2.判断说真话人数3.如果说真话的人数为3人,输出冠军编号4.重复以上步骤,直到A、B、C、D都假设完成实现方法:算法实现算法实现(函数设计函数设计)我们需要把每个人说的话转换成计算机能够执行的表达式。如:A说:“不是我。”可以表示为“i i!=
4、A”,其中i 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位枚举的适用条件枚举的适用条件1.要枚举的可能的情况是有限的,否则计算机在有效的时间内是无法完成计算的(有穷性)2.要枚举的可能情况必须是确定的(确定性)3.要枚举的可能情况是能够转换成计算机可计算的(可行性)课后练习课后练习拓展练习拓展练习课堂小结课堂小结枚举算法分析问题,确定枚举对象和范围一一列举,逐一检验(不遗漏,不重复)注意枚举法的使用限制条件(有穷性/确定性/可行性)时代是思想之母,实践是理论之源。时代是思想之母,实践是理论之源。