软件技术专题-课件

《软件技术专题-课件》由会员分享，可在线阅读，更多相关《软件技术专题-课件（75页珍藏版）》请在金锄头文库上搜索。

1、软件技术基础,1 概述 2 算法 3 程序设计 4 软件工程,1 概 述,什么是计算机软件?,操作系统、QQ、360,计算机系统=硬件+软件,程序以及相关的文档的集合。,什么是文档？,文档：记录软件开发活动和阶段性成果，理解软件所必需的阐述性资料。 需求分析文档 软件设计文挡等 编写文档目的 促进对软件的开发、管理和维护； 便于各种人员(用户、开发人员)的交流,什么是程序？,程序一词源于生活。做任何一件事情，都是有程序的。 例如，颁奖大会的程序；做菜的程序等等。 把做菜的步骤用大家看得懂的方式记录下来，其他人可以按这些步骤顺序实施就完成了该事情。,用计算机完成某事情，就把事先设计好的计算机处理

2、信息的步骤，用计算机能够识别的指令编写出来，送入计算机。计算机按照指令执行，就能完成指定的工作。,算法,程序设计语言,程序就是用计算机语言表述的算法。,为解决一个问题而采取的方法和步骤，就称为算法。,什么是算法？,什么是计算机语言？,人们想和计算机交流，用符号来表达。,怎样维护交通秩序？ 音乐是怎样表示的？,用来表达这种关系的符号系统就是计算机语言，也叫“程序设计语言”。人与计算机交流使用的是“程序设计语言”。 同人类语言一样，程序设计语言也是由字、词和语法规则构成的一个系统。,2 算 法,主要内容,算法的表示 算法的要素 算法的特点 算法的复杂度 常用算法,算法的表示,算法一般可以使用下面几

3、种类型的工具描述： 1.自然语言 例：求12345。,最原始方法： 步骤1：先求12，得到结果2。 步骤2：将步骤1得到的乘积2乘以3，得到结果6。 步骤3：将6再乘以4，得24。 步骤4：将24再乘以5，得120。,改进的算法： S1: 使t=1 S2: 使i=2 S3: 使ti, 乘积仍然放在在变量t中，可表示为tit S4: 使i的值+1，即i+1i S5: 如果i5, 返回重新执行步骤S3以及其后的S4和S5；否则，算法结束。,2.专用图形工具 常用的有流程图、PAD图和N-S图等。,流程图描述,3.伪代码 为了便于转换成某种编程语言，一般采用准程序设计语言作算法描述语言。,伪代码描述

4、：,BEGIN(算法开始) 1=t 2=i while i t i+1=i print t END(算法结束),算法两要素,算法的两要素 算法由操作与控制结构两要素组成。 1.操作 (1)逻辑运算：“与”、“或”、“非”； (2)算术运算：加、减、乘、除； (3)数据比较：大于、小于、等于、不等于； (4)数据传送：输入、输出、赋值。,2.控制结构,1）算法的控制结构，决定了各操作的执行次序。用流程图可以形象地表示出算法的控制结构。 2）任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成。,F,T,我们在构造一个算法的时候，也只能以这三种基本结构作为“建筑单元”，遵守三种基本结构的规范

5、。 基本结构之间可以并列、可以相互包含，但不允许交叉。 正因为整个算法都由这三种基本结构构成，所以结构清晰，易于验证，易于纠错。这种方法就是结构化方法。,算法的特征,有穷性 一个算法必须总是在执行有穷步后结束，且每一步都可在有穷时间内完成； 确定性 算法中的每一个指令必须有明确的含义，不能有二义性； 例：武松打死老虎 手举过头顶 单手?双手？举多高？,可行性(有效性) 算法中描述的操作都是可通过已经实现的基本运算、执行有限次实现的； 例：a/b 若b=0则无效 输入 一个算法应有0个或多个输入； 输出 一个算法应有1个或多个输出。,算法的复杂度,评价算法的标准： 执行算法所耗费的时间，即时间复

