梯形法
抛物线法
2. 非数值算法 包括排序，查找，图形操作等问题。 例如排序问题，N个整数排序。
§2.2 算法举例
1 简单算法
求和：1+2+3……+100 1：S=0 2：i=1 3：S+i的值给S 4：i+1的值给i 5： 判断i<=100，如果i<=100执行3，4，5，否则算
法结束。 6：打印S的值
输入n
1=>i
当i<=n
i=>xi 1+i=>i
B:
B1
将x1去掉（ 使x1 =0）
B2
2=>i
当i<=sqrt(n)
B3
如xi未去掉，则将 xi+1到xn间全部是xi
倍数的数去掉
1+i=>i
F: Y xj=0
N
Y N xj能被 xi整除
xj=0
D:
xi=0
Y
N
将xi+1到xn间
D
E 是xi倍数的数
2次扫描 ：1 3 7 4 9 5
3次扫描 ：1 3 4 7 9 5 4次扫描 ：1 3 4 5 9 7 5次扫描 ：1 3 4 5 7 9
§2.3 算法的性质
1.有穷性 操作步骤是有限的，不能无限。
2.确定性 算法中每一个步骤都是明确的,不能是模糊的
3.有零个或多个输入 可以从外界输入必要的信息.
（2）单个模块易于编写，查错，调试和修改。
（3）一个模块可以在多个地方供多个程序用， 提高编程效率。
（4）整个程序功能的修改和差错，可局限在某 一模块内进行而不考虑其它模块。
（5）适于“自顶而下”的设计
2.分解模块的原则 （1）简明性（单功能度） 每一模块应简单易懂，易于实现，且模块仅执行一种功能。 （2）独立性
2.三种基本结构
1966年 Bohra Jacopini 提出三种结构： （1）顺序结构 （2）选择结构（选取结构，分支结构） （3）循环结构
A B
顺序结构
p Y
A
N B
选择结构
A
p
Y
N
A
p N
Y
“当型”循 环
While •只有一个入口
“直到型”循 环
Until
•只有一个出口
•结构的每一部分都可能被执行到
4.有一个或多个输出 输出解或结果，没有输出的算法是没有意义的。 5.有效性
每一步能有效执行，并得到确定的结果。
§2.4 算法的表示
2.4.1用自然语言表示算法 2.4.2用流程图表示 1.ANSI表示
起止框
输入输出框 判断框 处理框
↓ → 或
流程线
○ 连接点
[ ----
注释框
特点：直观形象，清晰易懂，易于找错，但必须限制 箭头的滥用
要求各模块相对独立，修改其中某一模块而不影响其它模块，减 少各模块间数据联系。
(3)完整性 每一个模块独立完整，不要求一个模块完成多种功能，也不要求
多个模块完成一个功能。 （4）一进一出原则
单个入口和单个出口。 （5）模块大小
100行左右（2页），分解基本功能即可。
例：将1到1000之间的素数打印出来。
•结构不存在“死”循环
开始
0=>s，1= Байду номын сангаасi
I<=100?
N 输出s
i+1=>i s+i=>s
Y
结束
s=1+2+……+100 算法流程图
2.4.3 N-S流程图
1973年，美国 I，Nassi.B.Shneiderman 提出了一种 新的流程图形式。
1.N-S流程图的流程图符号 ①顺序结构 ②选择结构 ③循环结构
第2章 算 法
烟台大学 机电汽车工程学院
刘鹏
程序=数据结构+算法
数据结构是指数据的类型和数 据的组成形式：诸如线性表， 集合，树，图。
算法是用计算机解决某一问题 的方法步骤。
§2.1算法的概念
算法是解决一个问题而采取的方法和步骤。这里仅限于计算机算 法，用计算机解决某一问题而用的方法和步骤。
2.1.1计算机算法分类 1. 数值运算算法 （《数值分析》《数值方法》） ①例如 数值积分： ②线性方程组的求解： 如果|A|≠0。
去掉
E:
i+1=>j
当j<=n
将能被 xi整除的
xj去掉
F
j+1=>j
C:
G:
1=> i
当i<=n
xi=0
Y
N
把未去掉的xi打印出来
G
1+i=>i
打印xi
例2.3 2.5 2.13 2.14 2.15 将例题吃透
作业：2.4 (3) (6) (8)
（1）问题分析。
算法采用 Eratosthenes（埃拉托色尼）筛法.就将 1-1000间的非素数挖掉。其余是素数。
（2）因此，选择数据结构，可以用数组，或不用数组， 未挖掉数立即打印出来；
（3）C 语言开发平台
（4）采用结构化编程； 算法：进行细化
A
输入1~n
B
把所有的非素数去掉
C
打印全部素数
A:
程序
子程序1
子程序 2 子程序3 子程序4
程序按功能模块划分为若干基本模块（子过程）， 每个子过程具有一定的功能，这些过程通过参数传 递数据。数据和过程分离为相对独立的实体。
如下图：
数据1
数据2
过程1
数据3
数据4
过程3
结构化方法
过程2
模块化原则
1.模块化的优点：
（1）对于大型程序系统便于分工编写可缩短编 程时间。
这就是一个简单的算法，i，S各占用一个存储单元。
2 排序问题 将1 4 7 3 9 5从小到大排序
（1）冒泡排序 ：从左向右，相邻两个数进 行比较，如果逆序则交换位置 1次扫描 ：1 4 3 7 5 9 2次扫描 ：1 3 4 5 7 9
（2）选择排序 ：从左向右，依次取数与后 面的数进行比较，如果逆序则交换位置 1次扫描 ：1 4 7 3 9 5
A B
当P成立
A
YPN AB
A
直到P成立
0=>s
1=>i
当P成立
s=s+i i=1+i
输出s
§2.5结构化程序设计方法
1自顶向下
2逐步细化
3模块化设计
4结构化编码。
“自顶向下，逐步细化”是一种系统分解的方法。根据 需要解决的问题，对问题根据功能进行系统的分类。将 一个大的复杂的系统解成若干子系统，每一个子系统完 成原系统的某一项或多项功能。同时每一子系统又可划 分若干子系统，就像树根，逐步细化，进入第二层，第 三层……设计。