(
课件网) 算法及其特征 1 信息意识 2 计算思维 3 数字化学习与创新 学习目标 01 根据具体的问题讨论分析出算法的基本特征。 03 能够将部分简单算法转换为程序，并调试运行得出结果。 02 尝试运用恰当的方法描述算法。 分析问题 设计算法 编写程序 调试运行 核心 课前回顾：计算机解决问题的过程 软件开发社团要招募新成员，报名的同学要经过面试才能加入。第一关面试题是：一个房间有3盏灯，房间外有3个开关分别控制这3盏灯，在只允许进房间一次的情况下， 如何判断哪个开关 控制哪盏灯？” 活动1：寻找开关对应关系 走进情景：探讨面试题的解决方案 1 2 3 灯只有亮、灭两种状态 因灯的特殊性，开灯的同时会伴随发光发热。 触摸还有冷、热两种状态 分析问题:灯的状态和特征 亮 灭 冷 热 灯的 状态 怎样让每盏灯的状态都是唯一的？ 分析问题:灯的状态和特征 第一步：为开关跟灯分别编号 第二步：打开1号跟2号两个开关 第三步：过几分钟后关闭1号开关 第四步：进房间，亮着的灯是由2号开关控制 第五步：摸一下另外两盏不亮的灯，发热的灯泡是由1号开关控制 第六步：不亮又不热的灯是由3号开关控制 自然语言描述 开始 为开关和灯分别编号 开1、2号开关，稍等片刻 关1号开关 进入房间 灯亮？ 该灯由2号 开关控制 灯热？ 该灯由1号 开关控制 该灯由3号 开关控制 结束 是 否 是 否 流程图描述 设计算法 开关对应关系 寻找开关对应关系的方法 跟步骤可以称为一个算法 解决该问题可以有多种方法 算法就是解决问题的方法和步骤 解决同一个问题的算法可能有多种 概念 理解 算法的概念 算法的 描述方法 自然语言 伪代码 流程图 自然语言就是使用日常所用的语言描述算法的步骤。 优点：使用简单，易于理解。 缺点：容易产生二义性。 流程图是用图形表示算法的一种常用工具。 优点：步骤清晰简洁，算法结构表达明确，适合初学者使用。 缺点：绘制过程繁琐，对于复杂问题，结构过于复杂，不易理解。 伪代码是采用一种类似程序设计语言的代码来描述算法。 优点：回避了程序设计语言严格的书写格式，叙述准确，无二义性，结构性强。 缺点：需要具备一定的程序设计语言基础，不利于初学者使用。 算法的描述 有穷性 算法必须能在执行有限个步骤之后终止，即算法一定要能够结束。 依次输出10000以内所有的正整数 依次输出所有的正整数 √ × 算法的特征 确切性 算法中的每一次运算都有明确的定义，具有无二义性，并且可以通过计算得到唯一的结果。 a=10 a=自然数 √ × 算法的特征 输入项 一个算法有0个或多个输入，以刻画运算对象的初始情况， 0个输入指算法本身给出了初始条件。 输入：a 输入：b 输出：a*b a=9 b=3 输出：a*b √ √ 算法的特征 输出项 算法一定要有输出，任何算法都不能无功而返。 至少有一个输出 就算问题是无解，也要把无解的状态输出 算法的特征 可行性 算法中的运算都必须是可以实现的，都可在有效时间内完成（也称为有效性） a=9 b=3 c=a/b a=9 b=0 c=a/b √ × 算法的特征 有穷性 确切性 输入项 输出项 + + + 可行性 + 算法的特征 面试的第二关是实验题：有四个装了药丸的瓶子，每颗药丸质量都相同，其中有一个药瓶中所有药丸被污染了。每颗被污染的药丸比污染前增重1克。已知每颗药丸的单颗标准质量，只允许称量一次，如何判断出哪个药瓶的药被污染了？ 活动2：寻找被污染的药丸 算法的特征实践探究 从每个药瓶中取出1颗药丸分别进行称重，肯定能判断出哪个药丸被污染，不符合只能称量一次的要求。 第一个药瓶取出1颗，第二个取出2颗 ，第三个取出3颗，第四个取出4颗共 10颗药丸。如果增重 克，则___号 药瓶中的药丸被污染。 考虑一颗药丸的重量变化，如果药丸 ... ...
