4.1 算法及其特征课件-2025-2026学年教科版高中信息技术必修1

第四单元 计算与问题解决 4.1 算法及其特征 授课人：吐洪江·祖农 情景导入 农夫过河问题：一个农夫带着一只狼， 一只羊和一颗白菜过河。河边只有一 条船，由于船小，农夫一次只能带其 中一样过 河。如无人看管，狼要吃羊， 羊要吃菜。 问:农夫如何安排过河，才能使狼、羊、 白菜都安全过河。 情景导入 第一步 农夫带羊过河，把羊丢在对岸； 第二步 农夫返回带白菜过河，把白菜丢在对岸，带羊返回； 第三步 农夫带狼过河，把狼与白菜丢在对岸； 第四步 农夫返回带羊过河。 开始 输入菜狼羊、规则 处理人和羊过河，人返回、留下羊 人和狼过河，人和羊返回、留下狼 人和菜过河，人返回、留下菜 人和羊过河 结束 判断都过河 是 否 解决问题的方法与步骤 算法的概念 1、自然语言 2、流程图 3、代码 算法的描述 1、食堂打饭：确定自己要吃的饭排队打饭刷卡/刷脸 2、超市购物：确定自己要买的物品挑选支付 生活中的算法 算法 知识回顾 知识回顾 活动1 寻找“开关对应关系” 一个房间有三盏灯，房间外有三个开关分别控制这三盏灯，在只允许进房间一次的情况下，如何判断哪个开关控制哪盏灯？ 任务一 探讨面试题的解决方案 灯的状态 第一关：“寻找开关对应关系” 灯亮 灯灭 发热 不发热 思考：如何能使3盏灯处于不同的状态？ ① ② ③ 第一步： 第二步： 第三步： 第四步： 第五步： …… 打开1、2两个开关 过2分钟后关闭1号开关 进房间，亮着的灯是由2号开关控制 摸一下另外两盏不亮的灯，发热的灯泡是由1号开关控制 不亮又不热的灯是由3号开关控制 第一关：“寻找开关对应关系” 第一关：“寻找开关对应关系” 关1号开关 灯亮？ 灯热？ 该灯由2号开关控制 该灯由1号开关控制 该灯由3号开关控制 第一关：“寻找开关对应关系” 1、“开关对应关系” 算法中有（ ）个输出项？ 2、“开关对应关系”算法的执行结果是（ ）。 3、“开关对应关系”算法的执行步骤是（ ）。 A.0个 B.1个 C.多个 A.确定的 B.不确定 C.都可以 A.有限的 B.无限的 C.都可以 C A A 比较算法流程图，说出特点 算法的特征 有穷性 确切性 输出项 可行性 输入项 算法必须能在执行有限个步骤之后终止。 算法中的每一次运算都有明确的定义，具有无二义性，并且可以通过计算得到唯一的结果。 算法一定要有输出。任何算法都不能 “无功而返＂ 。 输入项。一个算法有0个或多个输入，以刻画运算对象的初始悄况，所谓0个输入是指算法本身给出了初始条件。 算法中执行的任何计算都可以在有限时间内完成（也称为有效性）。 巩固联系 1.算法的重要特征不包括（ ） A．无穷性 B．确定性 C．数据输出 D．可行性 2.下列关于算法输入输出的描述，正确的是（　　） A．有一个或多个输入、有一个或多个输出 B．有一个或多个输入、有零个或多个输出 C．有零个或多个输入、有一个或多个输出 D．有零个或多个输入、有零个或多个输出 A　 C 巩固联系 3.以下对算法特点的叙述中，错误的是（　　） A．可以使用程序设计语言来实现 B．一定有输入 C．一定有输出 D．明确及无二义性 4.下列关于算法特征的的描述，正确的是（　） A．一个算法的每一个步骤必须有确切的含义 B．一个算法可以有多个输出，但是至少有一个输入 C．一个算法可以永无止境的进行下去 D．一个算法不一定必须可行，理论上想法对就可以执行 B A 巩固联系 5.下列关于算法描述错误的是（　　） A．算法必须在有限步骤内实现 B．算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述 C．算法是解决问题的方法和步骤 D．一个有效的算法至少要有一个输入 D 共有7个鸡蛋，每天至少吃2个，吃完为止，共有几种不同的吃法？ 2+2+3 2+3+2 2+5 3+2+2 3+4 4+3 5+2 7 枚举 16 什么是枚举？ 枚举法解决问题的一般结构：循环+判断 优点：相对简单，易于理解。 只要时间足够，并且结果可能的情况是确定的、有限的，我们就能编写一个程序将所有结果都找到,它利用的是计算运行速度快，精确度高的特点。 枚举法（穷举法）：把所有可能情况一一列举，符合条件就保留，不符合条件就丢弃，直至找到所有符合条件的结果。 枚举 17 任务二 求解 “谁是冠军” 在一场精彩的赛车比赛中，冠军是A、B、C、D中的一位。A说:“不是我。”B说:“是C。”C说:“是D。”D说:“C说的不对。” 已知四个人中，有一个人说了假话，你能判断到底谁是冠军吗？ A B C D C说的不对 是D 是C 不是我 枚举 18 利用枚举法解决问题 逐一假设A、B、C、D是冠军，判断是否正确。 冠军 A说:“不是我。” B说:“是C。” C说:“是D。” D说：“C说的不对。” 说真话的人数 A × × × √ 1 B √ × × √ 2 C √ √ × √ 3 D √ × √ × 2 枚举 19 如何用计算机程序求谁是冠军？ 1.假设冠军人员 2.判断说真话人数 3.如果说真话的人数为3人，输出冠军编号 4.重复以上步骤，直到A、B、C、D都假设完成 实现方法: 枚举 20 算法实现(函数设计) 我们需要把每个人说的话转换成计算机能够执行的表达式。 如：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位 枚举 21 枚举的适用条件 1.要枚举的可能的情况是有限的，否则计算机在有效的时间内是无法完成计算的（有穷性） 2.要枚举的可能情况必须是确定的（确定性） 3.要枚举的可能情况是能够转换成计算机可计算的（可行性） 枚举 22 课后练习——拓展练习 枚举 23 总结 $$