语言、算法和程序设计方法.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,For Example：1+3=4,命令：输入1,1,1,命令：输入3,3,3,Write,Write,Read,Read,1,3,4,Out,一条指令的执行过程,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，重复进行第二、三步,程序的逻辑结构,所有程序都由三种结构构成 顺序结构 按命令出现的先后顺序依次执行 分支结构 根据设定的条件来决定程序的执行方向 循环结构 按照设定的条件重复执行一组命令 当型 直到型 流程图,顺序结构,分支结构,X=0,X=5,Y=2*X,循环结构,当型结构 直到型结构,X=0,X=0,三、编写程序代码,编写程序代码 选择合适的编程语言 按照上阶段设计的算法编写代码 选择哪种程序设计语言？ 主要看是否能够完成程序设计任务 编程人员对这个语言的熟悉程度 程序代码的例子 计算 5！ fac=1*2*3*4*5 分别用C语言、VB和Java实现,一个程序代码的例子（C语言）,一个程序代码的例子（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 P I P*I 1 1 1 1 2 2 2 3 6 6 4 24 24 5 120 120 6,用自然语言表示的求5！的算法,第一步：使 P1 第二步：使 I2 第三步：计算 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! 迭代公式 S0=0 a0=1 ai=ai-1*i Si=Si-1+ai,开始 置 S 的初值为0 置 a 的初值为1 置 i 的初值为1 当 i=10, 执行下面操作： 使 a=a*i 使 S=S+a 使 i=i+1 打印出 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步：如果jn，则跳到第3步执行，否则输出 “n是素数” 的信息 算法结束,递归结构,递归指用一个概念本身直接或间接地去定义该概念 把一个或者一类问题分解或分割为一个个更小的问题，然后解决这些小问题 确定递归算法的方法：看这个算法定义中是否包含它本身 递归解决方法 关键-找到递推公式 两个阶段-递推和回推 例子分析 计算 Factorial(n)=n! 递推公式 Factorial(n)=1 n=0 Factorial(n)=n*(n-1)! n0 =n* Factorial(n-1) 递归步骤,排序问题,排序就是按增加或减少的顺序对一组类似的信息重新进行安排的过程 插入排序 选择排序 冒泡排序,以第一个数据作为已排序数据序列，从第二个数据起，将各数据逐个插入到已排序序列中的合适位置，使其继续成为有序数据序列,每次从未排序的数据中选出最小（大）数据，放到已排序数据之后,从第一个数据开始，依次对相邻两个数据比较，当发现它们不合顺序时就进行一次