算法的描述与设计

算法的描述与设计当前1页，总共19页。学习目标：1、理解什么是算法，知道算法的多样性；2、学会用自然语言、流程图和伪代码来描述算法；3、能够对设计的算法做出简单的评价。当前2页，总共19页。

算法的描述与设计

有一个牧羊人带着一头羊,一只狼和一颗大白菜准备过河,他找到一只很小的船,每次只能带一样东西过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，牧羊人应如何过河？

要求：现在请同学们来设计一个方案,把3样东西安然无恙的带过河。农夫问题当前3页，总共19页。

思考：123这个方案总共有多少步？

哪几步顺序可以颠倒？同学们农夫过河问题解决了，那到底什么是算法？当前4页，总共19页。

过河方案牧

羊

人

过

河

方

案第一步：将羊运过去第二步：人返回第三步：将菜运过去第四步：将羊运过来第五步：将狼运过去第六步：人返回第七步：将羊运过来当前5页，总共19页。算法就是解决问题的方法和步骤。

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

算法的概念

算法

那算法都有哪些特征呢？也就是问题的解决都有哪些特点，我们应该注意些什么呢？当前6页，总共19页。算法的特征有穷性：执行有限步，每一步执行时间有限;确定性：每一步都有确切的含义;输入：有零个或多个输入;输出：至少产生一个输出;可行性：原则上能精确运行，用纸和笔做有限次运算后即可完成。当前7页，总共19页。如何描述算法算法可以用多种方法来描述1、用自然语言来描述。2、用流程图来描述。3、用伪代码描述算法。当前8页，总共19页。

实践活动：韩信点兵问题:“今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何？”当前9页，总共19页。

实践活动：自

然

语

言用自然语言描述“韩信点兵问题”

:当前10页，总共19页。

自然语言

用自然语言表达算法，就是把算法的各个步骤，依次用人们熟悉的自然语言表示出来。优点：容易理解。缺点：书写较烦、不确定性、对复杂的问题难以表达准确、不能被计算机识别和执行。自然语言描述当前11页，总共19页。流程图流程图当前12页，总共19页。

流程图

也称为程序框图，它是算法的一种图形化表示方法。流程图描述当前13页，总共19页。

描述“韩信点兵”算法的两种方法流程图

S1：将N初始值赋值为1；

S2：若N被3、5、7整除后的余数分别为2、3、2，则输出N的值，转S4；

S3：将N的值加1，转S2；

S4：结束程序。自然语言当前14页，总共19页。

伪代码伪代码描述初始化N=1DOIfN整除3余2、整除5余3、整除7余2then

输出N的值ExitDOEndIfN=N+1Loop当前15页，总共19页。伪代码描述Ifa除以2余数为0then

输出“a为偶数”判断某个数是否偶数Else x=-b/aEndif

求解ax+b=0Else

输出“a不是偶数”Endif输入正数a输入a,bIfa=0thenifb=0then

输出x为任意值else

输出x无实数解

endif当前16页，总共19页。

伪代码

伪代码是介于自然语言和计算机程序语言之间的一种算法描述。优点：简洁、易懂、修改容易。缺点：不直观、一旦出现逻辑错误不容易排查。伪代码描述当前17页，总共19页。小结特征：有输入确定性有穷性有输出可行性算法的描述用自然语言描述算法用流程图描述算法用伪代码描述算法算法——解决问题的方法和步骤

一个问题，可能有多种算法，应该通过分析、比较、挑选一种