07高级程序语言.ppt

1、1,第七讲 程序的灵魂-算法,教材:C程序设计导论,2,本讲重点,1.了解算法的重要性，掌握算法的概念。 2.掌握算法的表示方法。 3.理解什么是结构化程序设计方法。 4.软件测试的一般方法。,3,如何理解程序？,著名计算机科学家沃思(Nikiklaus Wirth)提出一个公式：数据结构算法程序 考虑其他要素： 程序算法数据结构程序设计方法语言工具和环境 算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。 算法是解决“做什么”和“怎么做”的问题。程序中的操作语句，实际上就是算法的体现。,4,编程过程,编程目的 解决问题，问题的解决是一个复杂的过程。 算法 解决问题所使用的一

2、系列合乎逻辑的、简洁的步骤。 解决问题包含的步骤： 分析问题，找出解决问题的模型。 根据模型设计出适合计算机特点的处理方法，即算法。 选择适合的计算机语言进行编程，以实现算法。 上机编辑、调试、运行所编制的程序，得到结果。 对结果进行分析，整理出文字材料，即文档。,5,编程过程,例：预定火车票的算法： 旅客输入如姓名，车次，路程起点，终点，日期等信息。 然后将订票单交到订票处。 柜台工作人员查看是否有座位。 如果存在满足要求的有效座位，就给旅客一张确认车票。 否则，发给一张等待单。 如果有其他人退票，可凭等待单换取车票。 如果最终乘客没有订到车票，将得到退款。,6,算法的分类,数值数据运算的算

3、法 如求积分，微分，高阶方程的解等 非数值数据运算的算法 如情报检索，事务处理，数据管理等 在计算机应用方面，非数值运算的应用 大大多于数值运算的应用。,7,算法的特点,有穷性：一个算法应包含有限个操作步骤。 确定性：每个步骤的含义都是确定的。 有输入：有0个或多个输入。 有输出：有1个或多个输出。 有效性：每个步骤都能被有效地执行。,8,算法的描述,1.自然语言：用自然语言给出解决问题的详细步骤，如前面的预定火车票的例子。 2.流程图：用图框表示。 3.伪代码：使用介于自然语言和计算机语言之间的文字、符号来描述算法。 4.计算机语言：采用这种方法必须严格遵守所使用的语言的语法规则。,9,算法

4、的描述自然语言,例4.1 判断一个数m是否为素数 分析：判断整数m（m2）是否为素数的方法是：如果m不能被i整除（i为2到m-1的所有整数），则m是素数。 算法如下： S1. 输入m的值； S2. i赋初值为2； S3. 判断m能否被i整除，若能，转到S6； S4. 若m不为被i整除，给i的值加1，若im，则转到S3； S5. 若i=m，输出m“是素数”，转到S7； S6. 输出m“不是素数”； S7. 算法结束。,10,算法的描述流程图,以图解方式说明实现一个解决方案所需要完成的一系列操作。 为了达到下列目的： 一目了然，比文字描述易懂。 程序可以很容易地查看和修改。 提供有效的程序文档。

5、解释程序和讨论解决方案变得容易。 流程图分类：传统流程图，N-S流程图，PAD图。,11,传统流程图里常用的符号,开始或结束框 “处理框”-运算步骤 输入或输出框 判断框 连接符：一个程序中两个部分之间 的连接程序的流程线 注释,12,例4.2 判断一个数m是否为素数的传统流程图,13,传统流程图里的符号连接符,在为复杂问题准备流程图时， 流程图可能无法放在同一页中， 要将所有的图块直接连接起来比较困难。 流程图可以被分割成若干部分。 连接符可以用于指定连接的位置。 在连接符中指定了一个唯一的数。 在图表断开的地方，一个箭头指示了那一点。,14,传统流程图里的符号连接符,15,流程图的一些提示

6、,画流程图时应该记住的一些要点： 开始应该把注意力集中在问题的逻辑上，画出流程图的主路径。 完成主路径后，加上分支和循环。 一个流程图只能含有一个起始点和一个结束点。 使流程图保持独立，只要可能，就不要用与计算机有关的术语。 没有必要在流程图中画出程序的每个步骤。 使用描述性的术语来表现问题的逻辑结构。 不要用模棱两可的词语。 让其他编程人员或用户能够轻松看懂你的流程图。,16,N-S流程图,N-S流程图 N-S流程图于1973年由美国学者I.Nassi和 B.Shneiderman提出，基本结构是矩形框。,顺序结构,分支结构,17,N-S流程图,当形循环,直到形循环,18,判断一个数m是否为

7、素数的NS流程图,19,PAD流程图,(a)顺序结构 (b)选择结构 (c)循环结构 PAD图的基本符号,1973年由日立公司提出，用二维树形结构表示程序控制流。,20,算法的描述伪代码,伪代码（Pseudo Code）是用介于自然语言与计算机语言之间的文字和符号来描述算法。 无固定的、严格的语法规则，如同一篇文章，自上而下地写下来。可以用自然语言，也可以用程序设计语言，或者使用自然语言与程序设计语言的混合体。 伪代码书写方便，格式紧凑，也比较好懂，便于向计算机语言过渡。,21,伪代码描述,例4.3 求5！即1*2*3*4*5 开始 置t的初值为1 置i的初值为2 当i5，执行循环 使t=t*

