第2章算法.ppt

第第2 2章章 程序的灵魂程序的灵魂 算法算法本章要点：了解算法的基本概念掌握C程序的基本结构能用流程图描述简单的算法2.1 2.1 算法的基本概念算法的基本概念 一般地，一个程序应包含两个方面的内容：对数据的描述：数据类型和数据的组织形式，即数据结构对操作的描述：即操作步骤，也就是算法算法(algorithm)是对特定问题求解步骤的一种描述。程序=算法+数据结构例：例：求求 1+2+3+100 1+2+3+100 的和的和p用逐项求和方法p用等差数列的求和公式p2.2 2.2 算法的特性算法的特性p有穷性：一个算法必须在执行有穷步之后结束。p确定性：算法的每一步必须是确切定义的。对于相同输入必须得到相同结果。p有效性：算法的每一步都是能够实现的，即可操作的。例如，若b=0,则a/b是不能有效执行p输入：算法有零个或多个输入。p有输出：算法执行完毕，必须有一个或若干个输出结果。2.3 2.3 怎样描述算法怎样描述算法 用自然语言描述算法 用流程图表示算法,常用流程图符号有:起止框输入/输出框判断框处理框流程线例：已知圆柱体的半径是6，高是7，求圆柱体的体积。rh开始给r,h赋值用s=*r2计算底面积用v=s*h计算圆柱体积输出体积v终止 用N-S流程图表示算法给 r,h 赋值用s=*r2计算底面积用v=s*h计算圆柱体积输出体积v 用伪代码表示算法 用计算机语言表示算法算法的组成（操作和控制结构）操作（运算）控制结构：控制算法中各个操作的执行顺序。顺序结构（顺序执行）选择结构（比较判断）循环结构（反复执行）条件条件A AB B真真假假选择结构传统流程图条件条件真真 假假A B选择结构N-S流程图例：输入三个不等的数x、y、z，输出最大的数输入 x,y,zx=y真假max=xmax=ymax=z真假max=z输出 max条件A假假真真当条件为真A条件A假假真真A当条件为真循环结构传统流程图循环结构N-S流程图1=i,0=sumi100sum+i=sumi+1=i假假真真例：求 1+2+3+100 的和开始输出sum终止1=i,0=sum输出sumi100sum+i=sumi+1=i例 求 1-1/2+1/3 1/4+1/99 1/100。0=sum,1=i,1=signi100sum+sign/i=sum-sign=sign,i+1=i假假真真开始输出sum终止本章内容十分重要，是学习后面各章的基础。学习程序设计的目的不只是学习一种特定的语言，而是学习进行程序设计的一般方法。掌握了算法就是掌握了程序设计的灵魂，再学习有关的计算机语言知识，就能够顺利地编写出任何一种语言的程序。脱离具体的语言去学习程序设计是困难的。但是，学习语言只是为了设计程序，它本身决不是目的。千万不能拘泥于一种具体的语言，而应能举一反三。如前所述，关键是设计算法。有了正确的算法，用任何语言进行编码都不应当有什么困难。在本章中只是初步介绍了有关算法的知识，并没有深入介绍如何设计各种类型的算法。我们将在以后各章中结合程序实例陆续介绍有关算法。