3.4算法及其实现 (3).ppt

3 4算法及其实现 农夫的问题 农夫 狼 山羊和蔬菜过河问题 一个农夫带着一条狼 一头山羊和一篮蔬菜过河 但只有一条小船 并且每次只能让农夫带一样东西过河 农夫在场的情况下一切相安无事 一旦农夫不在 狼会吃羊 羊会吃蔬菜 问聪明的农夫如何解决过河问题 解一 解二 1 农夫带羊过河 2 农夫回来 3 把狼带过河 4 把羊带回来 5 带蔬菜过河 6 农夫回来 7 把羊带过河 1 农夫带羊过河 2 农夫回来 3 带蔬菜过河 4 把羊带回来 5 把狼带过河 6 农夫回来 7 把羊带过河 算法表示解决问题的方法和步骤 算法 algorithm 是解题方法的精确描述 3 4 1算法 算法描述的是一种有穷的动作序列 即算法是由有限个步骤组成的 在算法中 每一步动作的表示形式并没有规定的格式 可以是抽象的 也可是具体的 但是这些动作的含义应当是明确的 即没有二义性 同时还应该是能行的 即在有限时间内可以做到的 对同一个问题 有时可以有不同的解题方法和步骤 有的方法只需要较少的步骤 而有的方法则需要较多的步骤 一般情况下 尽可能采用简单省时的和步骤少的方法去解决问题 因此 为有有效地解决问题不公需要保证算法正确 还要考虑算法的质量 这就要求人们设计或选择合适的算法 以我国著名数学家华罗庚的 泡荼 为例 p67 3 4 2算法和表示 算法的表示形式 自然语言 流程图 flowchart 计算机语言 用汉语或英语这样的自然语言来表示算法 通俗易懂 但通常所用文字会比较冗长 一容易出现 歧义性 流程图是人们经常用来描述算法的工具 流程图用图框和流程线来表示算法 形象直观 美国国家标准化协会 ANSI 规定了流程图符号 流程图中几个常用的基本的符号 1 处理框 框中指出要处理的内容 此框有一个入口和一个出口 2 输入 输出框 用来表示输入和输出数据 3 判断框 用于表示条件判断及产生产生分支的情况 菱形框的四个顶点 通常用上面的顶点表示入口 视需要用其余两个顶点来表示出口 4 连接框 用于连接因页面写不下而断开的流程线 5 流程线 有向线段 控制流程方向 6 开始 结束框 用于本段算法的开始或结束 3 4 3算法的三种模式 1 顺序模式在算法流程中 执行完一个处理步骤step1后 顺序执行紧跟着的下一个步骤step2 一直这样下去 直到遇到其他模式 P69图3 4 3 2 分支模式在算法流程中 往往需要对某个情况e进行判断 当结果为真时 执行yes指向的流程线下的步骤step1 否则执行no指向的流程线下的步骤step2 P70图3 4 4 3 循环模式在算法流程中 对某个情况e进行判断 当结果为真时 执行yes指向的流程线下的步骤step1 然后再次判断情况e 如果结果还为真 则再次执行步骤step1 并继续判断情况e 重复上述过程 直到判断的结果为假 执行no指向的流程线下的其他语句 P70图3 4 5 例如 要设计一个算法 对任意输入的三个整数x y和z 找出并输出其中的最大值 这个算法比较简单 只要先比较x和y 得到一个较大值max 再用max与z比较 将两者中较大的值作为结果输出即可 用自然语言描述如下 1 输入变量x y和z的值 2 比较x和