《计算机信息技术》第三章计算机软件

第3章计算机软件

3.1概述

3.1.1什么是计算机软件

软件(Softeware)这个术语是1957年由美

国统计学家JohnWilderTukey首先使用的。

在计算机领域，软件被ISO定义为：包含与

数据处理系统操作有关的程序、规程、规则以

及相关文档的智力创作。

所以，软件可概括为：

计算机软件=程序+数据+文档

2

过

性

，程

确定性：:

使

某

用

种

口程序完成某一确定计

语

机

言

描

述

信息处理任务

□是软件的主体

动态性：

口是告诉计算机处今及期啰

T效果只能

（语句）序列」在运行过

程中展现

□是存储在某种介质上的，静态实体。只

有被装入内存，3动执彳寺后才起作用！

3

口数据

是程序所处理的对象（输入）、及处理后得

到的结果（输出）的统称

程序和数据都有相对性:

一个程序执

行后得到的

输入数据一结果可能是

另一个程序

执行时的输

入数据

4

输入给编译程序产生另一种

的源程序（数据）形式的程序

语言源程序—►计算机系统A目序

一个程序执行时只有

获得正确的数据才会

获得有意义的结果！

2,5,人,8,人一计算机系统►9•9•9•

5

口文档

文档是程序开发、维护和使用所涉及的完

整、规范化的资料：

•设计报告；

•维护手册；

・使用指南；

・参考资料；

6

口软件的作用

软件是计算机系统中的重要组成部分，归

结起来其作用有三：

口用户与计算机系统之间的接口界面；

□计算机系统中的控制、指挥与管理；

口扩充计算机硬件功能、提高效率。

7

口软件的发展

软件的发展与计算机应用和硬件的发展相

互促进，更多的是受到应用要求的影响。其发

展大致经历了3个阶段：

□程序阶段（40年代到50年代中期）

从第一个实用的计算机程序开始到实用的

高级语言程序出现以前，是计算机软件发展初

期。这个阶段软件主要特征是：

8

•软件即是程序，二者之间没有区别；

•用低级语言编写程序；

・软件规模小；

•只注重程序功能、追求占用内存小，节省运

行时间、强调编程技巧等；

•个体工作设计方式；

•应用领域窄，主要是科学与工程计算。

9

口软件阶段（56年〜68年）

高级语言FORTRAN出现到软件工程概念

提出的这段时间。这个时期的软件特征是：

•用高级语言编写程序，出现了操作系统、数

据库管理系统；

•程序不仅仅是一段代码，还包含了测试、维

护及说明书，程序规模中等；

・设计不是由个人，而代之以是由开发小组；

采用结构化程序设计方法；

•应用领域扩大（大量的非数值计算）

10

存在问题：

•软件需求迅速增长，软件的复杂性大大增加;

•软件研制周期长；

•软件研制费用大，到1965年计算机软件费用

已上升到系统的60%；

•软件的可靠性、正确性问题突出。

产生了“软件危机”：

11

•软件开发的高成本同产品质量之间的矛盾；

•软件技术的缓慢发展与硬件技术的高速提高

之间的矛盾；

•大量的人力、物力与极低的软件生产力之间

的矛盾；

•作坊式的生产与大规模的需要之间的矛盾。

12

为了摆脱软件危机，NATO（北约）的科技

委员会68年秋季在德国召开了一次会议，讨论

对策，会上首次提出了“软件工程”概念，并

着手从以下3个方面解决软件危机问题：

•提出结构化程序设计方法；

•提出用工程化方法开发软件；

•从理论上探讨程序正确性与可靠性问题;

从此软件的发展进入第三阶段。

13

口软件工程及软件产品阶段（68年〜今）

软件工程概念可以这样来理解：

•采用工业化的原理和方法对软件进行规划、

开发与维护；

•作为一种产品来开发；

•软件开发按一步步的“工序”来完成:

14

.软件工程开发的瀑布模型

八句题定义

T、

可行性研究（技术、经济、社会可行性）

甘

