2.2算法的概念及描述

走进信息技术 第一课 2.2算法的概念及描述 2023 Hello,world! 主讲人： 小品《钟点工》大象装冰箱 小品《钟点工》大象装冰箱 步骤： 1.打开冰箱门 2.把大象放进去 3.关上冰箱门 问题的解决方法、步骤——算法 PART 01 算法的定义 PART 02 算法的特征 PART 03 算法的描述 目录 CONTENTS 4 算法的定义 1 PART 01 5 问题探究--农夫过河 一个农夫带着一只狼、一头羊和一颗白菜要过河,但只有一条小船可用。乘船时，农夫每趟只能带一样东西。 当农夫在场的时候，这三样东西相安无事。一旦农夫不在，狼会吃羊,羊会吃白菜。请设计一个方案，使农夫能安全地将这三样东西带过河。 请同学们分组讨论这个问题的解决方案 一个农夫带着一只狼、一头羊和一颗白菜要过河,但只有一条小船可用。乘船时，农夫每趟只能带一样东西。 当农夫在场的时候，这三样东西相安无事。一旦农夫不在，狼会吃羊,羊会吃白菜。请设计一个方案，使农夫能安全地将这三样东西带过河。 问题探究--农夫过河 一个农夫带着一只狼、一头羊和一颗白菜要过河,但只有一条小船可用。乘船时，农夫每趟只能带一样东西。 当农夫在场的时候，这三样东西相安无事。一旦农夫不在，狼会吃羊,羊会吃白菜。请设计一个方案，使农夫能安全地将这三样东西带过河。 思考以下问题： （1）小组得出的方案共有多少步？ （2）这些步骤的顺序是固定不变的吗？ 问题探究--农夫过河 参考方案1： （1）人和羊过河，人返回，留下羊。 （2）人和狼过河，人和羊返回，留下狼。 （3）人和菜过河，人返回，留下菜。 （4）人和羊过河。 参考方案2： （1）人和羊过河，人返回，留下羊。 （2）人和菜过河，人和羊返回，留下菜。 （3）人和狼过河，人返回，留下狼。 （4）人和羊过河。 问题探究--农夫过河 ? 算法的定义 算法的概念 为解决一类特定问题而采取的 确定的、有限的步骤。 有些步骤可以颠倒，不影响最终结果。 有些步骤不能颠倒，一旦颠倒，最终的结果就完全不一样。 算法的定义 广义的算法既包括传统意义上计算任务，也可以是生活中各种事物的处理。 广义算法 算法是为解决一类特定问题而采取的确定的、有限的步骤。 古代的算法 古代的算法主要指的是“算术”，即数值的算术运算。随着科学技术的发展，算法的外延和内涵逐渐发生着变化。 计算机算法 计算机领域内，算法指的是用计算机解决问题的步骤。 古代的算法 解法一：《孙子算经》 上置头，下置足，半其足，以头除足，以足除头，即得。也就是兔子的只数=总腿数÷2－总只数。 因此，兔子的数量=94÷2-35=11（只）。 解法二：列方程法 第一步，设有x只鸡，y只兔； 第二步，列方程： 第三步，解方程求得：x=23,y=12； 第四步：答：笼子里有23只鸡，12只兔。 “鸡兔同笼”是我国古代数学著作《孙子算经》中的一个有趣而具有深远影响的问题。 今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？这四句话的意思是：有若干只鸡兔同在一个笼子里，从上面数，有35个头，从下面数，有94只脚。问笼中各有多少只鸡和兔？ 计算机算法 猜数游戏 算法在生活中的应用 电梯按照一定的算法响应用户请求，停靠到相应的楼层 “互联网+单车”=“共享单车” 算法的特征 2 PART 02 15 算法的特征 阅读课本48页算法的特征部分，把思维导图补充完整。 算法的特征 阅读课本48页算法的特征部分，把思维导图补充完整。 在计算机领域，算法作为一个精心设计的运算序列，描 述了计算机如何将输入转化为输出的过程。 算法一般具有如下特征: 有输入。一个算法一般要求有0个或多个输入，以描述运算对象的初始情况。 有输出。一个算法可以有一个或多个输出，以反映对输入数据加工后的结果。 有穷性。算法的有穷性指算法必须能在执行有限个步骤之后终止，也就是算法步骤不能是无限的。 可行性。算法中的每一步操作都是可以执行的，或者都可以分解成计算机可执行的基本操作。 确定性。算法的每个步骤都具有确定的含义，没有歧义。模糊不清、模棱两可或带有二义性的描述都会影响算法的确定性。 算法的特征 1、把大象放冰箱是不是算法？ 不是算法，不满足算法的可行性。 2、计算宇宙的面积是不是算法？ 不是算法，不满足算法的可行性。 算法的特征 3、写出所有的偶数是不是算法？ 不是算法，不满足算法的有穷性。 4、找出唱歌最好听的人是不是算法？ 不是算法，不满足算法的确定性。 算法的特征 例题5: 24-3X=3 3X=24-3 3X=21 X=7 例题6: 已知三角形的底为5cm，高为4cm，求三角形的面积。 5×4÷2=10（平方厘米） 答：三角形的面积为10平方厘米。 算法必须要有？但有时却可以没有？ 什么是输入？什么是输出？ 算法的特征 有输入 算法的每个步骤都具有确定的含义（没有歧义） 算法的每一步操作都是可执行的 算法必须能在执行有限个步骤之后终止 （算法步骤不能是无限的） 有输出 一个算法要求有0个或多个输入 一个算法要求有1个或多个输出 有穷性 确定性 可行性 算法特征 算法的描述 3 PART 03 22 问题探究--计算BMI 自然语言描述算法： 步骤1：输入身高 步骤2：输入体重 步骤3：BMI = 体重[kg] ÷ (身高[m])² 步骤4：输出BMI BMI，身体质量指数，是国际上常用的衡量人体肥胖程度的重要标准。 BMI = 体重[kg] ÷ (身高[m])²，计算BMI指数。 如何用自然语言描述算法？(自然语言是人们在日常生活中交流使用的语言） 自然语言描述算法的优缺点 还可以用哪些方式来描述算法？ 咬死猎人的狗 咬死猎人的“狗” 咬死“猎人的狗” 咬“死猎人”的狗 咬死“猎人的”狗 优点 容易理解 缺点 书写烦琐，不确定性，不能被计算机识别和执行。 流程图 开始 输入三角形的底d和高h S=d×h÷2 输出S 结束 1、这个流程图里出现了几种符号? 2、每种符号代表什么意思? 3、该流程图描述的什么内容? 流程图 名称 功能 开始/结束框 表示算法的开始或结束 输入/输出框 表示输入或输出数据 处理框 框中指出要处理的内容 判断框 用于表示条件判断及产生分支的情况 流程线 用于控制流程方向 连接点 用于连接因页面写不下而断开的流程线 用流程图描述算法的三种基本控制结构 A B 条件 A B True Flase 条件 B True Flase 顺序结构 选择结构 循环结构 用流程图描述算法的三种基本控制结构 举个栗子 x%2=0 True Flase 开始 输入一个正整数x 输出“偶数” 输出“奇数” 结束 选择结构 判断奇偶数流程图 密码是否正确 True Flase 开始 输入用户名 结束 输入密码 登录成功 登录失败 循坏结构 某APP登录模块流程图 流程图制作工具 问题探究--计算BMI BMI，身体质量指数，是国际上常用的衡量人体肥胖程度的重要标准。 BMI = 体重[kg] ÷ (身高[m])²，计算BMI指数。 如何用流程图描述算法？ 开始 输入身高height 结束 输入体重weight bmi=weight/height**2 输出BMI指数 直观易读 步骤清晰 结构明确 伪代码 如何用伪代码描述算法？ 伪代码 input height input weight bmi=weight/height**2 output bmi Python程序 height=float(input("请输入身高:")) weight=float(input("请输入体重:")) bmi=round(weight/height**2,1) print("BMI=",bmi) 类似程序设计语言，容易书写和理解 伪代码没有固定的、严格的语言规则，只要定义合理，没有矛盾即可。 算法的描述方法 自然语言 人们日常所用的语言，易于理解，但容易产生二义性。 ① 伪代码 类似程序设计语言，容易书写和理解。 ③ 流程图 顺序结构、选择结构和循环结构三种基本控制结构。 特点：直观易读、问题解决的步骤清晰简洁。 ② 课堂总结 感谢聆听 守正创新 引领未来 33 EVCapture5.0.3软件录制 Lavf58.33.100 本视频由湖南一唯信息科技开发的EV录屏软件录制, www.ieway.cn $$