6、杂度； 执行算法所耗费的存贮空间，主要是辅助空间，即空间复杂度。,思考：给出一组数12、13、26、27、38、49、55、60、67、86，查找某一个数x是否在这组数中的算法？,的时间复杂度？,算法的设计要求,正确性 满足需求 可读性 有助于算法的理解、调试和修改 健壮性 容错 高效率与低存储量,常 用 算 法,先依据题目的部分条件确定答案的大致范围，在此范围内对所有可能的情况逐一验证，直到全部情况验证完。 若某个情况使验证符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。,1.枚举法,例：公鸡每只五元，母鸡每只三元，小鸡三只一元，问一百元钱买一百只鸡有几

7、种买法？,假设公鸡数为x，母鸡数为y，则小鸡数是z，也就有了下面的方程式：,x+y+z=100 5x+3x+z/3=100,算法：,2.递推法,顺推法和倒推法,例：猴子分食桃子 一天，一只猴子采得一堆桃子，当天它吃掉一半多一个，第二天又吃了一半多一个一直到第七天，它就剩一个桃子了。那么那天它共采了多少个桃子呢？,算法： S1: 使s=1 S2: 使t=7 S3: 使(s+1)2, 结果仍然放在变量s中，可表示为(s+1)2 s S4: 使t的值-1，即t-1t S5: 如果t=1, 返回重新执行步骤S3以及其后的S4和S5；否则，算法结束。,3.递归法,如果一个过程直接或间接地调用它自身，则

8、称该过程是递归的。,例：求阶乘。,算法：,Function Factorial(n As Long) As Long If n = 1 Then Factorial = 1 Else Factorial = n * Factorial(n - 1) End Function,例：有一个nm的棋盘(2=n=50，2=m=50)，在棋盘上有一个马，马走的规则为：马走日字且只能向右走。当n，m给出之后，同时给出马起始的位置和终点的位置，找出从起点到终点的所有路径的数目。,4.回溯法,回溯算法：从一条路往前走，能进则进，不能进则退回来，换一条路再试。,3 程序设计基础,程序设计的一般步骤：,解决问题的

9、核心： 算法及算法的处理对象。,一个程序应包括： 对操作的描述。 即操作步骤，也就是算法(algorithm)。 对数据的描述。 在程序中要指定数据的类型和数据的组织形式，即数据结构(data structure)。 Nikiklaus Wirth提出的公式： 数据结构+算法=程序,程序设计语言,1.发展的过程 程序设计语言分类：机器语言、汇编语言、高级语言,机器语言 机器语言是一种CPU指令系统,是该CPU可以识别的一组组由0和1序列组成的指令码。 最初的语言是机器语言，二进制编码，机器可直接执行，执行速度快。,00000001000000001000 数据装入寄存器0 0000000100

10、0100001010 数据装入寄存器1 00000101000000000001 寄存器0与1的数据乘 00000001000100001001 数据装入寄存器1 00000100000000000001 寄存器0与1的数据加 00000010000000001110 保存寄存器0里的数 编程困难、可读性差、容易出错、可移植性差,汇编语言 用一些简洁的英文字母、符号串来替代一个特定的指令的二进制串，比如，用“ADD”代表加法，“MOV”代表数据传递等等。 例：load 0,a 将单元a的数据装入寄存器0 load 1,b 将单元b的数据装入寄存器1 mult 0,1 寄存器0与1的数据乘 lo

11、ad 1,c 将单元c的数据装入寄存器1 add 0,1 寄存器0与1的数据加 save 0,d 将寄存器0里的数存入单元d,计算机无法直接执行汇编语言程序，执行前需要翻译为机器指令。 最早是人自己翻译，后来人们开发出“汇编系统”，让计算机去完成这项工作。 汇编语言细节太多，程序无结构，缺乏组织手段，写程序仍然很困难。,高级语言 具有类似文字的表现形式； 用类似数学的表达式形式描述基本计算； 用变量等概念取代低级的存储概念，人们摆脱了繁琐的存储安排工作； 提供高级流程控制手段和程序组织手段。 例：d=a*b+c,高级语言程序必须经过翻译变成机器语言程序。翻译有两种做法：编译和解释，相应的翻译工

