1.2.2算法的描述.ppt

1、1.2算法和算法的描述,株洲市第十八中学,算法的描述与设计,有一个牧羊人带着一头羊,一只狼和一颗大白菜准备过河,他找到一只很小的船,每次只能带一样东西过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，牧羊人应如何过河？ 要求：现在请同学们来设计一个方案,把3样东西安然无恙的带过河。,问题一,第三步：人和菜过河，人返回，留下菜；,过河方案,牧羊人过河方案,第二步：人和狼过河，人和羊返回，留下狼；,第一步：人和羊过河，人返回，留下羊；,第四步：人和羊过河。,算法的概念,算法,什么是算法？(解决问题的方法与步骤） 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。

2、 通俗地说，算法就是用计算机求解某一问题的方法，是能被机械地执行的动作或指令的有穷集合。,算法的特征,能行性,输出,有穷性,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则,算法的描述方法,自然语言,优点：容易理解 缺点：书写较烦、不确定性、对复杂的问题难以表达准确、不能被计算机识别和执行,自然语言描述,自然语言,过河的方案: 第一步：人和羊过河，人返回，留下羊； 第二步：人和狼过河，人和羊返回，留下狼； 第三步：人和菜过河，人返回，留下菜； 第四步：人和羊过河,自然语言描述,S1：移项得 ax = - b ; S2：若a不等于0，则x=-b/a，结束 S3：若a=0，b=0，得x为任

3、意值，结束； S4：否则输出x无实数解，结束；,自然语言,例：求方程 ax + b = 0 的解。,流程图,常用的“流程图”所用的基本符号,流程图描述,流程图,优点：形象、直观、容易理解,伪代码,伪代码描述,输入 a , b If a = 0 then if b = 0 then 输出x为任意值 else 输出x无实数解 end Else x= -b/a End if,伪代码描述,优点：简洁、易懂、修改容易 缺点：不直观、错误不容易排查,算法的特征,有穷性：执行步骤和每步执行时间都是有限的,算法特征,确定性：每一步都有确切的含义,输出：至少产生一个输出,输入：有零个或多个输入,可行性：原则上能

4、精确运行,上机任务：每位同学都启动Visual Basic程序设计环境，输入程序代码，并调试运行。并保存工程。,算法的择优,处理同一个问题可能有不同的算法，采用什么样的算法更简单、方便呢？,著名数学家华罗庚“烧水泡茶”的两个算法。 算法一 第一步：烧水； 第二步：水烧开后，洗刷茶具； 第三步：沏茶。 算法二 第一步：烧水； 第二步：烧水过程中，洗刷茶具； 第三步：水烧开后沏茶。,第二个算法的科学性在于应用了“统筹方法”,区别？ 哪个更高效？,一个好算法必须用到科学的方法,算法在解决问题中的地位与作用,“烧水泡茶”两种算法的效率 算法是程序设计的核心，是灵魂。 编程解题实际上是从人工解题描述算法根据算法写出程序。 人会解决问题，就可以设计出算法，就可编程解决 编程解题不会难！,小结,小结,特征：有输入 确定性 有穷性 有输出 可行性,算法解决问题的方法和步骤,一个问