8、i 使i=i+1 打印t的值 结束,也可以写成以下形式： BEGIN 1t 2i while i=5 t*it i+1i print t END,22,算法的描述计算机语言,例4.4 判断一个数m是否为素数 #include void main(void) int m,w,i; printf(“input m:n”); scanf(“%d”, ,23,结构化程序设计方法,自顶向下 逐步细化 模块化设计 结构化编码 结构化程序设计方法举例：,24,求1n之间素数的另一种方法（筛选法）: （1）先将1挖掉，因为1不是素数； （2）用2去除它后面的各个数，把2的倍数挖掉（置0）； （3）依次用3,4

9、,5, 作为除数去除这些数以后的各数，并将倍数挖掉。,25,求素数续:,26,求素数续:,27,求素数续:,28,求素数续:,29,求素数续:,30,算法的时间复杂度,在计算机上执行算法所耗费的时间和所占用的空间，是对算法进行评价和选择的依据。 时间复杂度：撇开与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模，或者说它是问题规模的函数。 常从算法中选取一种与求解问题相关的基本操作，以该基本操作的重复执行次数作为算法时间量度的依据，如时间复杂度在n级，n的平方级，n的立方级，n的指数级等。,31,算法的空间复杂度,空间复杂度：作为算法所需存储空间的量度。

10、 存储空间指算法所处理的数据所需的存储空间与算法操作所需的辅助空间之和。 设n为问题规模的大小，f（n）为存储空间，空间复杂度是以f（n）为变量的函数。类似地，也有n级，n的平方级，n的立方级，n的指数级等区分。,32,例4.5 求一元人民币兑换成1分、2分、5分共有多少种方法。 分析：若5分、2分、1分的个数分别为i个、j个、k个。则i的取值为020，j的取值为050，k的取值为0100，于是有方程5i2jk100。 程序如下： #include void main(void ) int i,j,k,m=0; for(i=0;i21;i+) for(j=0;j51;j+) for( k=0;

11、k101;k+) if(5*i+2*j+k=100)m+=1; printf(“m=%dn”,m); ,循环次数：21*51*101,33,例4.6 求一元人民币兑换成1分、2分、5分共有多少种方法。 改进后的程序如下： #include void main(void) int i,j,m=0; for(i=0;i21;i+) for (j=0;j(100-5*i)/2;j+) m+=1; printf(“m=%dn”,m); ,循环次数：,34,软件测试,软件测试的目的：找出软件开发过程中的错误。测试的目的不是为了证明程序的正确性，而是“假定程序中存在错误”，要通过测试的方法发现尽可能多的错

12、误。 软件测试的原则： 侧试用例应由输入数据和预期的输出数据两部分组成。 测试用例不仅要选用合理的输入数据，还要选择不合理的输入数据。 除了检查程序是否做完了它应做的事之外，还要检查它是否做了不应做的事。 软件测试方法：白盒法，黑盒法。,35,软件测试-白盒法,白盒法又称逻辑覆盖法，要求测试者必须对程序内部结构 和处理过程非常清楚。 1、语句覆盖法：使程序的每一条语句都能执行一次。 例4.7 有以下的程序#include void main(void)float a,b,c; scanf(“%f%f%f”,选择a=4、 b=2、c=3,36,软件测试-白盒法,2、判定覆盖判定覆盖又称分支覆盖，

13、是指选择足够多的测试用例，使每个判定的可能的结果（“真”或“假”）都能执行一次，也就是说，程序中的每一个分支都至少执行一次。例 4.7 有以下的程序#include void main(void)float a,b,c; scanf(“%f%f%f”,a=2、b=2、c=1（使表达式a0 scanf(“%f%f%f”,有四个条件：a0 b=2 a=4 c1 因此可以选择：a=4、b=2、c=4a=0、b=1、c=1,38,软件测试-白盒法,4、判定/条件覆盖同时满足判定覆盖和条件覆盖就是判定/条件覆盖。例 4.7 有以下的程序#include void main(void)float a,b,

14、c; scanf(“%f%f%f”,a=4、b=2、c=4a=0、b=1、c=1,39,软件测试-白盒法,5、条件组合覆盖条件组合覆盖指选取足够多的测试用例，使得每个判定中的每个条件的各种可能组合都至少出现一次。例 4.7 有以下的程序#include void main(void)float a,b,c; scanf(“%f%f%f”,a0&b=2、a0&b!=2、 a1、a=4|c1、a!=4|c=1。,a=4、b=2、c=4（针对，组合）a=4、b=1、c=1（针对，组合）a=0、b=2、c=2（针对，组合）a=0、b=1、c=1（针对，组合）,40,软件测试黑盒法,黑盒测试是将程序看成一个黑盒子，只在程序接口上进行测试，主要看软件是否能完成功能要求。因此黑盒测试也称为功能测试。 1、等价分类法 例4.8 测试编写的一个计算sqrt(x-4)/(6-x)的程序。分析： 将该程序的输入数据分为三个有效等价类（划分等价类很大程度上是试探性的）：x4、x=4，以及三个无效等价类：x6、x=6、x4。 首先应该选取尽可能多包含有效等价类的测试用例，如x=5，4包括全部三个有效等价类；其次选择多个测试用例包括全部无效等价类，如x=7，6，3。 所以，可以选取x=3，4，5，6