语言、算法和程序设计方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,6,章,语言、算法和程序设计方法,6.1,从算法到程序再到软件,6.2,程序和指令,6.3,程序的程序：翻译系统,6.4,程序设计语言,6.5,怎样编写程序,6.6,算法,6.7,*,数据表达和数据结构,6.8,*,软件工程简介,6.9,*,职业：软件工程师,从算法到程序再到软件,计算机完成各种,不同的任务,，需要,不同的软件,软件开发,算法,程序,软件,程序设计,是软件开发的一部分,程序设计分解为几个步骤,程序设计需要使用程序设计语言,算法设计,软件开发,的任务之一,选择一种,语言,使用这个语言,编写,完成操作任务的,代码,程序设计,软件开发的核心工作是算法设计,算法,一项工作如何被完成的步骤,数学问题,寻找如何解决特定问题的方法,一个著名的算法,欧几里德算法,：,求两个正整数,A,和,B,的最大公约数,如：,9,、,6,的最大公约数是,3,第一步：比较,A,和,B,这两个数，将,A,设置为较大的数，,B,设置,为较小的数；,第二步：,A,除以,B,，,得到余数,C,；,第三步：如果,C,等于,0,，则最大公约数就是,B,；,否则将,B,赋值给,A,，,C,赋值给,B,，,重复进行第二、三步,从算法到程序再到软件,A B C,9 6 3,6 3 0,3,图灵理论,只要能被分解为有限步骤的问题就可以被计算机执行,有限的步骤,能够将这些步骤设计为计算机所执行的程序,程序设计中，首先寻找算法，算法找到后，实现算法的步骤,算法的描述,使用某种计算机语言,不同的计算机语言对一个算法具有不同的实现方法,算法是程序设计的基础,从算法到程序再到软件,程序和指令,程序,program,计算机,执行,某种,任务,的一系列,操作步骤,的,总和,一组计算机指令的有序集合,指令,instruction,控制计算机,执行,各种基本操作的,命令,指令是计算机执行的最基本操作,如：处理器从内存中读取一个数据,二进制的算术运算加、减、乘、除,逻辑判断等,处理器能执行的,二进制代码,程序和指令,指令作为计算机软件和硬件的接口,指令在处理器中,以逻辑电路实现,软件,硬件,指令,指令系统,一个,CPU,能够执行的所有指令,指令的主要类型,数据传输类,将数据从一个地方,(,源,),传输到另外一个地方,(,目的,),一种是在,CPU,内部、存储器内部、,CPU,和存储器之间进行,一种是在,CPU,和外设（外设接口）之间进行,的,算术逻辑运算类,控制操作类,有条件转移、无条件转移,翻译系统,基本概念,源程序,用各种语言编写的程序,目标程序,源程序经过翻译，成为机器可执行的机器语言程序,库文件,由一些标准子程序,(,函数和过程,),及常用的应用程序块组成的文件,可执行程序,目标程序与库文件连接后形成的程序,程序的整个处理过程,翻译,和库文件,连接,装入,源程序,目标程序,可执行程序,执行,翻译系统,语言处理系统，,翻译计算机程序,任务是把,非机器语言,编写的,源程序,翻译,成,目标程序,是系统软件,不同编程语言的翻译系统是不同的,分类,汇编程序,编译程序,解释程序,逐条翻译并执行源程序的语句，不生成可执行文件,把源程序代码一次性翻译成目标程序代码，最终生成可执行文件,把汇编语言源程序翻译为机器语言程序,编译系统的结构和工作过程,词法分析程序,语法分析程序,中间代码生成程序,优化程序,目标代码生成程序,目标程序,源程序,If x=0 Then y=1 Else y=-1,程序设计语言,发展阶段,机器语言,低,级,语言,汇编语言,中,级,语言,面向过程的,高级,语言,面向对象,的,高级,语言,机器语言和指令,机器语言,计算机能直接执行的程序设计语言,二进制语言,，用二进制机器指令来编写程序,机器指令的信息,操作类型,操作数或操作数的地址（操作数的存储位置）,操作结果的存储位置,下一条指令的地址信息,指令格式,操作码,操作数或地址码,下一条指令的地址,机器语言和指令,指令的例子：,数,1,和,3,的相加,指令,10000000 00000001 00000011,“,加,”,操作码,Number1,：,1 Number 2,：,3,实现过程,用计算器,计算机,程序,过程,指令执行过程,特点,既简单又难,执行速度最快,面向机器，兼容性差，移植性差,最低级语言,计算器的工作原理,用,VB,设计的加法程序,Private Sub Command1_Click(),Dim A As Integer,B As Integer,S As Integer,A=,Val(InputBox,(,请输入第一个数,),B=,Val(InputBox,(,请输入第二个数,),S=A+B,Print A;+;B;=;S,End Sub,Memory,Input,Output,控制器,ALU,For Example,：,1+3=4,命令：输入,1,1,1,命令：输入,3,3,3,Write,Write,Read,Read,1,3,4,Out,Add,+,一条指令的执行过程,1.,取操作码,2.,内部译码,3.,取第一个数,4.,取第二个数,5.ALU,完成加,6.,保存结果,7.,取下一条指令,汇编语言,机器语言的“,符号化,”,用容易记忆的文字符号,(,助记符,),表示指令中的操作码和地址码,指令格式,助记符 符号地址,例：加法语句,ADD,A,，,B,特点,机器不能直接识别,可读性好,面向机器，兼容性差，移植性差,中级语言,高级语言,与机器,完全独立的语言,，描述解题过程,语法与自然语言接近,特点,面向问题，通用，可移植,分类,面向过程,BASIC,C,PASCAL,FORTRAN,COBOL,Ada,面向对象,Visual Basic,C+,JAVA,Delphi,Power Build,面向对象程序设计,程序的基本成分,对象,是具有特殊,属性,(,数据,),和,方法,(,行为、操作,),的,实体,特点,封装性,继承性,多态性,把对象的属性和操作结合在一起，构成一个独立的对象,子类可以拥有父类的属性和行为,基类中定义的属性和行为被子类继承后，可以具有不同的数据类型或不同的行为,*其它语言,函数型语言,LISP,Scheme,说明性语言,逻辑语言，用于根据逻辑推理的原则回答问题,Prolog,超文本链接标记语言,(HTML),由一种格式标记和超链接组成的“伪语言”，主要用于网络上的信息服务,XML,可扩展标记语言,其它语言,如,SQL,*,基于组件的程序设计,基于组件的程序设计是微软提出的思想,COM,（,Component Object Model,，,组件对象模型）,组件技术属于面向对象的程序设计技术,使用,COM,技术，一个新的应用系统的开发不必按照传统的方法进行所有代码的编写，可以通过组件进行“组装”软件,对于提高开发速度、降低开发成本、增加应用软件的灵活性、降低软件维护费用很有帮助,软件开发技术的主流方向,程序设计语言的发展历史,怎样编写程序,程序设计是一个系统过程,不是简单的编写程序代码,一般可以分为,六个步骤,问题的定义（程序说明）,设计解决问题的方案,编写程序代码,进行程序测试,编写程序的文档,程序应用（程序运行与维护）,一、理解问题：程序说明,程序设计中最重要的部分,是对问题的描述,设计一个程序是为了解决某个特定的问题,分析特定问题，决定,应该做什么，如何做,系统分析员,主要弄清以下问题：,程序的目标是什么？即程序需要解决什么样的问题,可能需要输入哪些数据？,数据具体的处理过程和要求是什么？,程序可能产生的数据输出以及输出形式是什么？,示例,1,示例,2,二、设计解决问题的方案,对要解决的问题设计出具体的解决方案,确定,程序的逻辑结构,关键,设计算法,例,：,欧几里德算法,求两个正整数,A,和,B,的最大公约数,第一步：比较,A,和,B,这两个数，将,A,设置为较大的数，,B,设置为较小的数；,第二步：,A,除以,B,，得到余数,C,；,第三步：如果,C,等于,0,，则最大公约数就是,B,；,否则将,B,赋值给,A,，,C,赋值给,B,，,重复进行第二、三步,程序的逻辑结构,所有程序都由三种结构构成,顺序结构,按命令出现的先后顺序依次执行,分支结构,根据设定的条件来决定程序的执行方向,循环结构,按照设定的条件重复执行一组命令,当型,直到型,流程图,顺序结构,A,B,分支结构,X=0,X=5,Y=2*X,循环结构,当型结构,直到型结构,X=0,X=0,三、编写程序代码,编写程序代码,选择合适的编程语言,按照上阶段设计的算法编写代码,选择哪种程序设计语言？,主要看是否能够完成程序设计任务,编程人员对这个语言的熟悉程度,程序代码的例子,计算,5,！,fac,=1*2*3*4*5,分别用,C,语言、,VB,和,Java,实现,一个程序代码的例子（,C,语言）,计算,5,！,#include/*,C,语言编译系统的库函数,*,/,main()/*,程序开始,*,/,int,i,fac,;/*,定义变量,*,/,fac,=1;/*,变量,fac,被赋值,1,*/,for(i=2;i=5;i+),/*,从,2,到,5,，循环执行乘法得到,5,的阶乘,*,/,fac,=,fac,*i;,printf(,the,5!=%d,fac,),；/*,输出结果,*,/,一个程序代码的例子（,VB,语言）,Dim i As Integer,fac,As Integer,定义,i,、,fac,为整型数变量,fac,=1,变量,fac,赋值,1,For i=2 To 5 Step 1,循环，从,2,到,5,，每次步长为,1,fac,=,fac,*i,计算,5,的阶乘,Next i,next,和,for,构成循环体,Print,fac,=,;,fac,输出阶乘结果,计算,5,！,一个程序代码的例子（,Java,语言）,public class Factorial,public static void main(String,args,),int,i=1;/,循环控制变量,double,fac,=1;/,存放结果的变量，注意类型,while(i=5),fac,=,fac,*i;/,循环体,i=i+1;,System.out.println(5!=+,fac,);/,输出结果,计算,5,！,四、,寻找错误：程序测试,调试程序，找出程序中的错误,语法错误,违反编程语言的语法规则,逻辑错误,程序得到的结果不对,需用大量数据测试,测试方法,黑盒测试,例,：加法程序,白盒测试,专业测试，使用一组特意设计的数据测试,五、编写程序文档,对前面所做的各种设计形成完整的手册,设计过程中形成的文档,流程图,变量列表,程序代码,运行结果等,供日后程序的维护、升级使用,设计完成后的使用手册,程序的功能,操作说明,六、运行与维护,培训用户,程序的安装、设置等,程序进行修改甚至升级,算 法,算法,是一组,明确,的、,可以执行,的步骤的,有序,集合,就是为了解决问题而采用的方法和步骤,算法分类,数值运算算法,非数值运算算法,算法特性,确定性,有穷性,有效性,可有零个或多个输入,有一个或多个输出,算法的表示方法,自然语言,流程图,伪代码,PAD,图（问题分析图）,例：,求,5,！的算法,*,用自然语言描述,*,用伪代码表示,用流程图表示,P=1*2*3*4*5,P=P*I,PIP*I,11,1,1,2,2,2,3,6,6,4,24,24,5,120,120,6,用,自然语言,表示的求,5,！的算法,第一步：使,P,1,第二步：使,I,2,第三步：计算,P*I,，,乘积仍放在,P,中,第四步：使,I,的值加,1,再放到,I,中,第五步：如果,I,不大于,5,，返回重新执行第三 步及其后的步骤，否则执行第六步,第六步：打印出,P,的值，算法结束,开始,置,P,的初值为,1,置,I,的初值为,2,当,I=5,执行下面循环操作：,使,P=P*I,使,I=I+1,(,循环体到此结束,),打印出,P,的值,结束,用,伪代码,表示的求,5,！的算法,用,流程图,表示求,5,！的算法,P,算法设计,程序设计有两个阶段,第一是,设计算法,第二是,实现算法,解决问题的基本原理,(4,个步骤,),1.,理解问题,2.,设计一个解决问题的方案,3.,执行这个方案,4.,检验这个方案,*常用的算法结构,迭代结构,递归结构,排序问题,查找问题,迭代结构,不断用变量的,旧值,递推出,新值,的过程,进行数值计算,建立在循环基础上的算法,关键,-,找到,迭代公式,例子分析,欧几里德算法,计算,S=1!+2!+3!+10!,迭代公式,S,0,=0,a,0,=1,a,i,=a,i-1,*i,S,i,=S,i-1,+a,i,开始,置,S,的初值为,0,置,a,的初值为,1,置,i,的初值为,1,当,i=10,执行下面操作：,使,a=a*i,使,S=S+a,使,i=i1,打印出,S,的值,结束,例子分析,判断一个整数是否为素数,素数是指只能被,1,和它本身整除的数,判断方法：,用,2,到,(n-1),的,各个整数轮流去除,n,，如果都不能,整除，则,n,是素数。,算法：,第,1,步：输入,n,的值,第,2,步：,j=2(,准备用,j,去除,n),第,3,步：,n,被,j,除，得到余数,a,第,4,步：,如,a=0,，表示,n,能被,j,整除，输出信息 “,n,不是素数,”，算法结束；否则就是,n,不能被,j,整除，进入下一步；,第,5,步：将,j,加,1,送回给,j,第,6,步：,如果,j0,=n*,Factorial(n-1),递归步骤,排序问题,排序就是,按增加或减少的顺序,对一组类似的信息,重新进行安排,的过程,插入排序,选择排序,冒泡排序,以第一个数据作为已排序数据序列，从第二个数据起，将各数据逐个插入到已排序序列中的合适位置，使其继续成为有序数据序列,每次从未排序的数据中选出最小（大）数据，放到已排序数据之后,从第一个数据开始，依次对相邻两个数据比较，当发现它们不合顺序时就进行一次交换，直到所有数据都有序为止,例：对以下数据按从小到大的顺序排列,5,，,4,，,9,，,2,，,7,排序问题,迭代的延续应用,n,个数据元素的列表进行排序，最多需要,n,-,1,排序问题,查找问题,把一个特定的数从列表中找到，并提供它所在的位置,顺序查找,折半查找,(,二分法,),从列表的第一个数据开始顺序查找，直到找到所要找的数据或搜索完所有数据,首先测试中间那个数据，如果它大于查找关键字，则再测试前半部分中间那个数据，否则测试后半部分中间那个数据，不断重复这个过程，直到找到了一个匹配项或所有元素都被测试遍了,例：从以下数据中找出数,20,的位置,5,，,6,，,10,，,17,，,20,，,24,，,30,数据必须有序,