第二章 算法.ppt

第二章程序的灵魂--算法
一个程序应包括以下两个方面:
1)对数据的描述。在程序中要指定数据的类型
和数据的组织结构。
2)对操作的描述。即操作步骤,也就是算法。
著名计算机科学家沃思提出:程序=数据结构+算法
程序=算法+数据结构+程序设计方法+语言工具和环境
§ 算法的概念
计算机算法分为两类:
数值运算算法:目的是求数值解。
非数值运算算法:事务管理(人事、档案)
§ 简单的算法举例
例1:1×2×3×4×5
[算法]
S1: p=1
S2: i=2
S3: p×ip
S4: i+1i
S5: i<=5 转到S3,否则输出p的值,终止算法。
模仿例1 :写出计算
s=1+2+3+…+100的算法
§ 算法的特征
1、有穷性
2、确定性
3、有零个或多个输入
4、有一个或多个输出
5、有效性
例1:
1×2×3×4×5
S1: p=1
S2: i=2
S3: p×ip
S4: i+1i
S5: i<=5 转到S3,
否则输出p的值,
终止算法。
§ 怎样表示一个算法
一、用自然语言表示算法
日常用语
二、用流程图表示算法
起止框输入输出框
判断框处理框
或流程线连接点
注释框
开始
1t
2i
t×it
i+1i
i>5
结束
yes
no
输出p
计算:1×2×3×4 ×5
画一个计算1+2+3+…+100的流程图
三、三种基本结构和改进的流程图
1、传统流程图的弊端
2、三种基本结构
顺序结构:最简单的一种结构
成立不成立成立不成立

顺序结构选择结构(1) 选择结构(2)
选择结构
其中 A、B是一个处理过程,P是一个条件
A
B
P
A
B
P
A
把这两种结构图自己画出来。
循环结构
当型循环
直到型循环


不成立

成立成立
不成立
当型循环直到型循
A可以是一条或多条语句或三个基本结构之一。
P1
A
A
P2
把着两个结构图自己画出来
以上三种结构的共同点:
1、只有一个入口
2、只有一个出口
3、结构内的每一部分都有机会被执行到。
4、结构内不存在“死循环”
四、用N-S流程图表示算法
1、顺序结构 2、选择结构
成立不成立
A
B
P
A
B
3、循环结构
当型循环直到型循环
当P1成立
直到P1成立
A可以是一条或多条语句或三个基本结构之一。
例1: 1×2×3×4×5的N-S图
直到i>5
A
A
1t
2i
t×it
i+1i
打印t
模仿例1画出计算 1+2+3+4+5 的N-S图来
N-S图的优点:
1、比传统流程图紧凑易画
2、上下顺序就是程序执行的顺序
五、用计算机语言表示算法
设计程序的基本过程: (记下来)
分析问题设计算法描述算法编写程序
例如:计算 1×2×3×4×5
1t
2i
t×it
i+1i
打印t
1、分析问题:用累乘的方法
2、设计算法:设两个变量,t、i。让t保存积,
3、描述算法:可以用N-S图
直到i>5