(
课件网) 第二节 算法描述与设计 有一个牧羊人带着一只羊,一匹狼和一颗大白菜准备过河,他找到一只很小的船,每次只能带一样东西过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，牧羊人应如何过河？ 过河的方案: 第一步：人和羊过河，人返回，留下羊； 第二步：人和狼过河，人和羊返回，留下狼； 第三步：人和菜过河，人返回，留下菜； 第四步：人和羊过河。 算法的概念：我们解决问题都需要遵循一定的方法和思路并正确的列出各个求解步骤。算法就是解决问题的方法和步骤。 总结： 我们看人在解决问题时，要先对问题进行分析思考，然后确定解决问题的方法和步骤，这种解决问题的方法和步骤就称为算法。 算法是“灵魂” 1.算法存在于人们生活中，如：上街购物、顾客付款、营业员找银等。 2.刷牙的步骤：拿牙刷，挤牙膏，接水，刷牙，清理泡沫等。 3.算法是尼克劳斯.沃斯（N.Writh）提出的，他指出：算法+数据结构=程序。 （即算法不能单独构成程序，它必须和数据结构合二为一） 算法的特征 有穷性：执行有限步，每一部执行时间有限 确定性：每一步都有确切的含义 输入：有零个或多个输入 输出：至少产生一个输出 可行性：原则上能精确运行，用纸和笔做有限次运算后即可完成 如何描述算法 算法可以用多种方法来描述 1、用自然语言来描述。 2、用流程图来描述。 3、用伪代码描述算法。 1、用自然语言来描述算法。 什么是自然语言。 人们日常生活中使用的语言 用自然语言表达算法，就是把算法的各个步骤，依次用人们熟悉的自然语言表示出来。 例如： 人大代表去化验科，护士指着前方一牌说：“非本科人员不得入内！”那人大怒“我就化验个血，还要本科文凭！” 自然语言 自然语言描述 第一步：移项得 ax = - b; 第二步：若a不等于0，则x=-b/a，结束; 第三步：若a=0，b=0，得x为任意值，结束； 第四步：否则输出x无实数解，结束； 例：求方程 ax + b = 0 的解。 自然语言的优缺点 优点：通俗易懂，容易理解 缺点：书写较烦、不确定性、对复杂的问题难以表达准确，有时候还有歧义，不能被计算机识别和执行 2、用流程图来描述算法。 什么是流程图？（也称程序框图）它是算法的一种图形化表示方法。 常用的“流程图”所用的基本符号 程序框 名称 功能 开始/结束 算法的开始和结束 输入/输出 输入和输出信息 处理 计算与赋值 判断 条件判断 流程线 算法中的流向 连接圈 表示算法流向出口或入口连接点 流程图 例：求方程 ax + b = 0 的解。 优点：形象、直观、容易理解 3.用伪代码描述算法 伪代码是介于自然语言和计算机程序语言之间的一种算法描述。 伪代码是一种怎样的算法描述？ 输入 a , b If a = 0 then if b = 0 then 输出x为任意值 else 输出x无实数解 end if Else x= -b/a End if 伪代码描述 例：求方程 ax + b = 0 的解。 使用伪代码描述算法没有严格的语法限制，书写格式也比较自由，只要把意思表达清楚就可以了，它更侧重于对算法本身的描述。 在伪代码描述中，表示关键词的语句一般用英文单词，其他语句可以用英文语句，也可以用汉语语句。 伪代码的优缺点： 用伪代码描述的算法简洁、易懂，修改起来也比较容易，并且很容易转化为程序语言代码。 优点：简洁、易懂、修改容易 缺点：不直观、错误不容易排查 三种描述算法的比较 三种描述算法的比较 自然语言 优点 通俗易懂 缺点 冗长，繁锁，缺乏直观性 简洁性，容易产生歧义 流程图 优点 形象、直观、更容易理解 缺点 需要一定数学知识 伪代码 优点 简洁、易懂，修改起来比较容易，易转为程序语言代码 缺点 没有流程图直观，出现错误不便排查 小结 什么是算法？ 解决问题 ... ...
