算法描述与设计.ppt

小结 小结 特征：有输入 确定性 有穷性 有输出 可行性 算法的描述 用自然语言描述算法 用流程图描述算法 用伪代码描述算法 算法——解决问题的方法和步骤 一个问题，可能有多种算法 ，应该通过分析、比较、挑选一种最优的算法。一个好算法必须用到科学的方法 ，应该好好学习各学科处理问题的科学方法。 课堂练习 2、阅读右边的流程图如果r=2,h=3 ，那么V= ; 1、已知一个学生的语文成绩为89,数学成绩为96,外语成绩为99.求他的总分和平均成绩的一个算法为： 第一步：输入A=89 B=96 C=99； 第二步： ； 第三步： ； 第四步： 。 总分S=89+96+99 平均分P=S/3 输出S、P 12π 课堂练习 1，输入正方形的边长为a，求面积S； 开始 输入边长a 计算S=a*a 输出面积S 结束 课堂练习 求A除以B的商。 课后实践 用流程图描述求“S=A/B,求S的值” 题一 用流程图描述求ax2 + b = 0方程的解 题二 用表格比较自然语言、流程图和伪代码3种描述方法的优缺点 题三 * 算法的描述与设计 北海七中 王丹丹 一个人带一只羊、一只狼和一蓝菜过河，只有一只小船，一次只能带一个物品。如果羊和狼在一起，狼吃羊；如果羊和草在一起，羊吃草。怎样才能安全渡河？ 要求：现在请同学们来设计一个方案,把3样东西安然无恙的带过河。 思考 1 2 3 4 这个方案总共有多少步？ 哪几步顺序可以颠倒？ 通过以上例子，我们能不能总结出什么是算法？ 【问题一】中，我们是用什么来描述算法的？ 5 算法还有其他的描述方法吗？ 一个人带一只羊、一只狼和一蓝菜过河，只有一只小船，一次只能带一个物品。如果羊和狼在一起，狼吃羊；如果羊和草在一起，羊吃草。怎样才能安全渡河？ 第三步：人和菜过河，人返回，留下菜； 过河方案 牧羊人过河方案 第二步：人和狼过河，人和羊返回，留下狼； 第一步：人和羊过河，人返回，留下羊； 第四步：人和羊过河。 算法就是解决问题的方法和步骤，而且步骤是有限的。在以后的编程中也要记住了，有些步骤是可以颠倒的，不影响程序的结果；但是有些一旦颠倒了那最终的结果也就全变了。 算法的概念 算法 算法的特征 1 有穷性：执行步骤和每步执行时间都是有限的 算法特征 确定性：每一步都有确切的含义 2 输出：至少产生一个输出 4 3 输入：有零个或多个输入 5 可行性：原则上能精确运行 算法的特征练习 第1题： ① S=1 ② 将S的值增加1 ③重复步骤② 解答：该算法的步骤②被重复执行了无穷次，不符合有穷性的特征。 算法的特征练习 第2题： ① L=1 ② 输出L/自然数 解答：自然数没有具体指明是哪个数，不符合算法的确定性。 算法的特征练习 第3题： ① R=2 ② S=3.14*R*R ③ 输出面积S 说明：如果算法中在执行时已包含计算所需要的初始数据，不必另外提供数据。符合算法的特征有零个或多个输入。 ① 输入R的值 ② S=3.14*R*R ③ 输出面积S 算法的特征练习 第4题： ① R=2 ② S=3.14*R*R ③ C=2*3.14*R ④ 输出面积S,周长C 解答：解决问题一定要有答案，有答案就要有输出，要符合算法的特征有一个或多个输出。 算法的特征练习 第5题： ① S=-2 ② 计算S的平方根 解答：S是负数，该算法不可行，不符合算法的可行性。 算法的描述方法 算法的描述 用自然语言描述算法 用流程图描述算法 用伪代码描述算法 自然语言 用自然语言表达算法，就是把算法的各个步骤，依次用人们熟悉的自然语言表示出来。 优点：容易理解 缺点：书写较烦、不确定性、对复杂的问题难以表达准确、不能被计算机识别和执行 自然语言描述 例：这个人连老张也不认识。 第三步：人和菜过河，人返回，留下菜； 过河方案 牧羊人过河方案 第二步：人和狼过河，人和羊返回，留下狼； 第一步：人和羊过河，人返回，留下羊； 第四步：人和羊过河。 流程图 也称为程序框图，它是算法的一种图形化表示方法。 优点：形象、直观、容易理解 流程图描述 程序框 名称 功能 开始/结束 算法的开始和结束 输入/输出 输入和输出信息 处理 计算与赋值 判断 条件判断 流程线 算法中的流向 连接圈 表示算法流向出口或入口连接点 常用的“流程图”所用的基本符号 第三步：人和菜过河，人返回，留下菜； 过河方案 第二步：人和狼过河，人和羊返回，留