第 2章 算法
C 语言程序设计
2009-7-31
2.1 算法的概念
2.2 怎样表示一个算法
2.3 算法的特性
2.4 简单算法举例
2.5 结构化程序设计方法
主要内容
2009-7-31
一个程序应包括两个方面的内容,
对数据的描述：数据结构 (data structure)
对操作的描述：算法 (algorithm)
著名计算机科学家沃思提出一个公式,
数据结构 + 算法 = 程序数据结构＋算法＋程序设计方法＋语言工具完整的程序设计应该是,
2009-7-31
2.1 算法的概念
什么是算法
– 为解决某一应用问题而采用的 解题步骤
– 算法的历史
,算法,即演算法出自,周髀算经,
英文名称 Algorithm
欧几里得算法 被人们认为是史上第一个算法 。
2009-7-31
用自然语言描述算法第一步：输入 x和 y的值第二步：比较 x和 y的值，如果 x大于 y，则输出 x
的值，否则输出 y的值。
易于理解，但冗长，不够精确，难于描述复杂算法。
例如当描述,输出 10个数中最大数,的算法时，
会冗长、难于理解例如：输出两个数中的最大数
2.2 怎样表示一个算法
2009-7-31
用流程图描述算法用流程图描述算法
NY
z= yz= x
x >y?
开始输入 x和 y
结束输出 z
起止框输入 /输出框判断框处理框流程线
2009-7-31
流程图是表示算法的较好的工具。
一个流程图包括以下几部分,
(1)表示相应操作的框；
(2)带箭头的流程线；
(3)框内外必要的文字说明。
用流程图表示算法直观形象，比较清楚地显示出各个框之间地逻辑关系。但是这种流程图占用篇幅较多，尤其当算法比较复杂时，画流程图既费时又不方便。
2009-7-31
三种基本结构和改进的流程图
传统的流程图用流程线指出各框的执行顺序，
对流程线的使用没有严格限制。因此使用者可以毫不受限制地使流程随意地转来转去，使流程图变得毫无规律，阅读者要花很大精力去追踪流程，使人难以理解算法的逻辑。
为了提高算法的质量，使算法的设计和阅读方便，必须限制箭头的滥用，既不允许无规律地使流程随意转向，只能顺序地进行下去。但是，
算法上难免会包含一些分支和循环，为了解决这个问题，人们规定出几种基本结构，然后由这些基本结构按一定规律组成一个算法结构。
2009-7-31
三种基本结构和改进的流程图
程序的三种基本结构
– 顺序结构程序,按照书写顺序依次执行语句
– 选择结构程序,按照条件判断选择执行语句
– 循环结构程序,通过条件控制循环执行语句三种基本结构的共同点：
都是只有一个入口和一个出口；
结构内的每一个框都有机会被执行；
结构内没有死循环。
2009-7-31
小结：
由三种基本结构顺序组成的算法结构，
可以解决任何复杂的问题。由基本结构所构成的算法属于,结构化,的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。
2009-7-31
扩展：
只要具有上述四个特点的都可以作为基本结构。可以自己定义基本结构，
并由这些基本结构组成结构化程序。
此图符合基本结构的特点
2009-7-31
用 N-S结构图描述算法输入 x,y的值
x>y
T F
z = x z = y
输出 z的值用 N-S结构图描述的算法
2009-7-31
N-S图表示算法的优点
比文字描述直观、形象,易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，
整个算法结构是由各个基本结构按顺序组成的,N--S流程图中的上下顺序就是执行时的顺序。用 N--S图表示的算法都是结构化的算法，因为它不可能出现流程无规律的跳转，
而只能自上而下地顺序执行。
已经证明，任何复杂的问题都可以三种基本算法结构来描述,顺序、选择、循环。 因此用计算机语句描述的 程序也包含三种基本结构。
2009-7-31
用伪代码表示算法流程图和 N-S盒图直观易懂，但画起来比较费事，修改麻烦，适宜表示一个算法，
但在设计算法过程中不是很理想。为了设计算法时方便，常用一种称为伪代码的工具。
伪代码是介于自然语言和计算机语言之间地文字和符号来描述算法。书写方便，格式紧凑，也比较好懂，也便于向计算机语言算法过渡。
2009-7-31
2.3 简单算法举例
例 2.1 求 1× 2× 3× 4× 5
最原始的方法：
s1：先求 1× 2，得到结果 2。
s2：将步骤 1得到的乘积 2再乘以 3，得到结果 6。
s3：将 6再乘以 4，得 24。
S4：将 24再乘以 5，得 120。最后结果。
2009-7-31
可以设两个变量：一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤得乘积放在被乘数变量中。今设 p为被乘数,i为乘数。用循环法来求结果。可将算法改写如下：
s1：使 p＝ 1
s2：使 i＝ 2
s3：使 p× i，乘积仍放在变量 p中，可表示为：
p× i＝ >p
s4：使 i得值加 1，即 i＋ 1＝ >i
s5：如果 i不大于 5，返回重新执行步骤 s3以及其后得步骤 s4和 s5；否则，算法结束。最后得到 p
的值就是 5！的值。
2009-7-31
流程图开始
1＝ >p
2=>i
P*i=>p
i+1=>i
i>5
结束
Y
N
2009-7-31
N-S盒图（结构化流程图）
1=>p
2=>i
P*i=>p
i+1=>i
直到 i>5
输出 p
2009-7-31
用伪代码表示算法开始置 p的初值为 1
置 i的初值为 2
当 i<=5，执行下面操作：
使 p=p*I
使 i=i+1{循环体到此结束 }
输出 p的值结束
Begin
1=>p
2=>i
while i<=5
{p*i=>p
i+1=>i
}
print
end
2009-7-31
用计算机语言表示算法
#include<stdio.h>
Void main()
{
int i,p;
p = 1;
i = 2;
while(i<=5)
{
p=p*i;
i=i+1;
}
printf(“%d\n”,p);
}
2009-7-31
例 2.2 P16
有 50个学生，要求将他们之中成绩在 80分以上的学号和成绩输出。用 n表示学生学号,n1代表第一个学生学号,ni代表第 i个学生学号。用 G代表学生成绩,gi代表第 i
个学生成绩。
分别用 传统流程图 和 N-S结构化流程图 来描述解决该问题的算法。
2009-7-31
开始
1＝ >i
gi≥80
i+1 ＝ >i
i>50
N
N
结束
Y
1=>i
gi ≥80
i+1=>i
i>50
Y N
输出 ni,gi输出 n
i,gi
Y
2009-7-31
例 2.3 判定 2000-2005年中的每一年是否闰年，将结果输出。 P17
要求用流程图和 N-S盒图给出相应的算法。
2009-7-31
开始
2000=>y
y不能被 4整除
y不是闰年y不能被 100整除
y是闰年
Y
N
Y N
y不能被 400整除
y不是闰年
y是闰年
N
Y
y=y+1
y≤2005
结束
Y
N
2009-7-31
2000=>y
y/4的余数为 0
是 否
y/100的余数不为 0
是 否输出 y
不是闰年
y/400的余数为 0是 否
y是闰年 y不是闰年
y不是闰年
y+1=>y
y>2005
2009-7-31
有穷性
确定性
有零个或多个输入
有一个或多个输出
有效性
2.4 算法的特性 (P19)
2009-7-31
2.5 结构化程序设计方法
一个结构化程序 就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、便于阅读、便于修改和维护。
结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。
结构化程序设计方法的基本思路是：把一个复杂问题的求解过程 分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。
2009-7-31
结构化程序设计的基本原则：
如果一个程序仅包含这三种基本结构（由这些基本结构顺序组成），则称为结构化程序。
结构化程序设计的基本原则：
– 采用 自顶向下、逐步细化 的方法进行设计；
– 采用 模块化原则和方法 进行设计。即将大型任务从上向下划分为多个功能模块，每个模块又可以划分为若干子模块，然后分别进行模块程序的编写；
– 每个模块都是用结构化程序实现,即都只能由三种基本结构组成，并通过计算机语言的结构化语句实现。
2009-7-31
用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫 做,自顶向下，逐步细化,
2009-7-31
自顶向下，逐步细化方法的优点：
考虑周全，结构清晰，层次分明，作者容易写，读者容易看。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分修改有关段落即可，与其它部分无关。我们提倡用这种方法设计程序。这
2009-7-31
模块设计的方法：
模块化设计的思想实际上是一种,分而治之,
的思想，把一个大任务分为若干个子任务，
每一个子任务就相对简单了。
在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。这个过程采用自顶向下方法来实现。
子模块一般不超过 50行。
划分子模块时应注意模块的独立性，即：使一个模块完成一项功能，耦合性愈少愈好。
C 语言程序设计
2009-7-31
2.1 算法的概念
2.2 怎样表示一个算法
2.3 算法的特性
2.4 简单算法举例
2.5 结构化程序设计方法
主要内容
2009-7-31
一个程序应包括两个方面的内容,
对数据的描述：数据结构 (data structure)
对操作的描述：算法 (algorithm)
著名计算机科学家沃思提出一个公式,
数据结构 + 算法 = 程序数据结构＋算法＋程序设计方法＋语言工具完整的程序设计应该是,
2009-7-31
2.1 算法的概念
什么是算法
– 为解决某一应用问题而采用的 解题步骤
– 算法的历史
,算法,即演算法出自,周髀算经,
英文名称 Algorithm
欧几里得算法 被人们认为是史上第一个算法 。
2009-7-31
用自然语言描述算法第一步：输入 x和 y的值第二步：比较 x和 y的值，如果 x大于 y，则输出 x
的值，否则输出 y的值。
易于理解，但冗长，不够精确，难于描述复杂算法。
例如当描述,输出 10个数中最大数,的算法时，
会冗长、难于理解例如：输出两个数中的最大数
2.2 怎样表示一个算法
2009-7-31
用流程图描述算法用流程图描述算法
NY
z= yz= x
x >y?
开始输入 x和 y
结束输出 z
起止框输入 /输出框判断框处理框流程线
2009-7-31
流程图是表示算法的较好的工具。
一个流程图包括以下几部分,
(1)表示相应操作的框；
(2)带箭头的流程线；
(3)框内外必要的文字说明。
用流程图表示算法直观形象，比较清楚地显示出各个框之间地逻辑关系。但是这种流程图占用篇幅较多，尤其当算法比较复杂时，画流程图既费时又不方便。
2009-7-31
三种基本结构和改进的流程图
传统的流程图用流程线指出各框的执行顺序，
对流程线的使用没有严格限制。因此使用者可以毫不受限制地使流程随意地转来转去，使流程图变得毫无规律，阅读者要花很大精力去追踪流程，使人难以理解算法的逻辑。
为了提高算法的质量，使算法的设计和阅读方便，必须限制箭头的滥用，既不允许无规律地使流程随意转向，只能顺序地进行下去。但是，
算法上难免会包含一些分支和循环，为了解决这个问题，人们规定出几种基本结构，然后由这些基本结构按一定规律组成一个算法结构。
2009-7-31
三种基本结构和改进的流程图
程序的三种基本结构
– 顺序结构程序,按照书写顺序依次执行语句
– 选择结构程序,按照条件判断选择执行语句
– 循环结构程序,通过条件控制循环执行语句三种基本结构的共同点：
都是只有一个入口和一个出口；
结构内的每一个框都有机会被执行；
结构内没有死循环。
2009-7-31
小结：
由三种基本结构顺序组成的算法结构，
可以解决任何复杂的问题。由基本结构所构成的算法属于,结构化,的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。
2009-7-31
扩展：
只要具有上述四个特点的都可以作为基本结构。可以自己定义基本结构，
并由这些基本结构组成结构化程序。
此图符合基本结构的特点
2009-7-31
用 N-S结构图描述算法输入 x,y的值
x>y
T F
z = x z = y
输出 z的值用 N-S结构图描述的算法
2009-7-31
N-S图表示算法的优点
比文字描述直观、形象,易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，
整个算法结构是由各个基本结构按顺序组成的,N--S流程图中的上下顺序就是执行时的顺序。用 N--S图表示的算法都是结构化的算法，因为它不可能出现流程无规律的跳转，
而只能自上而下地顺序执行。
已经证明，任何复杂的问题都可以三种基本算法结构来描述,顺序、选择、循环。 因此用计算机语句描述的 程序也包含三种基本结构。
2009-7-31
用伪代码表示算法流程图和 N-S盒图直观易懂，但画起来比较费事，修改麻烦，适宜表示一个算法，
但在设计算法过程中不是很理想。为了设计算法时方便，常用一种称为伪代码的工具。
伪代码是介于自然语言和计算机语言之间地文字和符号来描述算法。书写方便，格式紧凑，也比较好懂，也便于向计算机语言算法过渡。
2009-7-31
2.3 简单算法举例
例 2.1 求 1× 2× 3× 4× 5
最原始的方法：
s1：先求 1× 2，得到结果 2。
s2：将步骤 1得到的乘积 2再乘以 3，得到结果 6。
s3：将 6再乘以 4，得 24。
S4：将 24再乘以 5，得 120。最后结果。
2009-7-31
可以设两个变量：一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤得乘积放在被乘数变量中。今设 p为被乘数,i为乘数。用循环法来求结果。可将算法改写如下：
s1：使 p＝ 1
s2：使 i＝ 2
s3：使 p× i，乘积仍放在变量 p中，可表示为：
p× i＝ >p
s4：使 i得值加 1，即 i＋ 1＝ >i
s5：如果 i不大于 5，返回重新执行步骤 s3以及其后得步骤 s4和 s5；否则，算法结束。最后得到 p
的值就是 5！的值。
2009-7-31
流程图开始
1＝ >p
2=>i
P*i=>p
i+1=>i
i>5
结束
Y
N
2009-7-31
N-S盒图（结构化流程图）
1=>p
2=>i
P*i=>p
i+1=>i
直到 i>5
输出 p
2009-7-31
用伪代码表示算法开始置 p的初值为 1
置 i的初值为 2
当 i<=5，执行下面操作：
使 p=p*I
使 i=i+1{循环体到此结束 }
输出 p的值结束
Begin
1=>p
2=>i
while i<=5
{p*i=>p
i+1=>i
}
end
2009-7-31
用计算机语言表示算法
#include<stdio.h>
Void main()
{
int i,p;
p = 1;
i = 2;
while(i<=5)
{
p=p*i;
i=i+1;
}
printf(“%d\n”,p);
}
2009-7-31
例 2.2 P16
有 50个学生，要求将他们之中成绩在 80分以上的学号和成绩输出。用 n表示学生学号,n1代表第一个学生学号,ni代表第 i个学生学号。用 G代表学生成绩,gi代表第 i
个学生成绩。
分别用 传统流程图 和 N-S结构化流程图 来描述解决该问题的算法。
2009-7-31
开始
1＝ >i
gi≥80
i+1 ＝ >i
i>50
N
N
结束
Y
1=>i
gi ≥80
i+1=>i
i>50
Y N
输出 ni,gi输出 n
i,gi
Y
2009-7-31
例 2.3 判定 2000-2005年中的每一年是否闰年，将结果输出。 P17
要求用流程图和 N-S盒图给出相应的算法。
2009-7-31
开始
2000=>y
y不能被 4整除
y不是闰年y不能被 100整除
y是闰年
Y
N
Y N
y不能被 400整除
y不是闰年
y是闰年
N
Y
y=y+1
y≤2005
结束
Y
N
2009-7-31
2000=>y
y/4的余数为 0
是 否
y/100的余数不为 0
是 否输出 y
不是闰年
y/400的余数为 0是 否
y是闰年 y不是闰年
y不是闰年
y+1=>y
y>2005
2009-7-31
有穷性
确定性
有零个或多个输入
有一个或多个输出
有效性
2.4 算法的特性 (P19)
2009-7-31
2.5 结构化程序设计方法
一个结构化程序 就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、便于阅读、便于修改和维护。
结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。
结构化程序设计方法的基本思路是：把一个复杂问题的求解过程 分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。
2009-7-31
结构化程序设计的基本原则：
如果一个程序仅包含这三种基本结构（由这些基本结构顺序组成），则称为结构化程序。
结构化程序设计的基本原则：
– 采用 自顶向下、逐步细化 的方法进行设计；
– 采用 模块化原则和方法 进行设计。即将大型任务从上向下划分为多个功能模块，每个模块又可以划分为若干子模块，然后分别进行模块程序的编写；
– 每个模块都是用结构化程序实现,即都只能由三种基本结构组成，并通过计算机语言的结构化语句实现。
2009-7-31
用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫 做,自顶向下，逐步细化,
2009-7-31
自顶向下，逐步细化方法的优点：
考虑周全，结构清晰，层次分明，作者容易写，读者容易看。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分修改有关段落即可，与其它部分无关。我们提倡用这种方法设计程序。这
2009-7-31
模块设计的方法：
模块化设计的思想实际上是一种,分而治之,
的思想，把一个大任务分为若干个子任务，
每一个子任务就相对简单了。
在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。这个过程采用自顶向下方法来实现。
子模块一般不超过 50行。
划分子模块时应注意模块的独立性，即：使一个模块完成一项功能，耦合性愈少愈好。
