1.2.2如何描述算法 (2)

1、1.2算法的描述与设计学习目标：1、理解什么是算法，知道算法的多样性；2、学会用自然语言、流程图和伪代码来描述算法；3、能够对设计的算法做出简单的评价。 算法的描述与设计有一个牧羊人带着一头羊,一只狼和一颗大白菜准备过河,他找到一只很小的船,每次只能带一样东西过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，牧羊人应如何过河？现在请同学们来设计一个方案,把3样东西安然无恙的带过河。农夫过河问题 思考：123这个方案总共有多少步？ 哪几步顺序可以颠倒？同学们农夫过河问题解决了，那到底什么是算法？ 过河方案牧羊人过河方案第一步：将羊运过去第二步：人返回第三步：将菜运过去

2、第四步：将羊运过来第五步：将狼运过去第六步：人返回第七步：将羊运过来算法就是解决问题的方法和步骤。 算法是程序设计的“灵魂”，世界著名计算机科学家尼克劳斯沃思（Nwirth）指出：算法+数据结构(Data Structure)=程序，可见，算法在程序设中具有多么重要的地位。算法独立于任何具体的程序设计语言，一个算法可以用多种程序设计语言来实现。 算法的概念 算法 那算法都有哪些特征呢？也就是问题的解决都有哪些特点，我们应该注意些什么呢？算法的特征有穷性：执行有限步，每一步执行时间有限;确定性：每一步都有确切的含义;输入：有零个或多个输入;输出：至少产生一个输出;可行性：原则上能精确运行，用纸和

3、笔做有限次运算后即可完成。如何描述算法算法可以用多种方法来描述1、用自然语言来描述。2、用流程图来描述。3、用伪代码描述算法。利用计算机求解方程：ax2+bx+c=0 (a0) 实例分析：自然语言Step1：输入a、b、c的值Step2：令d为 b2- 4acStep3：如果 d大于或等于0 则输出X1, x1为 ， X2, x2为， 转到step4。 否则输出方程无实数解，转到step4。Step4：结束程序。 自然语言 用自然语言表达算法，就是把算法的各个步骤，依次用人们熟悉的自然语言表示出来。优点：容易理解。缺点：书写较烦、不确定性、对复杂的问题难以表达准确、不能被计算机识别和执行。自然

4、语言描述流程图YN开始输入a,b,c的值d=b2-4*a*cd=0X1=(-b+sqr(d)/(2*a)X2=(-b-sqr(d)/(2*a)输出“此方程无实数解”结束输出x1,x2的值流程图Step1：输入a、b、c的值Step2：令d为 b2- 4acStep3：如果 d大于或等于0 则输出 X1, x1为 ， X2, x2为， 转到step4。 否则输出“方程无实数 解”，转到step4。Step4：结束程序。 自然语言开始输入a,b,c的值d=b2-4*a*cd=0X1=(-b+sqr(d)/(2*a)X2=(-b-sqr(d)/(2*a)输出“此方程无实数解”结束输出x1,x2的值

5、流程图 也称为程序框图，它是算法的一种图形化表示方法。与自然语言描述相比，用流程图描述算法形象、直观、更容易理解。流程图描述 伪代码伪代码描述inputbox(“请输入a,b,c的值”)d=b2-4acIf d=0 then X1=(-b+sqr(d)/(2*a) X2=(-b-sqr(d)/(2*a) 输出 x1, x2的值Else输出“此方程无实数解” 伪代码 伪代码是介于自然语言和计算机程序语言之间的一种算法描述。优点：简洁、易懂、修改容易。缺点：不直观、一旦出现逻辑错误不容易排查。伪代码描述小结特征：有输入 确定性 有穷性 有输出 可行性 算法的描述用自然语言描述算法用流程图描述算法用伪代码描述算法算法解决问题的方法和步骤 一个问题，可能有多种算法 ，应该通过分析、比较、挑选一种最优的算法。一个好算法必须用到科学的方法 ，应该好好学习各学科处理问题的科学方法。课堂练习1.不需要精确计算时，我们可以使用估算的方法。例如，考虑班级外出旅游费用时，如果每人需要21元，则全班48人的费用大约为1000元。计算机会这样解决问题吗，为什么？2.超市苹果进行打折促