算法描述与设计完整版

算法描述(miáoshù)与设计第一页，共十六页。农夫(nóngfū)问题：有一个牧羊人带着一头羊,一只狼和一颗大白菜准备过河,他找到一只很小的船,每次只能带一样东西(dōngxī)过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，牧羊人应如何过河？要求：现在请同学们来设计一个方案,把3样东西(dōngxī)安然无恙的带过河。第二页，共十六页。思考(sīkǎo)：★这个方案总共有多少步？★哪几步顺序可以颠倒？★同学们农夫过河问题解决了，那到底什么(shénme)是算法？第三页，共十六页。过河方案(fāngàn)：第一步：将羊运过去第二步：人返回(fǎnhuí)第三步：将菜运过去第四步：将羊运过来第五步：将狼运过去第六步：人返回第七步：将羊运过来第四页，共十六页。算法(suànfǎ)：概念：算法就是解决问题的方法和步骤

算法是程序设计的“灵魂”，世界著名计算机科学家尼克劳斯·沃思指出：算法+数据结构(DataStructure)=程序，可见，算法在程序设中具有多么(duōme)重要的地位。算法独立于任何具体的程序设计语言，一个算法可以用多种程序设计语言来实现。

那算法都有哪些特征(tèzhēng)呢？也就是问题的解决都有哪些特点，我们应该注意些什么呢？第五页，共十六页。算法(suànfǎ)特征：有穷性：执行有限步，每一步执行时间有限；确定性：每一步都有确切的含义；输入：有零个或多个输入；输出：至少产生一个(yīɡè)输出；可行性：原则上能精确运行，用纸和笔做有限次运算后即可完成。第六页，共十六页。如何(rúhé)描述算法：算法可以用多种方法(fāngfǎ)来描述1、用自然语言来描述(miáoshù)。2、用流程图来描述。3、用伪代码描述算法。第七页，共十六页。课堂(kètáng)实践：韩信点兵问题：

如果每3个人(gèrén)编为一队，那最后剩下2个人；如果每5个人编为一队，那最后剩下3个人；如果每7个人编为一队，最后剩下2个人。请你自己算一下，我有多少士兵？”第八页，共十六页。自然语言描述(miáoshù)：第九页，共十六页。流程图描述(miáoshù)：开始N=1N被3、5、7整除后余数为2、3、2输出N的值N=N+1结束YN第十页，共十六页。任意给定3个正实数，判断以这3个正实数能否(nénɡfǒu)构成三角形。请用流程图描述(miáoshù)下题中的算法：开始输入a，b，ca+b>c,b+c>ac+a>b是否同时成立？结束能构成三角形不能构成三角形否是第十一页，共十六页。自然语言描述(miáoshù)与流程图描述(miáoshù)的比较自然语言描述流程图描述直观清晰确定性繁琐程度是否容易修改通俗易懂第十二页，共十六页。初始化N=1DOIfN整除(zhěngchú)3余2、整除5余3、整除7余2then

输出N的值ExitDOEndIfN=N+1Loop伪代码(dàimǎ)描述：第十三页，共十六页。伪代码(dàimǎ)：优点：简洁、易懂、修改容易，且容易转化(zhuǎnhuà)为程序语言代码。缺点：不直观、一旦出现逻辑错误不容易排查。

伪代码是介于自然语言和计算机程序语言之间的一种算法描述。

它是专业软件开发人员描述算法的一种常用方法。没有(méiyǒu)严格的语法限制，书写格式较自由，一般关键词用英文单词。第十四页，共十六页。小结(xiǎojié)：特征：有输入(shūrù)确定性有穷性有输出可行性算法的描述用自然语言描述算法用流程图描述算法用伪代码描述算法算法(suànfǎ)——解决问题的方法和步骤

一个问题，可能有多种算法，应该通过分析、比较、挑选一种最优的算法。一个好算法必须用到科学的方法，应该好好学习各学科处理问题的科学方法。第十五页，共十六页。内容(nèiróng)总结算法描述与设计。算法独立于任何具体的程序设计语言，一个算法可以用多种程序设计语言来实现。有穷性：执行有限步，每一步(yībù)执行时间有限。输入：有零个或多个输入。输出：至少产生一个输出。如果每3个人编为一队，那最后剩下2个人。如