第三章 算法基础 课件(共38张PPT)　2023—2024学年粤教版（2019）高中信息技术必修1

(课件网) （1）把羊带到右岸； （2）空船返回左岸， 把狼带到右岸； （3）把羊带回左岸； （4）把卷心菜带到右岸； （5）空船返回左岸， 把羊带到右岸。 第三章 算法基础 一、算 法 1.算法的概念 算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。 1.算法的概念 通俗地说，算法就是计算机求解某一问题的方法，是能被执行的动作或指令的有穷集合。 2.人工解决问题 VS 计算机解决问题 例1：圆周率的计算 历史人物 研究方法/时间 圆周率位数（范围） 阿基米德（古希腊） 内外接多边形（96边形） 3.141851 祖冲之（中国） 割圆术（公元480年） 3.1415926~3.1415927 鲁道夫（德国） 1596年 1610年 20位小数值 35位小数值 梅钦（英国） 无穷级数（1706年） 突破100位 Jurij Vega 梅钦类公式（1789年） 140位（137位正确） 弗格森、伦奇 1948年 808位 2.人工解决问题 VS 计算机解决问题 例1：圆周率的计算 时间节点 花费时间 圆周率位数 1950年 70小时 2037位 1955年 13分钟 3089位 1973年 100万位 1989年 10.1亿位 2010年 5万亿位 2011年 一年（自组装计算机） 10万亿位 2.人工解决问题 VS 计算机解决问题 例2：韩信点兵 西汉大将韩信，善于带兵，神机妙算，能征善战。一次阅兵时，韩信要求士兵排成3路纵队，此时末尾多出2人，改排成5路纵队，末尾多出3人，再排成7路纵队，末尾余下2人。这时，领兵的部下报告说，这队士兵一共有2395人，韩信立刻摇头说：不对，实际实际只有（ ）人，部下迟疑地回去，又重新清点人数，果真是那么多人，部下们因此对韩信十分佩服。 人数范围x：2300~2400 从2300开始，逐个数去试试，如果这个数能同时被3、5、7整除后的余数分别为2、3、2，则这个数就是正确的人数。 例2：韩信点兵 例2：韩信点兵 ①总人数x=2300； ②判断x是否在2300~2400之间，满足则执行下一步，否则结束； ③判断x是否满足x÷3······2并且x÷5······3并且x÷7······2，满足则执行第⑤步，不满足则执行第④步； ④x在原来的基础上加1，回到第②步； ⑤输出x。 思考1：计算机解决问题的过程是怎样的？ 例2：韩信点兵 ①总人数x=2300； ②判断x是否在2300~2400之间，满足则执行下一步，否则结束； ③判断x是否满足x÷3······2并且x÷5······3并且x÷7······2，满足则执行第⑤步，不满足则执行第④步； ④x在原来的基础上加1，回到第②步； ⑤输出x。 3.算法的特征 （1）有穷性； （2）确定性：每个步骤必须有确切的定义，不能出现模棱两可的情况； （3）数据输入：算法可以有零个或多个输入； （4）数据输出：算法必须有一个或多个输出； （5）可行性：任何步骤都可执行，能在有限时间内完成。 4.算法的描述 （1）用自然语言描述算法 易掌控 当算法较复杂时，用自然语言很难清晰表示 自然语言具有歧义性，容易导致算法执行的不确定性 4.算法的描述 （2）用流程图描述算法 使算法的流程描述得清晰、简洁 流程图的基本图形及其功能 起始框：表示算法的开始和结束 处理框：表示完成某种操作 判断框：表示根据一个条件成立与否，决定执行两种不同操作的其中一个 输入、输出框：表示数据的输入输出 流程线：用箭头表示程序执行的流向 朋友的意思 程序猿的理解 例2：韩信点兵 ①总人数x=2300； ②判断x是否在2300~2400之间，满足则执行下一步，否则结束； ③判断x是否满足x÷3······2并且x÷5······3并且x÷7······2，满足则执行第⑤步，不满足则执行第④步； ④x在原来的基础上加1，回到第②步； ⑤输出x。 4.算法的描述 （3）用伪代码描述算法 伪代码是介于自然语言和计算机语言之间的文字和符号。是一种非正 ... ...