12算法的描述与设计.ppt

《12算法的描述与设计.ppt》由会员分享，可在线阅读，更多相关《12算法的描述与设计.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、LOGO算法的描述与设计高级中学赵晓乐高级中学赵晓乐 算法的描述与设计有一个牧羊人带着一头羊,一只狼和一颗大白菜准备过河,他找到一只很小的船,每次只能带一样东西过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，牧羊人应如何过河？要求：现在请同学们来设计一个方案,把3样东西安然无恙的带过河。农夫问题1234这个方案总共有多少步？这个方案总共有多少步？ 哪几步顺序可以颠倒？哪几步顺序可以颠倒？同学们农夫过河问题解决了，那到底什么是算法？同学们农夫过河问题解决了，那到底什么是算法？ 【农夫问题】中，我们是用什么来描述算法的？【农夫问题】中，我们是用什么来描述算法的？ 5算

2、法还有其他的描述方法吗？算法还有其他的描述方法吗？ 过河方案牧羊人过河方案第一步：将羊运过去第二步：人返回第三步：将菜运过去第四步：将羊运过来第五步：将狼运过去第六步：人返回第七步：将羊运过来算法就是解决问题的方法和步骤方法和步骤 一个能被解决的问题，其中都包含着算法一个能被解决的问题，其中都包含着算法 算法是程序设计的算法是程序设计的“灵魂灵魂”，世界著名计算机科学家尼克劳斯，世界著名计算机科学家尼克劳斯沃思（沃思（N Nwirthwirth）指出：算法）指出：算法+ +数据结构数据结构(Data Structure)=(Data Structure)=程序，可见，算法在程序设程序，可见，算

3、法在程序设中具有多么重要的地位。算法独立于任何具体的程序设计语言，一个算法可中具有多么重要的地位。算法独立于任何具体的程序设计语言，一个算法可以用多种程序设计语言来实现。例如，以用多种程序设计语言来实现。例如，“鸡兔同笼问题鸡兔同笼问题”的算法可以用的算法可以用BASICBASIC语言来实现，也可以用语言来实现，也可以用C C语言来实现。语言来实现。 算法的概念算法的概念 算法 那算法都有哪些那算法都有哪些特征特征呢？也就是问题的解决都有哪些特点，我们应该注意呢？也就是问题的解决都有哪些特点，我们应该注意些什么呢？些什么呢？算法的特征 有穷性有穷性：执行有限步，每一部执行时间有限 确定性确定性

4、：每一步都有确切的含义 输入输入：有零个或多个输入 输出输出：至少产生一个输出 可行性可行性：原则上能精确运行，用纸和笔做有限次运算后即可完成 自然语言 用自然语言表达算法，就是把算法的各个步骤，依次用人们熟悉的自然语言表示出来。优点：容易理解缺点：书写较烦、不确定性、对复杂的问题难以表达准确、不能被计算机识别和执行自然语言描述自然语言描述 实践活动二 S1：输入a，b的值，确定方程； S2：若a=0，b0，方程无解，结束； S3：若a=0，b=0，x为任意值，结束； S4：若a不等于0，移项得 ax=-b则x=- b/a，结束。自然语言用自然语言描述求解ax+b=0的过程（注意讨论a，b的情

5、况） 算法的描述方法算法的描述用自然语言描述算法用流程图描述算法用伪代码描述算法 用?描述解方程ax+b=0流程图算法的开始或结束算法的开始或结束输入或输出信息输入或输出信息条件判断条件判断程序框名称功能开始/结束算法的开始或结束输入/输出输入或输出信息处理计算与赋值判断条件判断流程线算法中的流向连接圈表示算法流向出口或入口连接点常用的“流程图”所用的基本符号 流程图 也称为程序框图，它是算法的一种图形化表示方法。优点：形象、直观、容易理解流程图描述流程图描述 描述解方程ax+b=0算法的两种方法流程图 S1：输入a，b的值，确定方程； S2：若a=0，b0，方程无解，结束； S3：若a=0，

6、b=0，x为任意值，结束； S4：若a不等于0，移项得 ax=-b则x=- b/a，结束。自然语言自然语言描述与流程图描述的比较自然语言描述流程图描述直观清晰确定性繁琐程度是否容易修改通俗易懂 伪代码伪代码表示举例伪代码表示举例（1）表示条件判断 （2）表示循环处理 if 条件 then do while 条件 执行语句一 循环处理语句 else loop 执行语句二 end if伪代码描述If a除以2余数为0 then 输出“a为偶数”判断某个数是否偶数ElseElsex= -b/ax= -b/aEnd ifEnd if求解ax+b=0Else 输出“a不是偶数”End if输入正数a输入

7、输入 a , ba , bIf a = 0 thenIf a = 0 thenif b = 0 thenif b = 0 then 输出输出x x为任意值为任意值 elseelse 输出输出x x无实数解无实数解 end ifend if 伪代码 伪代码是介于自然语言和计算机程序语言之间的一种算法描述。优点：简洁、易懂、修改容易缺点：不直观、一旦出现逻辑错误不容易排查伪代码描述伪代码描述描述求解ax+b=0的三种方法输入输入 a , ba , bIf a = 0 thenIf a = 0 then if b = 0 then if b = 0 then 输出输出x x为任意值为任意值 else

8、else 输出输出x x无实数解无实数解 end ifend ifElseElse x= -b/a x= -b/aEnd ifEnd if伪代码描述 S1 S1：输入：输入a a，b b的值，的值，确定方程；确定方程； S2S2：若：若a=0a=0，b0b0，方，方程无解，结束；程无解，结束； S3S3：若：若a=0a=0，b=0b=0，x x为为任意值，结束；任意值，结束； S4S4：若：若a a不等于不等于0 0，移，移项得项得 ax=-bax=-b则则x=- x=- b/ab/a，结束。，结束。自然语言描述流程图描述根据具体的情况选择不同的方法小结特征：特征：有输入 确定性 有穷性 有输出 可行性 算法的描述算法的描述用自然语言描述算法用流程图描述算法用伪代码描述算法算法算法解决问题的方法和步骤 一个问题，可能有多种算法一个问题，可能有多种算法 ，应该通过分，应该通过分析、比较、挑选一种最优的算法。一个好算法必析、比较、挑选一种最优的算法。一个好算法必须用到科学的方法须用到科学的方法 ，应该好好学习各学科处理问，应该好好学习各学科处理问题的科学方法。题的科学方法。