12、具分别叫做编译器和解释器。,汇编语言VS高级语言,DATA SEGMENT XX DB X YY DB ？ DATA ENDS CODE SEGMENT ASSUME CS：CODE，DS： DATA START：MOV AX，DATA MOV DS，AX MOV AL，XX CMP AL，0 JGE BLGR MOV AL 0FFHAL， MOV YY，AL HLT BLGR：JE EQUT MOV AL 01HAL， MOV YY，AL HLT EQUT:MOVE YY，AL HLT CODE ENDS ENDSTART,If x0 then y=1 elseif x=0 then y=0

13、 else y=-1 endif Print x,y,常用高级程序语言,目前，使用较广泛的高级语言有C、C+、Visual Basic 、Visual Foxpro 、Visual C+、Power Builder、Java、Delphi、ASP、JSP、PHP等。,2.常见的程序控制结构,程序设计方法,面向过程的程序设计,面向过程的程序设计强调模块化和结构化。采用自顶向下、逐步求精的程序设计方法；使用三种基本控制结构构造程序。遵循这种方法的程序设计就是面向过程的程序设计。,常用软件：C，FORTRAN，PASCAL等。,程序分解实例：,面向对象的程序设计,什么是对象？,现实世界中,比如书、人

14、、车都是对象。我们怎么区分它们呢？从外观特征以及他们的动作行为。 比如：人 外观：一个脑袋,两条腿,两个胳臂 动作行为：说话,吃饭,跑步,流泪,在面向对象编程中，程序被看作是相互协作的对象集合，通过消息来实现对象间的通讯。,类是对象的集合，每个对象都是某个类的实例，所有的类构成一个通过继承关系相联系的层次结构。,常用语言：Java、c+、VB.Net等。,在结构化程序设计中可以用下面的式子表示程序： 程序=数据结构+算法 在面向对象程序设计中可以用下面的式子表示程序： 程序=对象+对象+对象 对象=算法+数据结构,面向过程：分析出解决问题所需要的步骤，用函数把这些步骤一步一步实现，使用的时候一

15、个一个依次调用。 面向对象：把构成问题事务分解成各个对象，建立对象的目的不是为了完成一个步骤，而是为了描叙某个事物在解决问题中的行为。,例1：有一台如下流程的演出：主持人开场演员1表演演员2表演主持人总结。 用面向过程的思想来分析，就是先完成主持人开场，再完成演员1的表演，再完成演员2的表演，最后完成主持人的总结。 如果用面向对象的思想来分析，就是：这个演出由两大部分组成：主持人、演员。与主持人相关的：开场、总结。与演员相关的：演员编号、所演的节目。然后这台演出就可以这样策划：需要一个主持人a，需要两个演员b、c。演出的事情可以表示为：a的开场 b、c的编号和节目 a的总结。,例2：下五子棋

16、面向过程的设计思路就是首先分析问题的步骤： 1、开始游戏， 2、黑子先走， 3、绘制画面， 4、判断输赢， 5、轮到白子， 6、绘制画面， 7、判断输赢， 8、返回步骤2， 9、输出最后结果。 把上面每个步骤用分别的函数来实现，问题就解决了。,面向对象的设计思路是，整个五子棋可以分为： 1、黑白双方，这两方的行为是一模一样的， 2、棋盘系统，负责绘制画面， 3、规则系统，负责判定诸如犯规、输赢等。 第一类对象（玩家对象）负责接受用户输入，并告知第二类对象（棋盘对象）棋子布局的变化，棋盘对象接收到了棋子的变化就要负责在屏幕上面显示出这种变化，同时利用第三类对象（规则系统）来对棋局进行判定。 可以明显地看出，面向对象是以功能来划分问题，而不是步骤。,功能上的统一保证了面向对象设计的可扩展性。 比如我要加入悔棋的功能，如果要改动面向过程的设计，那么从输入到判断到显示这一连串的步骤都要改动，甚至步骤之间的顺序都要进行大规模调整。