(月

需求分析（系统与软件需求分析）

「设计（总体与详细设计）

开

疫<编程

期

八〔测试占33%时间

运占67%时间

行运行与维护

期15

・计算机软件技术（略）

为了实现软件的优质生产目标，经过30多年的发展研

究，计算机工作者做了大量工作，产生了各种理论、技术

和方法，逐渐形成了软件学科。计算机软件技术包括如下

7个方面：

①软件工程技术

软件开发的原则与策略；软件开发方法与软件过程模

型；软件标准与软件质量的衡量；软件开发的组织与项目

管理；软件版权等。

16

②程序设计技术

程序的结构与算法设计；程序设计的风格；程序设计语

言；程序设计方法和程序设计自动化；程序的正确性证明；

程序的变换等。

③软件工具与开发环境技术

接口技术；软件自动生成；软件工具的集成和软件开发

环境；软件的复用；逆向工程等。

④系统软件技术

操作系统；编译方法；分布式处理系统；并行处理技术等。

17

⑤数据库技术

数据模型；数据库与数据库管理系统；分布式数据库;

面向对象的数据库技术、各类专用数据库技术等。

⑥网络软件技术

协议工程；网络管理；局域网技术；网络互连技术；智

能网络等。

⑦与实际工作相关的软件技术

软件质量的控制；软件配置的管理；用户的在线帮助

文档和图标设计；软件规模控制、软件评估和软件开发计

划的制定；软件需求的表示和软件规格说明书的确定等。

18

3.1.2软件的特性

口动态性/不可见性

记录软件的载体只是软件的逻辑实体,而

非物理实体，其价值不以载体的成本衡量，

只能由其运行过程反映的功能与效果来体现。

口适用与通用性

通常适用于一类应用问题,并不只是解决

特定问题。如Word可以适应各种文本处理的

需要。

19

口依附性

依附于特定的硬件、网络和其他软件。为

了让一个软件能在不同系列的硬件系统上运行，

不是简单的复制，而必须采用软件“移植”方式

口复杂性（规模、人员、投资）例如：

•WindowsXP源程序约有5000万行

•Vista及Office2007开发设计成员达9000余

人，总投资$240〜270亿美元，开发周期达

6年之久

20

□软件不会老化、磨损、失效

任何工业产品（特别是电子产品）在使用

过程中，老化、磨损、失效率其失效率呈“U”

型曲线（即所谓的浴缸曲线）

失效率1失效曲线

A时间

而软件功能和性能不会发生变化，很多60

年代的软件现在还仍然运行良好，看来还将继

续运行下去。因此软件只有“过时”而不会失

x21

□易复制性

软件复制的效果可以与原版一模一样。而

仿制工业产品的形态、功能不可能一模一样，

且有质量问题。现在所谓的“软件工厂”的

说法，只是指“高效开发软件”，并非指以

工厂模式制造、生产软件。

口不断演变性

软件功能不断扩充、完善（更新升级、补

丁、修复漏洞，提高安全）例如：

Office2000>Office2003>Office2007

版本的不断变化22

口有限责任

目前还无法从理论上证明一个软件能百分

之百正确执行！软件运行错误导致的问题与软

件商无关。

“本软件不做任何保证。程序运行的风险

由用户自己承担。这个程序可能会有一些

错误，你需要自己承担所有服务、维护和

纠正软件错误的费用。另外，生产厂商不

对软件使用的正^性、精确性、可靠屉和

通用性做任何承诺。”

□脆弱性

黑客攻击、病毒入侵、信息盗用……很难

防止软件被恶意地修改与破坏23

3.1.3计算机软件的分类

口按软件用途

计算机软件

系统软件应用软件

文字处理

操作系统图形图像

电子表格

数据库管理系统演示软件

信息检索

语言处理系统网络通信游戏娱乐

实用程序学习软件

口系统软件

•给用户使用计算机提供方便

•给应用软件的开发与运行提供支持

•使计算机有效、安全、可靠地运行

口系统软件主要特征

•依赖于硬件，与计算机有很强的交互性；

•控制、调度和管理计算机资源；

I•通用性，所有用户都可以使用；

•系统的基本软件。（但只有OS必不可少!）

口实用程序（Utility）

实用程序用于协助os或用户完成日常系统

维护和监管任务，使计算机系统更加安全、可

靠、方便、有效。

杀毒软件防火墙

备份软件

26

□应用软件

是针对特定应用需求，专门用于解决各种具体

应用问题的软件。

应用软件按应用范围可分为：

•定制应用软件

是按特定应用要求而专门开发的软件。

•通用应用软件

几乎所有领域、所有人都需要使用的软

件。可分为若干类：

27

□中间件(middleware)软件

是应用软件与系统软件之间使用的标准化

编程接口和协议。

•便于相对独立地(独立于计算机硬件与

操作系统)开发应用软件；

•节省开发成本；

•便于实现通用性与兼容性

28

□各种软件之间的关系

29

用户

应用软件

虚拟机

C画

用户.A操作系统.破

其他系统软件

应用软件

30

HiOS,要打

印的数据已

经准备好了,

Hi,财务系统,应用软件

放在报表文

请准备打印数

件中！

据！

系统软件Hi,打印机，

HiOS,用户把报表文件

要求打印！中的报表打

计算机硬件印出来吧！

打印机打

键，要求打印

印报表

口按软件权益与保护

根据ISO对软件的定义，软件是一种“智能

创作”，是一种知识产品，因此与书籍、电影

等一样受到版权保护。从这个角度看：

32

□版权保护

版权是给予作者对作品的独占权利的合法

保护形式。

版权的所有者唯一地享有该软件的拷贝、

发布、修改、署名、出售等权利，所有违反上

述条件的做法都是违法行为。

购买一个软件获得的只是使用权，并没

有获得该软件的版权。

33

口软件许可证保护（Licence）

许可证是一种法律合同，它放宽了版权法

给予用户的使用权利。允许用户按如下方式使

用软件：

•允许复制，但限制使用者和范围。

•允许多人使用同一个软件许可证。如某个

单位的所有员工。

•不得进行反汇编、反编译

•不得将其组成部分分散在多台计算机上

•不得出租或出借34

口商品软件

商品软件需要付费使用，受版权和软件许

可证保护

口共享软件(shareware或demoware)

共享软件是买前免费试用、具有版权的软

件，允许拷贝和散发，但不可修改。

35

□自由软件(FreeSoftware)

遵守自由软件基金会(FSF)的通用公共

许可证(GPL)免费软件。允许销售和自由传

播，但源代码公开、允许修改。

口免费软件(Freeware)(rFreeSoftware)

无需付费即可获得的软件。如PDF阅读器、

Flash播放器等

注意：Freeware^FreeSoftware,自由软件很多

是免费软件；免费软件不全是自由软件！

36

3.2操作系统

计算机的作用与神奇众所周知。那么，靠

什么来控制计算机？用户和计算机之间起媒

介作用的是什么？又由谁来提供各种服务？

正是操作系统(OperatingSystemOS)

3.2.1操作系统概述

11操作系统的作用

任何一种计算机都必须配置一种或多种操

作系统，配置操作系统的基本目的有4个:

37

□为用户提供一个良好环境（对用户屏蔽硬件操

作特性），使用户容易使用这样的系统

口扩展机器功能，使用户能获得更多的服务

口统一管理系统资源，使资源得以充分利用，且

能被正确、安全共享

□合理组织计算机工作流程，使系统高效工作

38

口操作系统在计算机系统中的地位

□是计算机系统中必须的软件

口是最重要的一种系统软件

□是控制计算机系统工作的软件

其

39

口操作系统的启动（加载）

口安装与加载OS的概念

操作系统本身由一些程序模块组成，安装

操作系统是指安装到硬盘上

因程序必须调入主存才可执行，而OS是程

序，所以必须装到内存（称之为加载，只装入

必要的部分并非全部）才可执行。

加载由驻留在BIOS中的引导程序引起

成功加载启动OS执行后，整个计算机就处

于OS的控制之下。启动过程如下:

40

□PC机中加载操作系统的过程

⑤装入引导程序RAM

硬盘」⑦装入操作系统一

CMOS

显示初

始界面

S513LA「■②执行自举装入程序、

BIOSCPU

ROMU10

V32R03A1H1

OCopyright

Acerlnc.①执行加电自检程序

41

口操作系统的功能

从资源管理的角度看，操作系统的主要功

能有：

□处理器（CPU）管理

口存储管理

口文件管理

口设备管理

口作业管理

42

3.2.2多任务处理与处理器管理

口什么是“任务”？

任务（task）是指装入内存并启动执行的一个

应用程序。一个任务对应着屏幕上的一个窗口。

口单任务处理系统

在这种系统中，只能启动一个任务，仅当当

前一个任务完成后才能启动后一个任务运行（顺

序执行）

口多任务处理系统

允许同时启动多个任务执行（并发执行）

43

并发多任务指宏观上多个任务在同时在执

行，而在微观上任何时刻只有一个任务正在占

有CPU执行。实质是CPU轮流为所有任务服务。

口寸间

并行则是指在多处理器系统中多个任务占

有不同的CPU真正同时执行o

44

口前台/后台任务

□前台任务指正在占有CPU执行的任务（仅一

个，也称当前任务或当前窗口），输入的信

息一般是送给前台任务；

□后台任务即“非活动任务”，可以有若干个。

前台任务与后台任务的共同点：都在计算

机中运行，都有机会占有CPU执行。

前台任务与后台任务之间可被切换

45

口实现多任务处理的目的

口提高用户的工作效率

口提高计算机资源利用率

II实现多任务处理的条件

口CPU速度要快

口充分大的内存储器

口CPU与I/O设备之间可以并行工作

口外围设备之间可以并行工作

46

口实现多任务处理要解决的问题

□任务多，CPU少，如何管理和调度

口存储器空间如何分配和管理

口I/O设备如何分配、管理

□……

47

口处理器管理的主要工作

口CPU的分配与调度，分配单位：线程、进

程、任务;

口线程、进程、任务的切换；

口实施调度策略

•时间片轮转调度

CPU的一个时间单位。即任务轮流占

有CPU执行的单位时间（ms为单位）

48

•优先级调度

•先来先服务调度

□Windows的多任务处理及处理器调度

采用“抢先式”多任务处理调度技术：

指分配给一个任务的时间片到了，无论

任务结束与否，强行让出CPU执行其他任务

的CPU调度方法。

49

3.2.3存储管理

操作系统仅对RAM进行分配与管理。

RAM

应用程序1每个应点

操作系统区

应用程序2程序均有

属于它自

用户区己的存储

应用程序4器空间

应用程序5、____，

50

口存储管理的主要工作

口主存的分配与回收；

口实现主存空间共享（由多个程序共享）；

口实现存储保护；

保证自己的区域可读又可写；公共区

域（共享区域）可读禁止写；别人的区域

不可读不可写。

□实现虚拟存储器，解决主存不够用的问题

51

口实现虚拟存储器的基本思想

□借助磁盘存储器作为主存储器的扩充；

口将程序和数据分页，存放到磁盘上；

口将主存分块（块与页的大小相同）；

口装入部分页面到主存块中

口若访问的页面不在主存中，则从盘上调入所

需页面，若已无空闲内存块可用，则淘汰

已在主存的一个页，腾出空间装入新的块

52

内存分块程序分页

块00

块21

执行页0中的程序时要访问页1,2

此时页1不在内存，请求调入页13

入

执行页1中的程序时要访问页2,页

此时页2不在内存，请求调入页2调0

执行页2中的程序时要访问页3,

口

此时页3不在内存，请求调入页3调入页2

।口口才口

「二口

上Ir一j——p—PI

此时已无空闲块，淘汰页0（已多

时不用），腾出的空间调入页3

53

口Windows中的虚拟存储器

口由RAM、硬盘上的交换文件pageflle.sys>

页表、地址转换机构等组成；

口每个程序的虚存空间最大可达到4GB

口页面大小：4KB（用户可自行设置）

□采用“LRU最近最少使用”页面调度算法

口虚拟存储器设置：

右击“我的电脑”一“属性”一“高级”一

性能框中的“设置”一高级一虚拟内存中的

“更改”54

口利用“任务管理器”查看内存的使用情况

理

.

■.

数

用

统

板

内

百

心

总

要

分

餐

分

耒

324文件管理（文件系统）

负责管理计算机中的文件，使用户和程序

能方便地按名存取文件

文件系统

外存储器

56

口文件概念

文件是以一个名字标识的一组相关信息的集合

口文件名

不同系统的文件名的形式与命名规则不同。

如在Windows中：

主文件名

•最多可包含255个字符

•不能使用？*\/v>等字符

•扩展名可有可无

•字母的大小写只是形式上的区分57

□文件的组成「目录区」

文件内容

说明信£文件内9

•基本属性（文件名字、所有者）

•类型属性（系统文件、设备文件、目录文件、隐

藏文件、存档文件、压缩、加密、索

弓I、二进制、文本文件……）

•存取保护属性（只读、读写、可执行、可删除）

•管理属性（创建时间、最近访问与修改时间）

•控制属性（文件大小或长度、存放位置）58

口文件管理的功能

口文件的存储

文件内容的存储大致有3种物理组织形式：

•连续存储（顺序文件）

文件名…存储位置。

•链接存储（链接文件）

文件名…存储位置。

59

60

口文件的组织（文件目录）

为便于管理、维护和检索文件，文件系统

把一个存储设备中的所有文件组织在许多文件

目录中。

•文件目录（文件夹）

实际上是用来记录文件说明信息（属性）的

一个特殊文件。

文件夹中既可以登记文件，也可登记子文

件夹，依此类推可以有若干层，而形成多级树

形目录结构。

61

•多级树形目录结构

abc.txt

Ol.docO2.ppt05.pdf

62

注意：

口树形目录结构是以盘（一个逻辑硬盘、优盘、

光盘等）为单位组织的，即每一个盘上都有一

个独立的树形目录结构。

口盘未格式化前，其上并不存在这样的树形目

录结构，盘格式化后也只是自动建立一个最基

本的目录——“根目录”，以标识。

♦“\”目录只能通过盘格式化或全盘复制产生

♦除目录之外，所有其他的子目录都是

由用户自己建立的。

63

•采用树形目录结构管理文件的优点

口有利于文件分类管理与维护

口允许在不同的文件夹中建立文件同名文件

口便于文件共享和保护

口便于文件检索与定位

64

文件在树形目录结构中的位置由文件所在

的驱动器号、文件路径以及文件名组成。

例如：

C:\数据\01.doc

应用程序

（绝对路径）

Pl.exe

概论'教案\01.doc

（相对路径）

资料

01.docO2.ppt65

口文件的安全与共享

文件的安全指防止系统崩溃和非法操作文

件时造成的文件破坏。

文件共享指不同用户（程序）使用同一文件。

实现文件共享的目的：

・减少存储空间的开销

•复制，存取及传输的开销

•满足不同用户协同完成同一任务的需要

66

口文件的操作与存取

为了方便用户和程序进行文件的存取操作,

文件系统应提供方便的存取文件的手段：

•创建

存

•保

开

•打

写

•读

除

•删

贝

•拷

送

•发

67

口外存空间的管理、分配与回收

文件存储空间管理方法有很多种，这里仅

简要介绍Windows中盘空间的管理方法。

盘存储空间的分配单位：“簇”，簇大小

与盘容量有关，一般为2n个扇区。

格式化盘时产生FAT,其中每个登记项对

应一个簇的使用情况（占用为非0值、空闲为全

0、损坏为全1）。

68

一个文件所占用簇的簇号组织成一个“簇号

链”，其起始簇号在FDT中指出：

文件名及扩展名……起始簇号文件大小

例如，若文件乂丫尸11^占用了5个簇(％16,

L10和25),其簇号链是：

9--16--1--10--25

该“簇号链”在FAT表中的链接状态如下:

注：文件的最后1簇的状态值为“EOF

69

文件分配表(FAT)

012345678910111213141516171819202122232425262728293031

文件名扩展名创建日期时间文件大小属性起始簇号

*□7口

卜m…中«oMYFILETXT1/23/200413:2440,3630’

，口上又？

IMS'O1«CJ««O

；'«O*[cZ»CJnQJ

MCa»O9*0

3•口0.二!X＞口，,口

J.

70

3.2.5设备管理

管理系统中I/O设备，使用户不必了解设备的

驱动细节,只要用简单操作就能方便、有效地完

成设备的I/O操作。

设备管理的主要任务：

□外部设备的分配，调度；

□外部设备的驱动与控制；

口实现虚拟设备，解决设备不够用、速度慢

、故障多问题；

口实现设备共享；

71

3.2.6常用操作系统介绍

口操作系统的类型

□批处理操作系统

程序

数据作业

说叫世

操作员

按说明书自动控

制程序的执行

72

批处理操作系统的特点:

・着重考虑系统效率和资源的利用率；

・用户不能直接上机，用户与作业非交互;

•作业由OS按说明书控制执行；

・不利于程序的开发和调试；

•作业的周转时间及平均周转时间长。

73

口分时操作系统

允许多个用户联机使用同一计算机系统,

进行交互式计算

74

分时系统特点：

・用户联机使用同一计算机系统

•分时系统着重快速响应、在于方便使用

•可亲自上机与作业和系统交互

用户进入系统的过程通常是：

连接一登录一使用系统一退出一断开

分时系统需要额外的硬件和软件，如前端

处理机、终端、通信软件

75

□实时操作系统

在接收到外部信号后必须及时

处理，且在严格的规定时间内处理

完毕，并给出处理结果（信号）的

操作系统，适用于瞬时控制的领域

实时系统特点：

•专用、不复杂、实现相对容易

・自动化程度很高，极少人工干预

•处理速度、可靠性、正确性要求高

76

口网络操作系统

「网络通信

网络资源共享

网络服务

常规的操作系统+

网络管理

网络安全

I网络应用

网络操作系统特点:

•具有强大的多用户并发处理能力

•支持多种网络通信功能

•安全性强，可靠性好

77

口嵌入式操作系统

嵌入在某个设备中，支持嵌入式软件运行,

起智能控制作用的操作系统。

嵌入式操作系统特点是：

•快速、高效

•专用性、实时性、可靠性

目前较成熟的嵌入式OS：gC/OS-II

VxWork

pSOS78

□Windows操作系统

□特点

•广泛用于个人计算机

•抢先式多任务处理

•GUI用户界面、操作方便直观

•支持虚拟存储器（理论上达4GB）

•增强的网络和多媒体功能

•允许使用长文件名；

•支持“即插即用”功能;

•以数据为中心

79

□版本的演变Windows的

Windows9x共有3个最新产品，

产品，面向家用PC有多种不同

/八\用途的版本

198519871990199519982000

-I——I1——I——I——K200120062009

1.02.03.09598MEXf

19?3।/

XPVistaWin7

WinNTWin2000

适合家庭、商用。有家庭版、

面向商用PC机，性能专业展、媒林中心版、和64

较高，安全性较好，提位版本等。有丰富的音、视

供服务器版本频和网络通信功能

□Windows操作系统的使用情况

WindowsOS市场份额对Windows的批;评：

DateMay2010

•可靠性不够高

Allversions91.16%

WindowsXP62.55%不稳定，系统会越

Windows来越慢，甚至死机

15.25%

Vista

Windows712.68%•安全性不够好

Windows20000.5%存在安全漏洞，容

Windows980.1%易受到病毒、蠕虫、

WindowsMe0.08%木马和其他攻击的

Windows侵扰

Server200381

□UNIX操作系统

一种通用的、多用户、交互式的分时操作

系统。可在巨型机、大型机上作为网络操作系

统使用

UNIX特点：

□结构简练系统分成内核层和外壳层

口可移植性

口可伸缩性能在各种硬件配置上运行

口开放性源代码开放

□网络通信功能强

□Linux操作系统

ElLiiiux特点：

口类UNIX操作系统

口可移植性强（做到二进制兼容）

□GUI界面（X-Window）

□支持多至32种不同的文件系统

口软件丰富，且都是免费的

□其他特点同UNIX

83

口Linux应用

Linux作为服务器操作系统：占到26.3%

Windows:占至24%

3Linux的起源与发展

1990年芬兰赫尔辛基技术

大学的学生LinuxTorvalds在

学习了MINIX后，自己动手写

了一个操作系统的内核，取名

为Linuxo

1991年，LinusTorvalds公开了Linux内核

1993年,Linux转向GPL版权协议

1994年，Linux1.0第一个商业发行版Slackware问世

1996年，美国国家标准技术局确认Linux版本1213

符合POSIX标准

1999年，Linux的简体中文版问世

2001年，Linux2.4版发布

2003年，Linux2.6版发布

目前的最新版本是：2.6.26（July13,2008发布）

85

3.3算法与程序设计语言

3.3.1算法

口什么是算法？

一般而言：

为解决一个问题而采取的方法和步骤。

严格而言：

算法是由若干条指令组成的有穷序列并

满足：

86

•零个或多个外部输入；

•至少产生一个输出；

•每条指令无二义性；

•每条指令的执行次数和时间有限。

[1算法的性质

按算法的定义，算法有如下性质：

□有穷性（有限性）

在有限的时间内，所有的步骤执行有限

次，且可以执行完毕。S7

口确定性

每一步操作必须是确定的，不应产生二义性。

口可行性/有效性

每一步操作应能被计算机有效地执行，并

能得到预期的结果。如，计算除法时除数为零

就是不可行的、无效的。

口有零个或多个输入（外部提供的初始数据）

□至少产生一个输出（提供给外部的运算结果）

88

口算法分类

□数值计算算法

例如，方程求根，积分计算等。

□非数值计算算法

例如，统计，排序，查找、交换等。

89

口算法例

例1:

有3个硬币，其

中一个是伪造的，

另两个是真的，伪

币与真币重量略有

不同。

现提供一座天

平，如何找出伪币

呢？

90

例2:“选择排序”算法□7・8.2.5

71812|51

S1:从数列中找到最小718141§

的数，与第一个数

交换

S2:从剩下的数列中找

到最小的数，交换

到已排序数的后面

S3:反复执行步骤S2,

直到所有数都处理

完毕

例3:“二分查找”算法

要从给出的一组数据（II个）中找出某个数据

k,较快的方法是利用折半查找法。

S1:对给出的一组数据排序

S2：置T=LB=n（首尾数据的序号）

S3：取中点（T+B）/2,取整

S4：比较k与（n+l）/2位置的值

若相等找到（结束）

若小于置B=（T+B）/2

若大于置T=（T+B）/2

S5：若（T+B）/2=0找不到，否则重复S3,S492s5

如从中查看是否有数2,则利

用二分查找法查找的过程如下:

排序2345789查找范围i：T=l,B=7

取范围1中点03|4|5|7|8|9]

在范围1左半查找HSQS789查找范围2：T=1,B=4

取范围2中点H7T8T9

在范围2左半查找2345789查找范围3：T=1,B=2

取范围3中点国3HSIH8T9

在范围3左半查找234578以查找范围4：T=1,B=1

93

例4:计算5!(略)

算法1：

(si)指定一个存储单元T,置初值为1；

(s2)计算TX2,将计算结果保存到T；

(s3)计算TX3,将计算结果保存到T；

(s4)计算TX4,将计算结果保存到T；

(s5)计算TX5,将计算结果保存到T；

(s6)输出T的值；

(s7)停止。

缺点：繁琐，不易扩充。

94

算法2：(略)

(1)指定两个存储单元T和I；

(2)1->[2一I；

(3)T义I―T；

(4)1+1->I；

(5)若IW5,转移至(3)执行;

(6)输出T的值；

(7)停止。

缺点：不具有通用性。

95

算法3：计算加(略)

(1)指定存储单元T、I和N；

(2)从键盘输入一个任意正整数，并保存到N中;

(3)1->T,27I；

(4)TXI->T；

(5)I+l->I；

(6)若IWN,转移至(4)执行；

(7)输出T的值；

(8)停止。

96

算法复杂度分析(选讲—略)

一个算法的复杂度体现在运行该算法时所需要的计

算机资源的多少，资源越多复杂度越高；反之，复杂度

越低。

因CPU时间和存储空间是主要资源，所以算法的复

杂度仅考虑时间和空间复杂度,且分别用两个函数来表

示：T(n)与S(n)

其中n为问题规模的大小，如多项式的项数、数组

元素的个数、矩阵的阶……

又因T(n)与S(n)的性质是类似的，所以一般

只研究T(n)

97

一般而言，对于T(n),当n单调增加且趋于8时，T(n)也

将单调增加且趋于8时，对于T(N)如果存在T(n),使得当n-oo

时，有：

(X(n)-T(N))/T(n)一。

那么就说T(N医T(n)当n一8时的渐近性态，通常用0(n)表、

示，并用0(n)来表示时间复杂度。

直观上0(n)就是T(n)中略去低阶所留下的主项。例如：

若T(n)=3n2+4nbgn+7,则0(n)为3M。因为有：

4nbgn+7

(T(n)-O(n))/T(n)=当n—oo

3n2+4nl0gn+7

98

显然，31>2要比3n2+4niogn+7简单得多。

下面是本节的排序例子的复杂度计算。排序规模为no

比较次数：11（11・1）/2而2/2

移动次数：（1>+4）（11・1）/2而2/2

2n2

比较次数+移动次数=n2/2+n2/2=一-二n2

所以，其排序的时间复杂度为0（小）。

99

口算法的表示

□自然语言表示

用任何日常使用的语言（汉语、英语等）

表示算法。

优点：

简单、方便、通俗易懂；

缺点：

是文字冗长、有歧义性、很难表示复杂

的算法。

100

计算n!的算法流程图

输出T

结束

N

102

口伪代码表示法

伪代码(pseudocode)是类似英语、但没

有严格语法的表述算法的方法。

例如：

IFxispositiveTHEN

Printx

ELSE

Print-x

103

□用计算机高级语言表示算法

如下面是用C语言表示的求5!算法的程序:

main()

(

inti,t;

t=l；

i=2•

while(i<=5){

t=t*i;

i=i+1;

104

口常用算法（略）

（1）迭代法

常用的一种求问题近似解的方法。所谓迭代就是从一个

已知的或事先估计的近似值X。出发，通过一个迭代公式

Xn=Q（XQn=l,2,3,……

依次求出Xi、X2、x3……，经过若干次迭代运算而得到

问题精确的解。通常给出一个允许误差£（如10-5）,当

前后两次近似解的绝对误差

IX/Xn.11<£

时，则把Xn作为问题的解。

105

例用牛顿迭代公式求a的平方根。

迭代公式：

Xn+1=1/2X(Xn+a/Xn)

假定：

Xo=5.0

旧

|X1rxm0-5

106

⑵穷举

不重复、不遗漏地考察处理对象的所有可能取值情

况，对每一种取值都作计算并判断是否是问题的解，从

而找出满足给定条件的若干个解。

例：父亲今年30岁，儿子今年6岁，问多少年后父亲的

年龄是儿子年龄的2倍。

求解方程：30+Y=2(6+Y)(其中Y代表年数)

求解算法：

30一F

6Ts

0一Y

WHILE((F+Y)^2X(S+Y))do

Y+l—Y

OUTPUTY

107

⑶递推法

一个问题的最终结果是通过求解一系列类似的中间

结果而得到的，在求解一个中间结果时，利用前面已求

得的一个或多个中间结果推出后一个新的中间结果。

例计算S=l+X+X2/2!+X3/3!++*。/10!的值。

该级数可描述为：

s=a0+a1+a2+...+a10一般公式

a0=l原始条件

an=an_1Xx/n(n=l,2,3...10)递推公式

1.原始条件2.递推公式3.终止条件测试

108

求解算法:

1一S

1一A

INPUTX

FOR1-NTO10DO

A*X/N一A/**/

S+A—S

N+l—N

OUTPUTS

109

(4)递归法

递归指的是在算法中又直接或间接地使用了算法

本身。每次递归调用时，其数据规模比前一次小，即

将原始难度为n的问题简化为难度为的问题。

指的是一个算法中，在结束处理之前，又调用了

算法自身。

指的是一个算法A中调用了其他算法B,而算法B

中又调用了算法A。

110

例求n!的递归算法:

j1当n=0

加=(nX(n-1)!当n>0

计算n!的函数fac:

longfac(intn)

{

longs;

if(n==0)

s=1;

else

s=n*fac(n-l);

returns;

in

口算法与程序的区别与关系

□程序与算法不同，程序可以不满足有限性，而

算法必须满足有穷性。

操作系统是一个无限循环执行的程序，因

此它不是算法！

□算法是解决一个问题的方法和步骤,而程序是

算法的一种描述形式,对算法的具体实现。

□程序有严格的语法规则，算法没有。

□算法是程序的灵魂程序=算法+数据结构

112

口算法分析

解决同一个问题可以设计出若干不同的算法

（就像写文章），当然就存在一个算法优劣的问题

评价一个算法的优劣，主要考虑以下因素：

□正确性，不正确的算法无优劣可言；

口是否易于理解、实现、验证、调试；

□占用臂经期［CPU时间（时间复杂度）

多少《复杂黔1存储空间（空间复杂度）

3.3.2程序设计语言

口基本概念

□程序设计语言

“语言”是表达意思、交流思想的通信工具

是由语音、词汇与语法构成的系统。

程序设计语言则是人与计算机之间的通信

通信工具，用于描述计算机程序的符号系统。

□程序

计算机的指令序列、或者符号化的指令序

歹！J、或者语句序列。

114

□程序设计

设计、编制、测试程序的方法和过程。

比方说：

程序设计就象建筑师按设计蓝图（算法），让

能工巧匠（程序员），利用建筑工具（语言），把

各种建筑材料（数据）有效地组织在一起（数据

结构），建成理想建筑物（程序）的过程。

115

口程序设计语言的类型

据统计，计算机语言有上百种。例如：

口计算机通信语言（通信协议）

用于描述计算机之间会话（请求一应答）

的语言。如:HTTP、POP3、SMTP、FTP、

Telnet>TCP、IP、……

□数据描述语言