第一章 软件设计概论第五章 类与对象第四章 函数第三章 结构化程序设计第二章 C++基础知识第十章 异常处理第九章 输入 /输出流类库第八章 继承与多态第七章 动态内存分配第六章 指针与数组第十一章 标准模板类库 (STL)
附 录目 录
1.1 软件与软件危机
1.2 软 件 工 程
1.3 程序设计方法 1.6 一个简单的 C++程序
1.5 C语言和面向对象的 C++
1.4 算法的设计与分析第一章 软件设计概述
1.1 软件与软件危机什么是软件什么是软件危机软件? 程序软件危机首次爆发于二十世纪六十年代。在大型程序设计中，人们发现投入大量的人力、物力、时间开发出的软件，
其成本、效率、质量等方面却处于失控状态，尤其软件维护异常困难。程序的修改扩充往往需要大量重复性投入。
1.1 软件与软件危机软件危机产生的原因主要有三个：
2 软件是一种逻辑产品而非物理产品，软件的开发过程本质上是人的思考过程。
3 人的智力在面对越来越复杂的问题时，处理问题的效率会越来越低。
1 软件开发者不熟悉用户问题的领域，或没有理解用户需求，软件产品与要求不一致。
1.2 软件工程软件危机的 出现迫使人们重新认识软件和软件开发过程。
大型软件开发也应该借鉴建筑、机械等行业的发展过程，由,手工方式,向,工程化,
方向发展。 1968年在北大西洋公约组织
(NATO)的年会上 首次 提出 软件工程 的概念，
此后又逐步提出 软件生命期 的概念。
1.2 软件工程软件工程的提出和软件的定义软件 是程序、方法、规则、相关文档以及在计算机上运行所必需的数据的集合。而 软件工程 是开发、运行、维护软件的系统方法。
软件生命期软件生命期指从开始研制到废弃不用的整个期间，可划分为五个阶段：需求分析、设计、编程、测试和运行维护。
软件的质量标准正确性 健壮性 可维护性可用性 可重用性 效率等
1.2 软件工程正确性软件的正确性指的是软件系统在 正常条件下 能够正确工作，完成规定功能。这是软件的首要指标。
例如，要求设计程序，输入一批数据，计算它们的累加和。在这里，正确性就是正确能正确计算累加和。
1.2 软件工程健壮性软件的健壮性指的是 在意外情况下 （ 如输入数据不合理或某些硬件故障 ）,软件系统仍能适当地工作,并对意外情况进行适当处理,而不致于导致错误结果甚至系统的瘫痪或死机 。
例如,要求设计程序,根据输入的三边 a,b,c的长度判别三角形类型 。 现有如下设计思想：若 a,b,c中只有两个量相等,则为等腰三角形,若三个量均相等,则为等边三角形,
否则为一般三角形 。 如果输入为 （ -2,-2,-2） 时,程序输出为：等边三角形 。 这个结果显然是错误的 。 这是由于程序对不合理数据不能进行适当处理,我们就说这个程序的健壮性不好 。
1.2 软件工程可维护性软件的维护包括发现并改正软件的错误，以及由于软件运行环境发生变化或软件功能扩充而对软件进行的改动。
软件的可维护性指的是软件容易维护的程度。
一般地说，软件的可读性好，容易理解，维护起来也就比较容易。因此可读性是可维护性的基础。
1.3 程序设计方法
1.3.1 传 统 的 结 构 化 程 序 设 计
SP (Structured Programming)
1.3.2 面 向 对 象 的 程 序 设 计
OOP (Object Oriented Programming)
1.3.1 传统的结构化程序设计传统的程序设计方法可以归结为,程序 =算法 +数据结构,,将程序定义为处理数据的一系列过程。这种设计方法的着眼点是 面向过程的,特点是将数据与程序分开存储，即数据与数据处理分离。
结构化程序设计的基本思想是采用 自顶向下,
逐步细化 的设计方法和 单入单出 的控制结构。
1.3.1 传统的结构化程序设计模块 2
2.1 2.2
模块 1
1.21.1 1.3
1.3.1 1.3.2 1.3.3
模块 3
3.1 3.2
3.1.1 3.1.2
程 序
1.3.1 传统的结构化程序设计举一个简单的例子,要求读入一组整数,统计其中正整数和负整数的个数 。
该任务的模块结构及细化过程如下：
1,读入数据；
2,统计正数、负数的个数 ;
3,输出结果；
正整数个数为 0；负整数个数 0；
取第一个整数
2.1 如果该数大于 0，正整数个数加 1；
2.2 如果该数小于 0，负整数个数加 1；
2.3,取下一个整数；
重复至统计完
1.3.1 传统的结构化程序设计结构化程序设计为处理复杂问题提供了有力手段，但到 80年代末，这种设计方法逐渐暴露出以下缺陷：
（ 1） 难以适应大型软件的设计。
（ 2） 程序可重用性差。
1.3.2 面向对象的程序设计为什么要引入面向对象的设计方法面向对象的设计方法与面向过程的设计方法有什么关系
1.3.2 面向对象的程序设计面向过程程序设计缺点的根源在于 数据与数据处理分离 。
面向对象程序设计模拟自然界认识和处理事物的方法，将 数据和对数据的操作方法放在一起,形成一个相对独立的整体 —— 对象（ object）,同类对象还可抽象出 共性,形成 类（ class ） 。一个类中的数据通常只能通过本类提供的方法进行处理，这些方法成为该类与外部的接口。对象之间通过 消息（ message） 进行通讯。
1.3.2 面向对象的程序设计
1 基 本 概 念
3,面向对象”程序设计的特点
2 面向对象的软件开发方法
1 基 本 概 念对 象（ object）
类（ class）
消 息（ message）
1 基 本 概 念属性行为表针旋钮其他机械机构调节旋钮对 象
1 基 本 概 念类是一个抽象的概念，用来描述某一类对象所共有的、
本质的属性和行为。
类 对象描述这类对象共有的、本质的属性和行为类的一个具体实现，称为实例手表 一块手表手表共有的属性（表针、旋钮、内部结构）
和行为（调节旋钮）
具体到一只圆形的或方形的手表类
1 基 本 概 念我们把对象之间产生相互作用所传递的信息称做消息。
消 息启 动发送消息 接收并响应消息消 息
1 基 本 概 念我们把对象之间产生相互作用所传递的信息称做消息。
发送消息 接收并响应消息转 向
2 面向对象的软件开发方法面向对象软件开发的根本合理性在于它符合可观世界的组成方式和大脑的思维方式 。
在大型程序开发过程中,编码只是其中很小一部分,应当采用工程化的方法,并将面向对象的思想贯穿于软件开发全过程,这就是 面向对象的软件工程 。
面相对象的软件工程同样遵循 分层抽象,逐步细化 的原则 。 软件开发过程包括以下五个阶段：
2 面向对象的软件开发方法测试 的任务在于发现并改正程序中的错误。
面向对象的分析（ OOA）
面向对象的设计（ OOD）
面向对象的编程（ OOP）
面向对象的测试（ OOT）
分析阶段的主要任务是按照面向对象的概念和方法，从问题中识别出有意义的对象，以及对象的属性、行为和对象间的通信，进而抽象出类结构，最终将它们描述出来，形成一个需求模型。
设计阶段从需求模型出发，分别进行类的设计和应用程序的设计。
编程阶段实现由设计表示到面向对象程序设计语言描述的转换。
面向对象的维护（ OOSM）
3,面向对象”程序设计的特点
(1)封装性
(2) 继承与派生性
(3) 多态性
3,面向对象”程序设计的特点封装性内 外机械零件动作调节旋钮读表盘对象是一个 封装体,在其中封装了该对象的属性和操作。通过限制对属性和操作的访问权限，可以将属性“隐藏”
在对象内部，对外提供一定的接口，在对象之外只能通过接口对对象进行操作。
C++通过建立数据类型 ——类 来支持封装和数据隐藏。封装性增加了对象的独立性，从而保证了数据的可靠性。一个定义完好的类可以作为独立模块使用。
汽车客车 货车小轿车 大客车载货载人小，速度快 大，速度慢
3,面向对象”程序设计的特点继承与派生以汽车为例看客观世界描述事物的方式：
当定义了一个类后，又需定义一个新类，这个新类与原来的类相比，只是增加或修改了部分属性和操作，这时可以用原来的类 派生 出新类，新类中只需描述自己所特有的属性和操作。
面向对象程序设计提供了类似的机制：
继承性大大简化了对问题的描述，大大提高了程序的可重用性，从而提高了程序设计、修改、扩充的效率。
新类称为 子类 或 派生类,原来的类称为 基类 。派生可以一直进行下去，
形成一个派生树。
3,面向对象”程序设计的特点语文、数学、英语、政治、
物理、化学、生物多态性多态性指,同一个消息 被 不同对象 接收时，产生 不同结果,即实现 同一接口，不同方法 。
高中生计 算平均成绩
3,面向对象”程序设计的特点多态性多态性指,同一个消息 被 不同对象 接收时，产生 不同结果,即实现 同一接口，不同方法 。
计 算平均成绩大学生 高数、英语、计算机、线性代数
3,面向对象”程序设计的特点继承和多态性组合，可以生成很多相似但又独一无二的对象。继承性使得这些对象可以共享许多相似特性，而多态又使同一个操作对不同对象产生不同表现形式。这样不仅提高了程序设计的灵活性，而且减轻了分别设计的负担。
1.4 算法的设计与分析
1.4.1 算 法 的 概 念
1.4.4 算 法 的 时 空 复 杂 度
1.4.3 常 用 算 法 介 绍
1.4.2 算法的表示及三种基本结构
1.4.1 算 法 的 概 念通俗地说，算法就是解决问题的步骤。
用计算机解决问题的算法应具有以下特征：
(1) 可执行性
(2) 确定性
(3) 有穷性
(4) 可输入输出信息
1.4.2算法的表示及三种基本结构
3 循 环 结 构
1 顺 序 结 构
2 分 支 结 构
1.4.2算法的表示及三种基本结构
【 例 1,1】 求两数之和 。
(1) 顺序结构块 1
块 2
块 3
流程图
num2?20；
sum?num1+num2;
输出 sum;
num1?15；
1.4.2算法的表示及三种基本结构
(1) 顺序结构
【 例 1,1】 求两数之和 。
num1
15
块 1
块 2
块 3
流程图
num2?20；
sum?num1+num2;
输出 sum;
num1?15 ；
1.4.2算法的表示及三种基本结构
(1) 顺序结构
【 例 1,1】 求两数之和 。
num1
15
num2
20
块 1
块 2
块 3
流程图
num2?20 ；
sum?num1+num2;
输出 sum;
num1?15；
1.4.2算法的表示及三种基本结构
(1) 顺序结构
【 例 1,1】 求两数之和 。
块 1
块 2
块 3
流程图
20
num1
15
num2
寄存器
sum
＋ 35
35
num2?20；
sum?num1+num2;
输出 sum;
num1?15；
1.4.2算法的表示及三种基本结构
(1) 顺序结构
【 例 1,1】 求两数之和 。
块 1
块 2
块 3
流程图
num1
num2
寄存器
sum
＋ 35
显示结果,35
15
20
35
num2?20；
sum?num1+num2;
输出 sum;
num1?15；
1.4.2算法的表示及三种基本结构
【 例 1,2】 输入三个数，输出其中的最大数。
x?7;
y?12;
z?10;
if (z>max) max?z;
输出 max;
if(x>y) max?x;
else max?y;
(2) 分支结构流程图条件块 1 块 2
真 假
1.4.2算法的表示及三种基本结构
【 例 1,2】 输入三个数，输出其中的最大数。
x?7;
y?12;
z?10;
if (z>max) max?z;
输出 max;
x 7
if(x>y) max?x;
else max?y;
(2) 分支结构：
流程图条件块 1 块 2
真 假
1.4.2算法的表示及三种基本结构
【 例 1,2】 输入三个数，输出其中的最大数。
x?7;
y?12;
z?10;
if (z>max) max?z;
输出 max;
y
x 7
12
if(x>y) max?x;
else max?y;
(2) 分支结构流程图条件块 1 块 2
真 假
1.4.2算法的表示及三种基本结构
(2) 分支结构
【 例 1,2】 输入三个数，输出其中的最大数。
x?7;
y?12;
z?10;
if (z>max) max?z;
输出 max;
y
x 7
12
z 10
if(x>y) max?x;
else max?y;
流程图条件块 1 块 2
真 假
1.4.2算法的表示及三种基本结构
(2) 分支结构
【 例 1,2】 输入三个数，输出其中的最大数。
x?7;
y?12;
z?10;
if(x>y) max?x;
else max?y;
if (z>max) max?z;
输出 max;
y
x 7
12
z 10
寄存器比较
max12
流程图条件块 1 块 2
真 假
1.4.2算法的表示及三种基本结构
(2) 分支结构
【 例 1,2】 输入三个数，输出其中的最大数。
x?7;
y?12;
z?10;
if(x>y) max?x;
else max?y;
if (z>max) max?z;
输出 max;
y
x 7
12
z 10
寄存器比较
max12
比较流程图条件块 1 块 2
真 假
1.4.2算法的表示及三种基本结构
(2) 分支结构
【 例 1,2】 输入三个数，输出其中的最大数。
x?7;
y?12;
z?10;
if(x>y) max?x;
else max?y;
if (z>max) max?z;
输出 max;
y
x 7
12
z 10
寄存器
max12
比较比较显示结果,12
流程图条件块 1 块 2
真 假
1.4.2算法的表示及三种基本结构
(3) 循环结构流程图条件块真 假
【 例 1,3】 求 4个整数的和。
count?4; //整数个数
while (count>0) {
sum?0; //累加和的初值
x?输入一个整数；
sum?sum+x;
}
输出 sum;
count?count-1;
1.4.2算法的表示及三种基本结构
(3) 循环结构流程图条件块真 假
【 例 1,3】 求 4个整数的和。
count?4; //整数个数
while (count>0) {
sum?0; //累加和的初值
x?输入一个整数 ;
sum?sum+x;
}
输出 sum;
count?count-1;
sum
count 4
0
1.4.2算法的表示及三种基本结构
(3) 循环结构流程图条件块真 假
【 例 1,3】 求 4个整数的和。
count?4; //整数个数
while (count>0) {
sum?0; //累加和的初值
x?输入一个整数 ;
sum?sum+x;
}
输出 sum;
count?count-1;
sum
count 4
0
1.4.2算法的表示及三种基本结构
(3) 循环结构流程图条件块真 假
【 例 1,3】 求 4个整数的和。
count?4; //整数个数
while (count>0) {
sum?0; //累加和的初值
x?输入一个整数 ;
sum?sum+x;
}
输出 sum;
count?count-1;
sum
count 3
12
x 12
1.4.2算法的表示及三种基本结构
(3) 循环结构流程图条件块真 假
【 例 1,3】 求 4个整数的和。
count?4; //整数个数
while (count>0) {
sum?0; //累加和的初值
x?输入一个整数 ;
sum?sum+x;
}
输出 sum;
count?count-1;
sum
count 3
12
x 12
1.4.2算法的表示及三种基本结构
(3) 循环结构流程图条件块真 假
【 例 1,3】 求 4个整数的和。
count?4; //整数个数
while (count>0) {
sum?0; //累加和的初值
x?输入一个整数 ;
sum?sum+x;
}
输出 sum;
count?count-1;
sum
count 2
21
x 9
1.4.2算法的表示及三种基本结构
(3) 循环结构流程图条件块真 假
【 例 1,3】 求 4个整数的和。
count?4; //整数个数
while (count>0) {
sum?0; //累加和的初值
x?输入一个整数 ;
sum?sum+x;
}
输出 sum;
count?count-1;
sum
count 2
21
x 9
1.4.2算法的表示及三种基本结构
(3) 循环结构流程图条件块真 假
【 例 1,3】 求 4个整数的和。
count?4; //整数个数
while (count>0) {
sum?0; //累加和的初值
x?输入一个整数 ;
sum?sum+x;
}
输出 sum;
count?count-1;
sum
count 1
44
x 23
1.4.2算法的表示及三种基本结构
(3) 循环结构流程图条件块真 假
【 例 1,3】 求 4个整数的和。
count?4; //整数个数
while (count>0) {
sum?0; //累加和的初值
x?输入一个整数 ;
sum?sum+x;
}
输出 sum;
count?count-1;
sum
count 1
44
x 23
1.4.2算法的表示及三种基本结构
(3) 循环结构流程图条件块真 假
【 例 1,3】 求 4个整数的和。
count?4; //整数个数
while (count>0) {
sum?0; //累加和的初值
x?输入一个整数 ;
sum?sum+x;
}
输出 sum;
count?count-1;
sum
count 0
59
x 15
1.4.2算法的表示及三种基本结构
(3) 循环结构流程图条件块真 假
【 例 1,3】 求 4个整数的和。
count?4; //整数个数
while (count>0) {
sum?0; //累加和的初值
x?输入一个整数 ;
sum?sum+x;
}
输出 sum;
count?count-1;
sum
count 0
59
x 15
1.4.2算法的表示及三种基本结构
(3) 循环结构流程图条件块真 假
【 例 1,3】 求 4个整数的和。
count?4; //整数个数
while (count>0) {
sum?0; //累加和的初值
x?输入一个整数 ;
sum?sum+x;
}
输出 sum;
count?count-1;
sum
count 0
59
x 15
显示结果,59
1.4.3 常用算法介绍
1,直接法 2.枚举法 3.递推法解决的问题的种类与复杂程度各不相同决定了算法的多样性，但从其思想方法上可以将其归为以下几种：直接法、枚举法、递推法、递归法、回溯法等等。
本节 将介绍以下三种：
1.4.3 常用算法介绍
1 直接法直接法就是根据问题给出的条件直接求解,前面的很多例子都是这种算法的运用 。 这里不再举例 。
1.4.3 常用算法介绍
2 枚举法枚举法也称 穷举法,基本思想是，在有限范围内 列举所有可能 的结果，找出其中符合要求的解。
枚举法适合求解的问题是：问题可能的答案是有限个且答案是可知的，但又难以用解析法描述。这种算法通常需要用循环结构来完成。
请看下例：
【 例 1,4】 给定一个正整数,判断其非负整数立方根是否存在,若存在,输出该立方根 。
1.4.3 常用算法介绍算法如下：
分析：设某正整数为 27，则非负整数立方根的取值范围为 1—27，因此可在这一范围内对所有整数进行检测，满足立方根为 27的就是所求整数。
【 例 1,4】 求非负整数立方根算法：
1.4.3 常用算法介绍
cube_root?0； //立方根初值
while (cube_root<=num) {
if (cube_root*cube_root* cube_root=num) {
输出 cube_root;
break; //终止循环
else cube_root?cube_root+1;
if (cube_root>num) 输出,无整数立方根”；
num?27；
}
}
【 例 1,4】 求非负整数立方根算法：
1.4.3 常用算法介绍
while (cube_root<=num) {
if (cube_root*cube_root*cube_root=num) {
输出 cube_root;
break; //终止循环
else cube_root?cube_root+1;
if (cube_root>num) 输出,无整数立方根”；
cube_root?1； //立方根初值
num?27；
}
}
num
cube_root
27
1
【 例 1,4】 求非负整数立方根算法：
1.4.3 常用算法介绍
while (cube_root<=num) {
if (cube_root*cube_root*cube_root=num) {
输出 cube_root;
break; //终止循环
else cube_root?cube_root+1;
if (cube_root>num) 输出,无整数立方根”；
cube_root?1； //立方根初值
num?27；
}
}
num
cube_root
27
1
比较
【 例 1,4】 求非负整数立方根算法：
1.4.3 常用算法介绍
while (cube_root<=num) {
if (cube_root*cube_root*cube_root=num) {
输出 cube_root;
break; //终止循环
else cube_root?cube_root+1;
if (cube_root>num) 输出,无整数立方根”；
cube_root?1； //立方根初值
num?27；
}
}
num
cube_root
27
1 c*c*c
比较
【 例 1,4】 求非负整数立方根算法：
1.4.3 常用算法介绍
while (cube_root<=num) {
if (cube_root*cube_root*cube_root=num) {
输出 cube_root;
break; //终止循环
else cube_root?cube_root+1;
if (cube_root>num) 输出,无整数立方根”；
cube_root?1； //立方根初值
num?27；
}
}
num
cube_root
27
2
【 例 1,4】 求非负整数立方根算法：
1.4.3 常用算法介绍
while (cube_root<=num) {
if (cube_root*cube_root*cube_root=num) {
输出 cube_root;
break; //终止循环
else cube_root?cube_root+1;
if (cube_root>num) 输出,无整数立方根”；
cube_root?1； //立方根初值
num?27；
}
}
num
cube_root
27
9
【 例 1,4】 求非负整数立方根算法：
1.4.3 常用算法介绍
while (cube_root<=num) {
if (cube_root*cube_root*cube_root=num) {
输出 cube_root;
break; //终止循环
else cube_root?cube_root+1;
if (cube_root>num) 输出,无整数立方根”；
cube_root?1； //立方根初值
num?27；
}
}
num
cube_root
27
9 c*c*c
比较
【 例 1,4】 求非负整数立方根算法：
1.4.3 常用算法介绍
while (cube_root<=num) {
if (cube_root*cube_root*cube_root=num) {
输出 cube_root;
break; //终止循环
else cube_root?cube_root+1;
if (cube_root>num) 输出,无整数立方根”；
cube_root?1； //立方根初值
num?27；
}
}
num
cube_root
27
9
显示结果,9
【 例 1,4】 求非负整数立方根算法：
1.4.3 常用算法介绍
while (cube_root<=num) {
if (cube_root*cube_root*cube_root=num) {
输出 cube_root;
break; //终止循环
else cube_root?cube_root+1;
if (cube_root>num) 输出,无整数立方根”；
cube_root?1； //立方根初值
num?27；
}
}
num
cube_root
27
9
显示结果,9
【 例 1,4】 求非负整数立方根算法：
1.4.3 常用算法介绍
while (cube_root<=num) {
if (cube_root*cube_root*cube_root=num) {
输出 cube_root;
break; //终止循环
else cube_root?cube_root+1;
if (cube_root>num) 输出,无整数立方根”；
cube_root?1； //立方根初值
num?27；
}
}
num
cube_root
27
9
显示结果,9
1.4.3 常用算法介绍
【 例 1,5】 判断一个正整数是否素数,给出相应结果 。
分析：假设正整数 num,如果 num不是 2，需要检测它是否含有除 1和它本身之外的其他因子，如果有，就不是素数。检测方法是在 2?num-1范围内逐个验证。实际上可以证明在 2?num平方根范围内逐个验证即可。
假定 num为 27，算法如下：
num
1.4.3 常用算法介绍
【 例 1,5】 判断 9是否素数算法
num?27;
if (num=2) 输出,是素数”；
k?sqrt(num)； //平方根取整
else {
while (i<＝ k) {
else i?i+1
if (i>k) 输出,是素数”；else 输出,不是素数”；
i?2;
if (num/i余数为 0) break; //不是素数
}
}
1.4.3 常用算法介绍
【 例 1,5】 判断 9是否素数算法
num?27;
if (num=2) 输出,是素数”；
k?sqrt(num)； //平方根取整
else {
while (i<＝ k) {
else i?i+1
if (i>k) 输出,是素数”；else 输出,不是素数”；
i?2;
if (num/i余数为 0) break; //不是素数
}
}
num 27
1.4.3 常用算法介绍
【 例 1,5】 判断 9是否素数算法
num?27;
if (num=2) 输出,是素数”；
k?sqrt(num)； //平方根取整
else {
while (i<＝ k) {
else i?i+1
if (i>k) 输出,是素数”；else 输出,不是素数”；
i?2;
if (num/i余数为 0) break; //不是素数
}
}
num 27
i 2
k 5
1.4.3 常用算法介绍
【 例 1,5】 判断 9是否素数算法
num?9;
if (num=2) 输出,是素数”；
k?sqrt(num)； //平方根取整
else {
while (i<＝ k) {
else i?i+1
if (i>k) 输出,是素数”；else 输出,不是素数”；
i?2;
if (num/i余数为 0) break; //不是素数
}
}
num 27
i 2
k 5
比较
1.4.3 常用算法介绍
【 例 1,5】 判断 9是否素数算法
num?9;
if (num=2) 输出,是素数”；
k?sqrt(num)； //平方根取整
else {
while (i<＝ k) {
else i?i+1
if (i>k) 输出,是素数”；else 输出,不是素数”；
i?2;
if (num/i余数为 0)
}
}
num 27
i 2
k 5
求余break; //不是素数 不为 0
1.4.3 常用算法介绍
【 例 1,5】 判断 9是否素数算法
num?9;
if (num=2) 输出,是素数”；
k?sqrt(num)； //平方根取整
else {
while (i<＝ k) {
else i?i+1
if (i>k) 输出,是素数”；else 输出,不是素数”；
i?2;
if (num/i余数为 0)
}
}
num 27
i 3
k 5
break; //不是素数
1.4.3 常用算法介绍
【 例 1,5】 判断 9是否素数算法
num?9;
if (num=2) 输出,是素数”；
k?sqrt(num)； //平方根取整
else {
while (i<＝ k) {
else i?i+1
if (i>k) 输出,是素数”；else 输出,不是素数”；
i?2;
if (num/i余数为 0)
}
}
num 27
i 3
k 5
break; //不是素数比较
1.4.3 常用算法介绍
【 例 1,5】 判断 9是否素数算法
num?9;
if (num=2) 输出,是素数”；
k?sqrt(num)； //平方根取整
else {
while (i<＝ k) {
else i?i+1
if (i>k) 输出,是素数”；else 输出,不是素数”；
i?2;
if (num/i余数为 0)
}
}
num 27
i 3
k 5
break; //不是素数 求余 为 0
1.4.3 常用算法介绍
【 例 1,5】 判断 9是否素数算法
num?9;
if (num=2) 输出,是素数”；
k?sqrt(num)； //平方根取整
else {
while (i<＝ k) {
else i?i+1
if (i>k) 输出,是素数”；else 输出,不是素数”；
i?2;
if (num/i余数为 0)
}
}
num 27
i 3
k 5
break; //不是素数
1.4.3 常用算法介绍
【 例 1,5】 判断 9是否素数算法
num?9;
if (num=2) 输出,是素数”；
k?sqrt(num)； //平方根取整
else {
while (i<＝ k) {
else i?i+1
if (i>k)
else 输出,不是素数”；
i?2;
if (num/i余数为 0)
}
}
num 27
i 3
k 5
break; //不是素数输出,是素数,；
比较
1.4.3 常用算法介绍
【 例 1,5】 判断 9是否素数算法
num?9;
if (num=2) 输出,是素数”；
k?sqrt(num)； //平方根取整
else {
while (i<＝ k) {
else i?i+1
if (i>k)
else 输出,不是素数”；
i?2;
if (num/i余数为 0)
}
}
num 27
i 3
k 5
break; //不是素数输出,是素数,；
显示结果：不是素数
1.4.3 常用算法介绍
3.递推法递推算法是通过问题的一个或多个已知解，
用同样的方法逐个推算出其他解，如数列问题以及一些近似计算问题等。通常也要借助于循环。
请看下例：
1.4.3 常用算法介绍
【 例 1,６ 】 求 n!
分析,n!=1?2?3n,因此可以从 1开 始,
由 1!乘以 2得到 2!,再乘以 3得到 3!,以此推出 n!。
假定 n＝ 4，算法如下：
1.4.3 常用算法介绍
【 例 1,６ 】 求 n!算法：
i?2;
n?4;
while (i<=n) {
factorial?factorial*i;
i?i+1;
}
输出 factorial;
factorial?1; //阶乘初值
1.4.3 常用算法介绍
【 例 1,６ 】 求 n!算法：
i?2;
n?4;
while (i<=n) {
factorial?factorial*i;
i?i+1;
}
输出 factorial;
factorial?1; //阶乘初值
factorial 1
i 2
n 4
1.4.3 常用算法介绍
【 例 1,６ 】 求 n!算法：
i?2;
n?4;
while (i<=n) {
factorial?factorial*i;
i?i+1;
}
输出 factorial;
factorial?1; //阶乘初值
factorial 1
i 2
n 4
比较
1.4.3 常用算法介绍
【 例 1,６ 】 求 n!算法：
i?2;
n?4;
while (i<=n) {
factorial?factorial*i;
i?i+1;
}
输出 factorial;
factorial?1; //阶乘初值
factorial 2
i 3
n 4
1.4.3 常用算法介绍
【 例 1,６ 】 求 n!算法：
i?2;
n?4;
while (i<=n) {
factorial?factorial*i;
i?i+1;
}
输出 factorial;
factorial?1; //阶乘初值
factorial 2
i 3
n 4
比较
1.4.3 常用算法介绍
【 例 1,６ 】 求 n!算法：
i?2;
n?4;
while (i<=n) {
factorial?factorial*i;
i?i+1;
}
输出 factorial;
factorial?1; //阶乘初值
factorial 6
i 4
n 4
1.4.3 常用算法介绍
【 例 1,６ 】 求 n!算法：
i?2;
n?4;
while (i<=n) {
factorial?factorial*i;
i?i+1;
}
输出 factorial;
factorial?1; //阶乘初值
factorial 6
i 4
n 4
比较
1.4.3 常用算法介绍
【 例 1,６ 】 求 n!算法：
i?2;
n?4;
while (i<=n) {
factorial?factorial*i;
i?i+1;
}
输出 factorial;
factorial?1; //阶乘初值
factorial 24
i 5
n 4
1.4.3 常用算法介绍
【 例 1,６ 】 求 n!算法：
i?2;
n?4;
while (i<=n) {
factorial?factorial*i;
i?i+1;
}
输出 factorial;
factorial?1; //阶乘初值
factorial 24
i 5
n 4
比较
1.4.3 常用算法介绍
【 例 1,６ 】 求 n!算法：
i?2;
n?4;
while (i<=n) {
factorial?factorial*i;
i?i+1;
}
输出 factorial;
factorial?1; //阶乘初值
factorial 24
i 5
n 4
显示结果,24
1.4.4 算法的时空复杂度
1 时间复杂度 （ Time Complexity）
2 空间复杂度 （ Space Complexity）
解决一个问题的算法往往不止一种,我们总希望选择一个较好的算法 。 算法的指标中有一项是效率,
指占用计算机资源情况,包括 执行程序消耗的时间 和占用的存储空间 （ 主要指辅助存储器 ） 两个方面,这两方面分别用以下两个概念进行描述 。
1.4.4 算法的时空复杂度程序在计算机中执行所消耗的时间取决于以下因素：
（ 1） 输入输出数据的总量；
（ 2） 编译及指令执行速度；
（ 3） 指令数量；
从算法选择的角度，执行时间取决于算法的指令数量，
其中指令的重复执行次数所起的影响作用最大 。
空间复杂度
1.4.4 算法的时空复杂度频度,语句重复执行的次数定义：
执行时间函数,频度 n的函数 F(n)称为程序的执行时间函数，用来表示时间复杂度。
计算机执行速度极快，有限的指令数量差异不能反映执行时间的快慢。我们理解 执行时间不同 指的是当频度 n?∞ 时，
F(n)的变化趋势明显不同。
执行时间函数的阶,设有另一个 n的函数 G(n)，当
n?∞ 时,F(n)/G(n)?常数，就称 F(n)是 G(n)阶的，
记为 F(n)=O(G(n))。通常用执行时间函数的阶对算法执行时间进行比较。
请看下例：
1.4.4 算法的时空复杂度
sum?0; i?0;
while(i<n) { //频度为 n
x?输入数据 ; //频度为 n
sum?sum+x; //频度为 n
i?i+1; //频度为 n
}
输出 sum;
F(n)=n+n+n+n=4n，当 n?∞ 时,F(n)/ n?4，所以 F(n)是 n阶的。
1.4.4 算法的时空复杂度在有些情况下，算法的执行时间不仅与算法有关，
还和处理的数据集合有关，比如对数据排序，原始数据杂乱无章和原始数据已经有序两种情况执行时间差别甚至会很大。对这种情况，通常按照最坏情况估算时间复杂度，有时也在某种约定下（如等概率）估算平均时间复杂度。
常用算法时空复杂度的阶有：
常数阶、对数阶、线性阶、平方阶、立方阶、指数阶等。按这个顺序描述的算法，时间复杂度是从优到劣的。
1.4.4 算法的时空复杂度一个程序在运行时所占用的存储空间大小通常也是问题规模的函数,和时间复杂度类似,这个函数就称为 空间复杂度 。
关于空间复杂度的计算这里不详细介绍,可参阅数据结构及其他相关书籍 。
空间复杂度
1.4.4 算法的时空复杂度我们总希望一个算法能够既执行得快,又占用较少的空间,但实际上这两个方面往往是一个矛盾,
所以要根据所解决问题的要求和计算机的特点进行选择 。
1.5 C语言与面向对象的 C＋＋
C语言是七十年代初贝尔实验室的 Dennis Richie
等人在 B语言基础上开发出来的 。 C最初是作为
UNIX操作系统的开发语言为人们所认识 。 七十年代末,随着微型计算机的发展,C语言开始移植到非
UNIX环境中,并逐步脱离 UNIX系统成为一种独立的程序设计语言 。 C 语言版本很多,为了让开发出来的代码能够在多种平台上运行,1988年美国国家标准协会 ANSI对 C语言进行了标准化,产生了 ANSI
C。
1.5 C语言与面向对象的 C＋＋
（ 1） C语言既具备高级语言的结构和编程环境,又提供类似于汇编语言那样的系统资源操纵能力及程序执行效率 。 适合解决有实时要求的问题 。
C语言的主要特点：
（ 2） 有丰富的运算符和数据类型,表达式类型多样化,可以方便地实现在其他语言中较难实现的运算,对各种不同类型的程序设计都有良好的适应性 。
（ 3） 以函数为基础实现程序的结构化设计,支持大型程序的多文件构成及单个文件独立编译,适合大型复杂程序的设计 。
（ 4） 语言简洁,紧凑,使用方便,灵活,书写形式自由 。
（ 5） 可移植性好 。
1.5 C语言与面向对象的 C＋＋
C++是由 C发展成为的以面向对象为主要特征的语言 。 作为
C语言的超集,C++继承了 C的所有优点,又对数据类型做了扩充,使得编译系统可以检查出更多类型错误 。
C++支持面向对象程序设计，通过类和对象的概念把数据和对数据的操作封装在一起，通过派生、继承、重载和多态性等特征实现了软件重用和程序自动生成，使得大型复杂软件的构造和维护变得更加有效和容易。
此外，在一致性（ Consistency）检查机制方面也作了加强，
提高了软件开发的效率和质量。
1.5 C语言与面向对象的 C＋＋
C++与 C完全兼容,很多用 C编写的库函数和应用程序都可以为 C++所用 。
但正是由于与 C兼容,使得 C++不是纯正的面向对象的语言,
它既支持面向对象程序设计,也支持面向过程设计 。 但我们应当注意用面向对象的思想进行设计,以发挥出 C++的优势 。
C++有许多版本,国内较为流行的有 Microsoft公司的 Visual
C++。
1.6 一个简单的 C++程序
// 程序文件名为 EX1_6.cpp
/* C++程序基本结构 */
# include <iostream.h>
max(int i,int j) { //A
if (i>=j) return i;
else return j;
}
void main(void) { //B
cout<<″输入 i,j,″; //显示提示信息
int i,j; //说明变量
cin>>i>>j; //从键盘上输入变量值
cout<<″max number is:″<<max(i,j)<<′ \n ′; //输出提示和结果
}
【 例 1,7】 一个简单的 C++程序。
程序组成：
注释编译预处理指令程序体由若干函数组成，其中有且仅有一个主函数
main（），这是程序的执行入口。在 MFC编程中定义为 winmain（）。
