第 2章 程序的灵魂 — 算 法算法是灵魂，数据结构是加工对象语言是工具，编程要有合适的方法程序包括,数据的描述 和 操作的描述算法解决的是,做什么,和,怎么做,的问题程序 = 数据结构 + 算法程序 =数据结构 +算法 +程序设计方法 +语言工具和环境
1.算法的概念
2.算法的特性
3,算法的表示
4.结构化程序设计方法本章内容算法的概念
1.算法的概念广义地讲 --算法是为完成一项任务所应当遵照的一步一步的规则的、精确的、无歧义的描述，它的总步数是有限的。
狭义地讲 -- 算法是解决一个问题采取的方法和步骤的描述。
2.算法的描述日常自然语言伪代码（自然语言与程序设计语言相结合）
流程图 (传统流程图,N—S流程图）
程序设计语言例 1：交换两个变量 a,b的值算法：⑴ a=>t
⑵ b=>a
⑶ t=>b
例 2,打印 50个学生中成绩高于 80分的学生学号（ Ni表示学号,Gi表示成绩 ）
(1) i=1
(2) 如果 Gi>80 则 打印 Ni Gi
(3) i=i+1
(4) 如果 i<=50，返回 (2)继续执行；否则，算法结束
3,简单的算法举例算法的特性
1,有穷性
2,确定性
3,有效性
4,有 0个或多个输入
5,有一个或多个输出怎样表示一个算法
1.用自然语言表示算法
2.传统流程图处理框起止框 I/O框 判断框流程线 连接点传统流程图中的基本符号三种基本结构的表示条件语句 1 语句 2
Y N语句 1
语句 2
（ 2）选择结构
3.改进的流程图
（ 1）顺序结构
（ 3）循环结构
a) 当型循环 While b) 直到循环 Until
条件语句
Y
N
条件语句
N
Y
三种基本结构的特点：
（ 1）只有一个入口
（ 2）只有一个出口
（ 3）结构内的每一部分都有机会被执行到
（ 4）结构内不存在死循环
N<10
Max =AN=1
A>=Max
Max =A
输入 A
开始再输入 A
N=N+1 打印 Max
结束
YN
N
Y
例,从 10个数中选出最大的数的流程图
4,N-S流程图将全部算法写在一个矩形框内，在矩形内还可包含其它从属于它的框。
三种基本结构的 N—S图表示：
语句 A
语句 B
1、顺序结构语句 1
语句 2
2、选择结构条件语句 1 语句 2
Y N
语句 A 语句 B
条件Y N
3.循环结构
a) 当型循环语句组当条件成立 条件语句
Y
N
b) 直到循环语句组直到当条件成立条件语句
N
Y
例,从 10个数中选出最大的数的 N-S 流程图传统流程图
N<10
Max =AN=1
A>Max
Max =A
输入 A
开始再输入给 A
N=N+1 打印 Max
结束
YN
N
Y
N-S流程图输入 A
当 N<=10
Max =A
N=N+1
打印 Max
输入 A,Max＝ A,N＝ 1
A>Max YN
5,用伪代码表示伪代码是介于自然语言和计算机语言之间的文字和符号来表示算法。如同一篇文章，自上而下地写下来。
例,打印 x的绝对值,的算法描述 If x is positive then
print x
Else
print -x
6,用计算机语言表示算法
main( )
{ int max,n,a;
n=1;
scanf(“%d”,&a);
max=a;
while (n<=10)
{ scanf(“%d”,&a);
if (max<a) max=a;
n=n+1;
}
printf(“Max=%d\n”,max);
}
只有用计算机编写的程序才能被计算机执行（先编译连接）
当型循环结构化程序设计方法用计算机解决问题的过程提出、分析问题确定算法模型设计算法编写程序调试程序分析输出结果正确合理结束结构化程序设计方法的基本思路是把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。
结构化程序设计思想自顶向下、逐步细化、模块化设计、结构化编码自顶向下：先从全局整体设计。
逐步细化：将一个问题分解成几个较小问题解决。
模块化设计：将一个大任务分解成若干个较小的部分，每 个部分承担一定功能，称为功能模块。
结构化编码,用高级语言正确实现三种基本结构。
输入 1000个数存入 X1，
x2,……x 1000
打印 x1…..x 1000中不等于 0的数
S1
N-S流程图让 X1，
x2,……x 1000中的非素变为 0
S3
S2
输入 xi
当 i<=1000
i=i+1
i=1
xi≠0
当 i<=1000
i=i+1
i=1
YN
打印 xi
例：给 1000个整数，打印输出其中的素数输入 1000个数存入 X1，
x2,……x 1000
打印 x1…..x 1000中不等于 0的数
S1
N-S流程图让 x1,……x 1000中的非素变为 0
S3
S2
判断 xi是否是素数，
若不是则将 xi=0
当 i<=1000
i=i+1
i=1
r=0
r=x1除 j的余数
j=j+1
j=2
YN
xi=0
S21
直到 j>xi/2
输入 xi
当 i<=1000
i=i+1
i=1
当 i<=1000
i=1
r=0
r =xi%j
j=j+1
j=2
YN x
i=0
直到 j>xi/2
i=i+1
xi≠0
当 i<=1000
i=i+1
i=1
YN
打印 xi
输入 1000个数存入 X1，
x2,……x 1000
打印 x1…..x 1000中不等于 0的数让 x1,……x 1000
中的非素变为 0
细化后的流程图习题：
P37 2.4（ 1）（ 4）（ 5）,2.5
要求：
将对应的流程图和 N-S图画在一起
1.算法的概念
2.算法的特性
3,算法的表示
4.结构化程序设计方法本章内容算法的概念
1.算法的概念广义地讲 --算法是为完成一项任务所应当遵照的一步一步的规则的、精确的、无歧义的描述，它的总步数是有限的。
狭义地讲 -- 算法是解决一个问题采取的方法和步骤的描述。
2.算法的描述日常自然语言伪代码（自然语言与程序设计语言相结合）
流程图 (传统流程图,N—S流程图）
程序设计语言例 1：交换两个变量 a,b的值算法：⑴ a=>t
⑵ b=>a
⑶ t=>b
例 2,打印 50个学生中成绩高于 80分的学生学号（ Ni表示学号,Gi表示成绩 ）
(1) i=1
(2) 如果 Gi>80 则 打印 Ni Gi
(3) i=i+1
(4) 如果 i<=50，返回 (2)继续执行；否则，算法结束
3,简单的算法举例算法的特性
1,有穷性
2,确定性
3,有效性
4,有 0个或多个输入
5,有一个或多个输出怎样表示一个算法
1.用自然语言表示算法
2.传统流程图处理框起止框 I/O框 判断框流程线 连接点传统流程图中的基本符号三种基本结构的表示条件语句 1 语句 2
Y N语句 1
语句 2
（ 2）选择结构
3.改进的流程图
（ 1）顺序结构
（ 3）循环结构
a) 当型循环 While b) 直到循环 Until
条件语句
Y
N
条件语句
N
Y
三种基本结构的特点：
（ 1）只有一个入口
（ 2）只有一个出口
（ 3）结构内的每一部分都有机会被执行到
（ 4）结构内不存在死循环
N<10
Max =AN=1
A>=Max
Max =A
输入 A
开始再输入 A
N=N+1 打印 Max
结束
YN
N
Y
例,从 10个数中选出最大的数的流程图
4,N-S流程图将全部算法写在一个矩形框内，在矩形内还可包含其它从属于它的框。
三种基本结构的 N—S图表示：
语句 A
语句 B
1、顺序结构语句 1
语句 2
2、选择结构条件语句 1 语句 2
Y N
语句 A 语句 B
条件Y N
3.循环结构
a) 当型循环语句组当条件成立 条件语句
Y
N
b) 直到循环语句组直到当条件成立条件语句
N
Y
例,从 10个数中选出最大的数的 N-S 流程图传统流程图
N<10
Max =AN=1
A>Max
Max =A
输入 A
开始再输入给 A
N=N+1 打印 Max
结束
YN
N
Y
N-S流程图输入 A
当 N<=10
Max =A
N=N+1
打印 Max
输入 A,Max＝ A,N＝ 1
A>Max YN
5,用伪代码表示伪代码是介于自然语言和计算机语言之间的文字和符号来表示算法。如同一篇文章，自上而下地写下来。
例,打印 x的绝对值,的算法描述 If x is positive then
print x
Else
print -x
6,用计算机语言表示算法
main( )
{ int max,n,a;
n=1;
scanf(“%d”,&a);
max=a;
while (n<=10)
{ scanf(“%d”,&a);
if (max<a) max=a;
n=n+1;
}
printf(“Max=%d\n”,max);
}
只有用计算机编写的程序才能被计算机执行（先编译连接）
当型循环结构化程序设计方法用计算机解决问题的过程提出、分析问题确定算法模型设计算法编写程序调试程序分析输出结果正确合理结束结构化程序设计方法的基本思路是把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。
结构化程序设计思想自顶向下、逐步细化、模块化设计、结构化编码自顶向下：先从全局整体设计。
逐步细化：将一个问题分解成几个较小问题解决。
模块化设计：将一个大任务分解成若干个较小的部分，每 个部分承担一定功能，称为功能模块。
结构化编码,用高级语言正确实现三种基本结构。
输入 1000个数存入 X1，
x2,……x 1000
打印 x1…..x 1000中不等于 0的数
S1
N-S流程图让 X1，
x2,……x 1000中的非素变为 0
S3
S2
输入 xi
当 i<=1000
i=i+1
i=1
xi≠0
当 i<=1000
i=i+1
i=1
YN
打印 xi
例：给 1000个整数，打印输出其中的素数输入 1000个数存入 X1，
x2,……x 1000
打印 x1…..x 1000中不等于 0的数
S1
N-S流程图让 x1,……x 1000中的非素变为 0
S3
S2
判断 xi是否是素数，
若不是则将 xi=0
当 i<=1000
i=i+1
i=1
r=0
r=x1除 j的余数
j=j+1
j=2
YN
xi=0
S21
直到 j>xi/2
输入 xi
当 i<=1000
i=i+1
i=1
当 i<=1000
i=1
r=0
r =xi%j
j=j+1
j=2
YN x
i=0
直到 j>xi/2
i=i+1
xi≠0
当 i<=1000
i=i+1
i=1
YN
打印 xi
输入 1000个数存入 X1，
x2,……x 1000
打印 x1…..x 1000中不等于 0的数让 x1,……x 1000
中的非素变为 0
细化后的流程图习题：
P37 2.4（ 1）（ 4）（ 5）,2.5
要求：
将对应的流程图和 N-S图画在一起
