级C程序设计-第2章.pptVIP

C程序设计,主要内容： 算法概念 算法特性 如何表示算法 结构化程序设计方法 掌握程序流程图画法,第二章:程序的灵魂-算法,1976年Nikiklaus Wirth提出了 程序 = 数据结构 + 算法 的观点。,数据结构：程序中数据的类型和数据的 组织形式。 算法： 解决问题的方法。,算法的概念,也就是说程序设计主要包括两方面的内容：,在这一章中，我们将介绍有关算法的初步知识。,例如，外地的同学开学返校，一般会有下列的步骤：,粗略地说，算法是解决问题的具体步骤。,算法的概念,这其实就是一个算法，通过这个算法的具体步骤解决了开学返校这个“问题”。,首先去买到成都的火车票,然后按时上车,到成都火车站时下车,再坐车到四川大学,简单算法举例,例：求 1 + 2 + 3 + + 1000 的值。,我们可以考虑使用一个其值可以变化的量（称为变量），用它存储变化的数值。 让这个变量的初值是0 ，然后依次地把从1 到n的值累加到这个变量中，于是就可以得到1 + 2 + 3 + + 1000的值。 变量的名字可以任意写 下面是这个算法的具体步骤：,先定义一个“变量”，我们给它取名叫 S 让 S 的值先为 0 把 1 加到 S 这个变量中去 把 2 加到 S 中去 把 1000 加到 S 中去,上面这个算法通过有限的步骤，就解决了问题。,例：求 1+2+3+ 1000 的值。,简单算法举例,例：求 1*2*3* n 的值。,我们可以考虑使用一个值可以变化的量（称为变量），它可以存储变化的数值。 让变量的第一次值是 1 ，然后依次地把 1 到 n 的值乘到这个变量中，就可以得到1*2*3*n 的值。 下面是这个算法的具体步骤：,简单算法举例,先定义一个“变量”，我们随意给它命名为 M 让 M 的值先为 1 把 1 乘到 M 这个变量中去 把 2 乘到 M 中去 把 n 乘到 M 中去,于是就得到一个可以解决该问题的算法。,例：求 1*2*3* n 的值。,简单算法举例,2.3 算法的特性 page 19,一个算法包含的操作步骤应该是有限的，而不能是无限的。另外有穷性也要在合理的范围之内，比如一个需要3000年才能结束的算法，虽然有穷，但超过了合理的限度，也不应把它视作有效算法。,一个算法应该具有以下特性：,有穷性,算法中的每一个步骤都应当是确定的，而不应当是含糊、模棱两可的。也就是说，算法的含义应当是唯一的，而不应当产生“歧义性”。,一个算法应该具有以下特性：,确定性,2.3 算法的特性 page 19,所谓输入是指在执行算法时需要从外界取得必要的信息。例如在执行 1+2+3+ n 的算法时，需要由用户手工输入 n 的值。 一个算法也可以没有输入。比如，只计算12的运算结果。,一个算法应该具有以下特性：,有零个或多个输入,2.3 算法的特性 page 19,算法的目的是为了求解，“解”就是输出。没有输出的算法是没有意义的。 所以，算法必须有输出。,一个算法应该具有以下特性：,有一个或多个输出,2.3 算法的特性 page 19,算法中的每一个步骤都应当能有效地执行，并得到确定的结果。 例如：算法中某一步出现了求负数平方根的运算，则该算法不是个有效算法。,一个算法应该具有以下特性：,有效性,2.3 算法的特性 page 19,2.4 怎样表示一个算法,可以用 自然语言 传统流程图 N-S流程图 来表示算法。,用流程图表示算法 流程图是一种用图形、文字和连线来表示程序的思路和方法的图,流程图 的基本符号,起止框：表示程序的开始和结束,输入/输出框：表示数据的输入输出操作,处理框：表示对数据进行处理,判断框：表示根据条件决定程序走向,箭头：表示程序流向,算法的三种基本结构,算法的基本组成结构有三种：24页 顺序结构、选择结构和循环结构。 任何一个算法，无论其多么简单或多么复杂，都可由这三种结构组合和构造而成。,顺序结构,顺序结构是最简单的结构。执行过程是：按箭头方向，顺序地执行所有的步骤。 右图的算法是一个顺序结构,步骤1,步骤2,三种基本结构,例1:画出程序流程图 用户输入一个数到变量X,计算X2,然后输出运算结果,选择结构,执行过程： 根据条件成立与否，选择某一个分支继续执行。,条件,步骤1,步骤2,成立,不成立,三种基本结构,例2:画出程序流程图 用户输入一个数到变量A，若A是正数，计算并输出A的平方根，否则什么都不做。,例3:画出程序流程图 用户输入一个数到变量X,若X0，Y=X2；若X=0，Y=0。计算并输出Y的值。,例4:画出程序流程图 输入一元二次方程ax2+bx+c=0的三个参数a,b,c,计算并输出方程的根（只计算实根,虚根不用考虑）,循环结构,在某条件成立的情况下，循环地执行某些步骤。当这个条件不成立时，循环就结束了。,三种基本结构,条件,步骤1