(
课件网) 算法及其特征 ———枚举算法 学 习 目 标 深入学习算法的重要特征 运用Python语言实现简单算法，解决问题 学会用枚举算法解决问题 01 02 03 PART 1 算法及其特征 一、旧知回顾 什么是算法？ 怎样描述算法？ 算法的基本特征有哪些？ 二、问题导入 小王报名参加学校社团时。面试中有一道IQ题：有四个装了药丸的罐子，每个药丸都有一定的重量，其中有一个药罐被污染了。每片被污染的药丸比污染前增重1克。只允许称量一次，判断出哪个罐子的药被污染了。 分析问题 考虑1颗药丸的质量变化，如果药丸被污染，则增重 克，否则增重0 克。 从任一药瓶中提取n颗药丸，如果被污染，则增重 克，否则增重0 克。 从第一罐中取出1颗，第二罐中取出2颗，第三罐中取出3颗，从第四罐中取出4颗（共10颗）。如果增重_____克，则_____号药瓶被污染。 输入：？ 计算：？ 输出：？ 几 几 思考： 三、算法及其特征 1 n 请设计程序并运行，使输入10颗药丸的总重量及单颗药丸标准质量就可以看到结果，找到被污染的药丸。 2.设计算法 分析 现象（可多选） 算法的特征 哪些信息属于输入： 输入项： □0个输入 □1个输入 □多个输入 哪些信息属于输出： 输出项： □0个输出 □1个输出 □多个输出 执行的结果： 执行的结果：□确定的 □不确定的 □都可以 需要 步得到结果。 执行的步骤：□有限 □无限 □都可以 题耗时 。 执行的时间：□有限 □无限 □都可以 单颗标准重量，称重后重量 多出的重量 找到被污染的瓶子 4 几秒 √ √ √ √ √ 0个或多个输入 一定有输出 确切性 有穷性 可行性 称重后的质量-10颗标准质量 danke=int(input(‘请输入每颗药丸的标准重量：’)) zongde=int(input(‘请输入药丸称得的重量：’)) x=zongde-10*danke print('被污染的药瓶序号是：',x) 3.编写程序 运行代码 PART 2 枚举算法 有一种算法是把所有可能的答案一一列举，合适就保留，不合适就丢弃。这种方法称作“枚举”或“穷举”。 四、枚举算法 枚举算法基本思想：一 一列举、逐一检验 枚举法解决问题的一般结构： 枚举使用要点：确定枚举范围和验证条件 循环+判断 密码暴力破解 火柴棒摆数字 查找罪犯指纹 生活中的枚举： 查找1000以内所有能被3、5 、7整除的数： 例： 范围： 条件： 1--1000 整除3 整除5 整除7 for i in range(1,1001): if (i%3==0)and (i%5==0)and (i%7==0): print(i) GO 循环 判断 这次面试的冠军就在小王和其他A、B、C、D四位同学中。消息很快传到了班上，当A、B、C、D四人回到班上，小王迫不及待地问他们中谁得了冠军。四人相对一笑： A说：“不是我。” B说：“是C。” C说：“是D。” D说：“C说的不对。” 原来他们想让小王猜出答案，而且有一人说了假话。小明很快就知道了答案，大家都想知道他的方法。你能判断到底谁是冠军吗？ 三、枚举算法 解析：利用枚举法，逐一假设A、B、C、D是冠军，判断是否正确。 冠军 A说：“不是我。” B说：“是C。” C说：“是D。” D说：“C说的不对。” A B C D 分子问题+设计算法 × × × × × × × × √ √ √ √ √ √ √ √ 用程序求谁是冠军时，我们需要把每个人说的话转化成计算机能够执行的表达式。如A说：“不是我。”可以表示为“i!='A'”，其中i为枚举的冠军选手编号。 冠军 i!=‘A’ i==‘C’ i==‘D' i!='D’ A × × × √ B √ × × √ C √ √ × √ D √ × √ × 实现方法：布尔值数值化 i!=‘A’的运算结果是一个逻辑值，在数值计算中会自动转换成1（True）或0（Flase） 分析以下代码的含义，理解解题思路。 xuanshou=['A','B','C','D'] #设置选手列表 for i in xuanshou: #循环读取选手编号 tiaojian=(i!=‘A’)+(i ... ...
