1
2009-7-29
第一章 算法进行程序设计，需要具备两方面知识：⑴掌握一门计算机语言； ⑵掌握解题的方法和步骤 。
§ 1 算法的概念及特征
§ 2 算法的表示
2
2009-7-29
§ 1 算法的概念及特征 (p1-5)
不论是计算机还是人，要完成一项工作都是按照一定的工作步骤进行的。
例如，去商业大厦买东西，可以按照下面步骤进行：
①到西校门；②乘 106路公交车；③到“商业大厦”站点下车；④进大厦买东西。
又如，到食堂吃饭，要按照以下步骤进行：
①带上饭碗走进食堂排队；②买饭付钱；③到餐桌吃饭。
一、算法的基本概念
3
2009-7-29
上述两个例子说明，无论完成什么任务，都有一定的方法和具体步骤。
算法 (Algorithm)是为解决某个问题而采取的方法和步骤。
对于同一个问题可以采用不同的方法和步骤 (即可以有不同的算法 )，但应选择最佳的方案。
100
1k
ksu m
【 例 1】 计算
§ 1 算法的概念及特征方法一,先进行 1＋ 2、再加 3、再加 4,…,加到 100为止。（做 99次加法）
4
2009-7-29
方法二,100＋ (1＋ 99)＋ (2＋ 98)＋ … ＋ (49＋ 51)
＋ 50=100＋ 49× 100＋ 50=5050。 （ 1次乘法,2
次加法）
……
此例说明：解决问题的算法有优劣之分。算法的优劣是程序设计中一个极为重要的问题,不仅要保证算法正确，而且要考虑算法的质量（方法简单、运算步骤少） 。
§ 1 算法的概念及特征二、计算机算法的分类
5
2009-7-29
分为 数值运算算法 和 非数值运算算法 两大类。
数值运算算法,求问题 数值解 所用的算法。例如求方程组的解、求函数的定积分等所用的算法都是数值运算算法。
非数值运算算法,求问题 非数值解 所用的算法，
它涉及的面比数值运算算法更广。例如在网络搜索引擎、图书检索、人事管理、行车调度等领域中的算法都是非数值运算算法。
§ 1 算法的概念及特征
6
2009-7-29
【 例 2】 计算 5!=1× 2× 3× 4× 5
约定,用 s1,s2,…,sn表示算法的第 1、第 2,…,
第 n步。
实现思想,设 A,B两个变量，其中 A代表被乘数,B代表乘数。每一步的乘积结果存放在 A中。另外，用循环表示每一步的乘积运算。
具体算法如下：
s1：使 A = 1（初值）
s2：使 B = 2（初值）
s3,A× B?A（ A与 B的积存放于 A中）
s4,B＋ 1?B（ B的值增 1）
s5：如果 B≤5，返回重新执行 s3,s4,s5；否则，
算法结束,A的值为 5！。
§ 1 算法的概念及特征三、简单算法举例
7
2009-7-29
1 A
2 B
A× B A
B+1 B
B﹥ 5? 算法结束是否计算 5!的算法示意图
§ 1 算法的概念及特征
8
2009-7-29
【 例 3】 计算 N!（ N为任意正整数）。
s1,输入 N
s2,使 A = 1（初值）
s3,使 B = 2（初值）
s4,A× B?A（ A与 B的积存放于 A中）
s5,B＋ 1?B（ B的值增 1）
s6,如果 B≤N，返回重新执行 s4,s5,s6；否则，算法结束,A值为 N!。
§ 1 算法的概念及特征
9
2009-7-29
是是否否
【 例 4】 将 2000～ 2500年中的闰年打印出来。
闰年的条件是,⑴ 能被 4整除，但又不能被 100整除的年份是闰年； ⑵ 能被 100整除，又能被 400整除的年份是闰年。
设年份为 Y,否Y被 4整除？是
Y被 100整除？
闰年非闰年
Y被 400整除？
闰年 非闰年
§ 1 算法的概念及特征
10
2009-7-29
具体算法如下：
S1,2000?Y
S2,若 Y不能被 4整除，则打印 Y“不是闰年”，然后转到 S5。
S3,若 Y能被 4整除，但不能被 100整除，则打印 Y“是闰年”，然后转到 S5。
S4,若 Y能被 100整除，又能被 400整除，则打印 Y“是闰年”；否则打印“不是闰年”。
S5,Y+1?Y
S6,若 Y≤2500时，转 S2继续执行；否则算法结束。
§ 1 算法的概念及特征
11
2009-7-29
⒈ 有穷性,一个算法应包含有限的操作步骤，而不能是无限的。例如：不能有死循环。
⒉ 确定性,算法的含义应当是确定的、唯一的，而不应产生“歧义性”。例如，,100被一个整数除”是不确定的，它没有说明“这个整数”具体是多少。
⒊ 有零个或多个输入,可以没有输入。
⒋ 有一个或多个输出,至少有一个输出结果。
⒌ 有效性,算法中的每一步骤都应当能有效地执行，
并得到确定的结果。例如：如果设 B＝ 0，则 A÷ B就是无效的。
四、算法的特征 (或特点 )
§ 1 算法的概念及特征
12
2009-7-29
常用的算法表示方法有：自然语言法,流程图法,伪代码法,PAD图法等。
自然语言法,用人类语言或其他文字表示算法。
如前面的例 1～例 4。
优点：通俗易懂。
缺点：文字冗长、繁琐，含义不严格（确定性不佳）。
流程图,用一些图框来表示算法的步骤。 (重点 )
§ 2 算法的表示 (p6-23)
13
2009-7-29
常用的算法表示方法有：自然语言法,流程图法,伪代码法,PAD图法等。
伪代码 (pseudo code)法,用 介于自然语言和计算机语言之间 的文字和符号来描述算法。
PAD图法,即问题分析图 (Problem Analysis
Diagram)，是在软件开发中用到的一种表示算法的图形工具。
流程图 包括,传统流程图,结构化流程图,N-S
流程图 三种。
§ 2 算法的表示
14
2009-7-29
ANSI规定了一些常用的流程图符号 (见教材图 1.3)。
一、传统流程图
§ 2 算法的表示起止框输入输出框判断框处理框流程线或连接点注释框
15
2009-7-29
【 例 3】 计算 N!（ N为任意正整数）。
§ 2 算法的表示
s1,输入 N
s2,使 A = 1
s3,使 B = 2
s4,A× B?A
s5,B＋ 1?B
s6,如果 B≤N，返回重新执行 s4,s5,s6；否则,A值为 N!，输出 A值，
算法结束。
输入 N
开始
1?A
2?B
A× B?A
B＋ 1?B
B>N?
输出A(N!)
是结束否
16
2009-7-29
一个流程图主要包括：⑴表示相应操作的图框；
⑵带箭头的流程图；⑶图框内外相应的文字说明。
传统流程图的优缺点优点,直观形象、图框间的逻辑关系清楚。
缺点,对流程线的使用没有限制。 因此，使用者可以不受限制地使流程任意地转来转去，使流程图变得毫无规律，使人难以理解算法的逻辑。
§ 2 算法的表示结构化流程图
17
2009-7-29
基本思路,由基本结构构成算法流程图，只在基本结构内才存在 分支 和 向前 \向后的跳转,从而限制流程线的滥用。
1966年,Bohra和 Jacopini提出了三种基本结构,顺序结构,选择结构,循环结构 。
⑴ 顺序结构按流程线先后顺序执行算法中的各图框。
二、结构化流程图
§ 2 算法的表示顺序结构示意图
B
A
18
2009-7-29
⑵ 选择结构根据判断框中的条件 P是否成立选择执行 A或 B。
注,A或 B两个框中可以有一个是空，即不执行任何操作。
§ 2 算法的表示选择结构示意图
A
P
B
成立 不成立
A
P
19
2009-7-29
⑶ 循环结构包括两种类型,当型循环,直到型循环 。
当型 (While型 )循环当型循环示意图成立
P1
循环体不成立
§ 2 算法的表示当条件 P1成立时，执行循环体；
再判断条件 P1，若成立，再执行循环体；
… 如此反复 … ；
直到当条件 P1不成立时，则退出循环结构。
特点：① 先判断后执行 ；
② 当条件 P1成立时执行循环体，条件 P1是执行循环的条件 。
20
2009-7-29
⑶ 循环结构包括两种类型,当型循环,直到型循环 。
直到型 (Until型 )循环直到型循环示意图成立
P2
循环体不成立先执行循环体；
然后判断条件 P2，若不成立，再执行循环体；
然后再判断条件 P2，若仍然不成立，
则再执行循环体；
… 如此反复 … ；
直到条件 P2成立，则退出循环结构。
特点：① 先执行后判断 ；
② 当条件 P2不成立时执行循环体，条件 P2是退出循环的条件 。
§ 2 算法的表示
21
2009-7-29
【 例 3】 计算 N!（ N为任意正整数）。
输入 N
开始
1?A
2?B
A× B?A
B＋ 1?B
B>N?
输出A(N!)
是结束否直到型循环输入 N
开始
1?A
2?B
A× B?A
B＋ 1?B
B≤N?
输出A(N!)
是结束否 当型循环
22
2009-7-29
当型循环和直到型循环小结：
当型循环是 先判断后执行 ；
直到型循环是 先执行后判断 。
当型循环中条件 P1是执行循环的条件，故 条件成立时执行循环体 ；
直到型循环中条件 P2是退出循环的条件，故 条件不成立时执行循环体 。
当型循环和直到型循环的条件 P1和
P2互为逆条件 。
当型循环中条件不成立时循环体不执行，而 直到型循环的循环体至少执行一次 。
故，如果没有至少执行一次循环体的要求时，最好选用当型循环。 直到型循环示意图成立
P2
循环体不成立当型循环示意图成立
P1
循环体不成立
§ 2 算法的表示
23
2009-7-29 § 2 算法的表示由上述顺序结构、选择结构、循环结构三种基本结构所构成的算法为 结构化算法 ；所对应的流程图称为 结构化流程图 ；用计算机语言设计结构化算法，称为 结构化程序设计 。
三,N-S流程图在结构化流程图基础上,1973年美国学者 I,
Nassi和 B,Shneiderman提出了一种新的流程图形式，称为 N-S流程图，又称盒图 (box diagram)。
在 N-S流程图中,完全去掉了流程线，三种基本结构均用矩形框来表示 。
24
2009-7-29
⑴ 顺序结构
B
A
B
A
⑵ 选择 结构
A
P
B
成立 不成立
§ 2 算法的表示
P成立
A B
成立 不
25
2009-7-29
⑶ 循环 结构
当型 (While型 )循环
直到型 (Until型 )循环成立
P1
循环体不成立成立
P2
循环体不成立
§ 2 算法的表示当 P1
循环体直到 P2
循环体
26
2009-7-29
【 例 3】 计算 N!（ N为任意正整数）。
输入 N
开始
1?A
2?B
A× B?A
B＋ 1?B
B≤N?
输出A(N!)
是结束否 A× B?A
B＋ 1?B
当 B≤N
2?B
1?A
输入 N
输出 A（ N!）
27
2009-7-29
N-S流程图的特点：
没有起止框，没有流程线；
其余流程图符号均以矩形框形式表示；
在一个基本结构中还可以包含另一个基本结构
（如教材 p19图 1.48）。
§ 2 算法的表示
2009-7-29
第一章 算法进行程序设计，需要具备两方面知识：⑴掌握一门计算机语言； ⑵掌握解题的方法和步骤 。
§ 1 算法的概念及特征
§ 2 算法的表示
2
2009-7-29
§ 1 算法的概念及特征 (p1-5)
不论是计算机还是人，要完成一项工作都是按照一定的工作步骤进行的。
例如，去商业大厦买东西，可以按照下面步骤进行：
①到西校门；②乘 106路公交车；③到“商业大厦”站点下车；④进大厦买东西。
又如，到食堂吃饭，要按照以下步骤进行：
①带上饭碗走进食堂排队；②买饭付钱；③到餐桌吃饭。
一、算法的基本概念
3
2009-7-29
上述两个例子说明，无论完成什么任务，都有一定的方法和具体步骤。
算法 (Algorithm)是为解决某个问题而采取的方法和步骤。
对于同一个问题可以采用不同的方法和步骤 (即可以有不同的算法 )，但应选择最佳的方案。
100
1k
ksu m
【 例 1】 计算
§ 1 算法的概念及特征方法一,先进行 1＋ 2、再加 3、再加 4,…,加到 100为止。（做 99次加法）
4
2009-7-29
方法二,100＋ (1＋ 99)＋ (2＋ 98)＋ … ＋ (49＋ 51)
＋ 50=100＋ 49× 100＋ 50=5050。 （ 1次乘法,2
次加法）
……
此例说明：解决问题的算法有优劣之分。算法的优劣是程序设计中一个极为重要的问题,不仅要保证算法正确，而且要考虑算法的质量（方法简单、运算步骤少） 。
§ 1 算法的概念及特征二、计算机算法的分类
5
2009-7-29
分为 数值运算算法 和 非数值运算算法 两大类。
数值运算算法,求问题 数值解 所用的算法。例如求方程组的解、求函数的定积分等所用的算法都是数值运算算法。
非数值运算算法,求问题 非数值解 所用的算法，
它涉及的面比数值运算算法更广。例如在网络搜索引擎、图书检索、人事管理、行车调度等领域中的算法都是非数值运算算法。
§ 1 算法的概念及特征
6
2009-7-29
【 例 2】 计算 5!=1× 2× 3× 4× 5
约定,用 s1,s2,…,sn表示算法的第 1、第 2,…,
第 n步。
实现思想,设 A,B两个变量，其中 A代表被乘数,B代表乘数。每一步的乘积结果存放在 A中。另外，用循环表示每一步的乘积运算。
具体算法如下：
s1：使 A = 1（初值）
s2：使 B = 2（初值）
s3,A× B?A（ A与 B的积存放于 A中）
s4,B＋ 1?B（ B的值增 1）
s5：如果 B≤5，返回重新执行 s3,s4,s5；否则，
算法结束,A的值为 5！。
§ 1 算法的概念及特征三、简单算法举例
7
2009-7-29
1 A
2 B
A× B A
B+1 B
B﹥ 5? 算法结束是否计算 5!的算法示意图
§ 1 算法的概念及特征
8
2009-7-29
【 例 3】 计算 N!（ N为任意正整数）。
s1,输入 N
s2,使 A = 1（初值）
s3,使 B = 2（初值）
s4,A× B?A（ A与 B的积存放于 A中）
s5,B＋ 1?B（ B的值增 1）
s6,如果 B≤N，返回重新执行 s4,s5,s6；否则，算法结束,A值为 N!。
§ 1 算法的概念及特征
9
2009-7-29
是是否否
【 例 4】 将 2000～ 2500年中的闰年打印出来。
闰年的条件是,⑴ 能被 4整除，但又不能被 100整除的年份是闰年； ⑵ 能被 100整除，又能被 400整除的年份是闰年。
设年份为 Y,否Y被 4整除？是
Y被 100整除？
闰年非闰年
Y被 400整除？
闰年 非闰年
§ 1 算法的概念及特征
10
2009-7-29
具体算法如下：
S1,2000?Y
S2,若 Y不能被 4整除，则打印 Y“不是闰年”，然后转到 S5。
S3,若 Y能被 4整除，但不能被 100整除，则打印 Y“是闰年”，然后转到 S5。
S4,若 Y能被 100整除，又能被 400整除，则打印 Y“是闰年”；否则打印“不是闰年”。
S5,Y+1?Y
S6,若 Y≤2500时，转 S2继续执行；否则算法结束。
§ 1 算法的概念及特征
11
2009-7-29
⒈ 有穷性,一个算法应包含有限的操作步骤，而不能是无限的。例如：不能有死循环。
⒉ 确定性,算法的含义应当是确定的、唯一的，而不应产生“歧义性”。例如，,100被一个整数除”是不确定的，它没有说明“这个整数”具体是多少。
⒊ 有零个或多个输入,可以没有输入。
⒋ 有一个或多个输出,至少有一个输出结果。
⒌ 有效性,算法中的每一步骤都应当能有效地执行，
并得到确定的结果。例如：如果设 B＝ 0，则 A÷ B就是无效的。
四、算法的特征 (或特点 )
§ 1 算法的概念及特征
12
2009-7-29
常用的算法表示方法有：自然语言法,流程图法,伪代码法,PAD图法等。
自然语言法,用人类语言或其他文字表示算法。
如前面的例 1～例 4。
优点：通俗易懂。
缺点：文字冗长、繁琐，含义不严格（确定性不佳）。
流程图,用一些图框来表示算法的步骤。 (重点 )
§ 2 算法的表示 (p6-23)
13
2009-7-29
常用的算法表示方法有：自然语言法,流程图法,伪代码法,PAD图法等。
伪代码 (pseudo code)法,用 介于自然语言和计算机语言之间 的文字和符号来描述算法。
PAD图法,即问题分析图 (Problem Analysis
Diagram)，是在软件开发中用到的一种表示算法的图形工具。
流程图 包括,传统流程图,结构化流程图,N-S
流程图 三种。
§ 2 算法的表示
14
2009-7-29
ANSI规定了一些常用的流程图符号 (见教材图 1.3)。
一、传统流程图
§ 2 算法的表示起止框输入输出框判断框处理框流程线或连接点注释框
15
2009-7-29
【 例 3】 计算 N!（ N为任意正整数）。
§ 2 算法的表示
s1,输入 N
s2,使 A = 1
s3,使 B = 2
s4,A× B?A
s5,B＋ 1?B
s6,如果 B≤N，返回重新执行 s4,s5,s6；否则,A值为 N!，输出 A值，
算法结束。
输入 N
开始
1?A
2?B
A× B?A
B＋ 1?B
B>N?
输出A(N!)
是结束否
16
2009-7-29
一个流程图主要包括：⑴表示相应操作的图框；
⑵带箭头的流程图；⑶图框内外相应的文字说明。
传统流程图的优缺点优点,直观形象、图框间的逻辑关系清楚。
缺点,对流程线的使用没有限制。 因此，使用者可以不受限制地使流程任意地转来转去，使流程图变得毫无规律，使人难以理解算法的逻辑。
§ 2 算法的表示结构化流程图
17
2009-7-29
基本思路,由基本结构构成算法流程图，只在基本结构内才存在 分支 和 向前 \向后的跳转,从而限制流程线的滥用。
1966年,Bohra和 Jacopini提出了三种基本结构,顺序结构,选择结构,循环结构 。
⑴ 顺序结构按流程线先后顺序执行算法中的各图框。
二、结构化流程图
§ 2 算法的表示顺序结构示意图
B
A
18
2009-7-29
⑵ 选择结构根据判断框中的条件 P是否成立选择执行 A或 B。
注,A或 B两个框中可以有一个是空，即不执行任何操作。
§ 2 算法的表示选择结构示意图
A
P
B
成立 不成立
A
P
19
2009-7-29
⑶ 循环结构包括两种类型,当型循环,直到型循环 。
当型 (While型 )循环当型循环示意图成立
P1
循环体不成立
§ 2 算法的表示当条件 P1成立时，执行循环体；
再判断条件 P1，若成立，再执行循环体；
… 如此反复 … ；
直到当条件 P1不成立时，则退出循环结构。
特点：① 先判断后执行 ；
② 当条件 P1成立时执行循环体，条件 P1是执行循环的条件 。
20
2009-7-29
⑶ 循环结构包括两种类型,当型循环,直到型循环 。
直到型 (Until型 )循环直到型循环示意图成立
P2
循环体不成立先执行循环体；
然后判断条件 P2，若不成立，再执行循环体；
然后再判断条件 P2，若仍然不成立，
则再执行循环体；
… 如此反复 … ；
直到条件 P2成立，则退出循环结构。
特点：① 先执行后判断 ；
② 当条件 P2不成立时执行循环体，条件 P2是退出循环的条件 。
§ 2 算法的表示
21
2009-7-29
【 例 3】 计算 N!（ N为任意正整数）。
输入 N
开始
1?A
2?B
A× B?A
B＋ 1?B
B>N?
输出A(N!)
是结束否直到型循环输入 N
开始
1?A
2?B
A× B?A
B＋ 1?B
B≤N?
输出A(N!)
是结束否 当型循环
22
2009-7-29
当型循环和直到型循环小结：
当型循环是 先判断后执行 ；
直到型循环是 先执行后判断 。
当型循环中条件 P1是执行循环的条件，故 条件成立时执行循环体 ；
直到型循环中条件 P2是退出循环的条件，故 条件不成立时执行循环体 。
当型循环和直到型循环的条件 P1和
P2互为逆条件 。
当型循环中条件不成立时循环体不执行，而 直到型循环的循环体至少执行一次 。
故，如果没有至少执行一次循环体的要求时，最好选用当型循环。 直到型循环示意图成立
P2
循环体不成立当型循环示意图成立
P1
循环体不成立
§ 2 算法的表示
23
2009-7-29 § 2 算法的表示由上述顺序结构、选择结构、循环结构三种基本结构所构成的算法为 结构化算法 ；所对应的流程图称为 结构化流程图 ；用计算机语言设计结构化算法，称为 结构化程序设计 。
三,N-S流程图在结构化流程图基础上,1973年美国学者 I,
Nassi和 B,Shneiderman提出了一种新的流程图形式，称为 N-S流程图，又称盒图 (box diagram)。
在 N-S流程图中,完全去掉了流程线，三种基本结构均用矩形框来表示 。
24
2009-7-29
⑴ 顺序结构
B
A
B
A
⑵ 选择 结构
A
P
B
成立 不成立
§ 2 算法的表示
P成立
A B
成立 不
25
2009-7-29
⑶ 循环 结构
当型 (While型 )循环
直到型 (Until型 )循环成立
P1
循环体不成立成立
P2
循环体不成立
§ 2 算法的表示当 P1
循环体直到 P2
循环体
26
2009-7-29
【 例 3】 计算 N!（ N为任意正整数）。
输入 N
开始
1?A
2?B
A× B?A
B＋ 1?B
B≤N?
输出A(N!)
是结束否 A× B?A
B＋ 1?B
当 B≤N
2?B
1?A
输入 N
输出 A（ N!）
27
2009-7-29
N-S流程图的特点：
没有起止框，没有流程线；
其余流程图符号均以矩形框形式表示；
在一个基本结构中还可以包含另一个基本结构
（如教材 p19图 1.48）。
§ 2 算法的表示
