第二章 算法
2.1算法的概念做任何事情都有一定的步骤 。 为解决一个问题而采取的方法和步骤,就称为 算法 。
计算机算法,计算机能够执行的算法 。
计算机算法可分为两大类：
数值运算算法：求解数值；
非数值运算算法：事务管理领域。
2.2 简单算法举例
【 例 2.1】 求 1× 2× 3× 4× 5。
最原始方法：
步骤 1：先求 1× 2,得到结果 2。
步骤 2：将步骤 1得到的乘积 2乘以 3,得到结果 6。
步骤 3：将 6再乘以 4,得 24。
步骤 4：将 24再乘以 5,得 120。
这样的算法虽然正确,但太繁 。
改进的算法：
S1,使 t=1
S2,使 i=2
S3,使 t× i,乘积仍然放在在变量 t中,可表示为 t× i→t
S4,使 i的值 +1,即 i+1→i
S5,如果 i≤ 5,返回重新执行步骤 S3以及其后的 S4和 S5；
否则，算法结束。
如果该求 1× 3× 5× 7× 9× 11,算法也只需做很少的改动：
S1,1→t
S2,3→i
S3,t× i→t
S4,i+2→t
S5:若 i≤11,返回 S3,否则,结束 。
该算法不仅正确,而且是计算机较好的算法,
因为计算机是高速运算的自动机器,实现循环轻而易举 。
思考：若将 S5写成,S5:若 i＜ 11,返回 S3;否则，
结束。
【 例 2.2】 有 50个学生,要求将他们之中成绩在 80
分以上者打印出来 。
如果,n表示学生学号,ni表示第个学生学号； g
表示学生成绩,gi表示第个学生成绩；
则算法可表示如下：
S1,1→i
S2,如果 gi≥80,则打印 ni和 gi,否则不打印
S3,i+1→i
S4:若 i≤50,返回 S2,否则,结束 。
【 例 2.3】 判定 2000 — 2500年中的每一年是否闰年,将结果输出 。
润年的条件：
1) 能被 4整除,但不能被 100整除的年份；
2) 能被 100整除,又能被 400整除的年份；
设 y为被检测的年份,则算法可表示如下：
S1,2000→y
S2:若 y不能被 4整除,则输出 y“不是闰年,,然后转到 S6
S3:若 y能被 4整除,不能被 100整除,则输出 y“是闰年,,然后转到 S6
S4:若 y能被 100整除,又能被 400整除,输出 y“是闰年,否则输出 y“不是闰年,,然后转到 S6
S5:输出 y“不是闰年,。
S6:y+1→y
S7:当 y≤ 2500时,返回 S2继续执行，否则，结束。
【 例 2.4】 求算法可表示如下：
S1,sigh=1
S2,sum=1
S3,deno=2
S4,sigh=(-1)× sigh
S5,term= sigh× (1/deno )
S6,term=sum+term
S7,deno= deno +1
S8:若 deno≤100,返回 S4；否则,结束 。
【 例 2.5】 对一个大于或等于 3的正整数,判断它是不是一个素数 。
算法可表示如下：
S1,输入 n的值
S2,i=2
S3,n被 i除,得余数 r
S4:如果 r=0,表示 n能被 i整除,则打印 n“不是素数,,算法结束；否则执行 S5
S5,i+1→i
S6:如果 i≤n-1,返回 S3；否则打印 n“是素数,；然后算法结束 。
改进：
S6:如果 i≤,返回 S3；否则打印 n“是素数,;然后算法结束。
2.3 算法的特性
l有穷性：一个算法应包含有限的操作步骤而不能是无限的 。
l确定性：算法中每一个步骤应当是确定的,而不能应当是含糊的,模棱两可的 。
l有零个或多个输入 。
l有一个或多个输出 。
l有效性：算法中每一个步骤应当能有效地执行,并得到确定的结果 。
对于程序设计人员,必须会设计算法,并根据算法写出程序 。
2.4 怎样表示一个算法
2.4.1 用自然语言表示算法除了很简单的问题，一般不用自然语言表示算法。
2.4.2 用流程图表示算法流程图表示算法，直观形象，易于理解。
5的阶乘
2.4.4 用 N-S流程图表示算法
1973年美国学者提出了一种新型流程图,N-S
流程图 。
顺序结构：
选择结构：
循环结构,
2.4.5 用伪代码表示算法伪代码使用介于自然语言和计算机语言之间的文字和符号来描述算法 。
2.4.6 用计算机语言表示算法
l任务是用计算机解题,就是用计算机实现算法；
l用计算机语言表示算法必须严格遵循所用语言的语法规则 。
【 例 2.20】 求 1× 2× 3× 4× 5用 C语言表示 。
main()
{ int i,t;
t=1;
i=2;
while(i<=5)
{t=t*i;
i=i+1;
}
printf(“%d”,t);
}
2.5 结构化程序设计方法自顶向下；
逐步细化；
模块化设计；
结构化编码第一、二章作业
【 题 1.1】 一个 C程序的执行是从 。
A） 本程序的 main函数开始,到 main函数结束
B） 本程序文件的第一个函数开始,到本程序文件的最后一个函数结束
C） 本程序的 main函数开始,到本程序文件的最后一个函数结束
D） 本程序文件的第一个函数开始,到本程序 main函数结束
【 题 1.2】 以下叙述正确的是 。
A） 在 C程序中,main函数必须位于程序的最前面
B） C程序的每行中只能写一条语句
C） C语言本身没有输入输出语句
D） 在对一个 C程序进行编译的过程中,可发现注释中的拼写错误
【 题 1.3】 以下叙述不正确的是 。
A） 一个 C源程序可由一个或多个函数组成
B） 一个 C源程序必须包含一个 main函数
C） C程序的基本组成单位是函数
D） 在 C程序中,注释说明只能位于一条语句的后面
【 题 1.4】 C语言规定：在一个源程序中,main函数的位置 。
A） 必须在最开始
B） 必须在系统调用的库函数的后面
C） 可以任意
D） 必须在最后
【 题 1.5】 一个 C语言程序是由 。
A） 一个主程序和若干子程序组成
B） 函数组成
C） 若干过程组成
D) 若干子程序组成
【 题 1.6】 C源程序的基本单位是 【 】 。
【 题 1.7】 一个 C源程序至少应包括一个 【 】 。
【 题 1.8】 在一个 C源程序中,注释部分两侧的分界符分别为 【 1】 和 【 2】 。
【 题 1.9】 在 C语言中,输入操作是由库函数 【 1】 完成的,输出操作是由库函数 【 2】 完成的 。
P37 2.4 2.8
【 题 1.1-1.5】 ACDCB
【 题 1.6】 函数
【 题 1.7】 主函数 （ 或,main函数 ）
【 题 1.8】 【 1】 /* 【 2】 */
【 题 1.9】 【 1】 scanf 【 2】 printf
2.1算法的概念做任何事情都有一定的步骤 。 为解决一个问题而采取的方法和步骤,就称为 算法 。
计算机算法,计算机能够执行的算法 。
计算机算法可分为两大类：
数值运算算法：求解数值；
非数值运算算法：事务管理领域。
2.2 简单算法举例
【 例 2.1】 求 1× 2× 3× 4× 5。
最原始方法：
步骤 1：先求 1× 2,得到结果 2。
步骤 2：将步骤 1得到的乘积 2乘以 3,得到结果 6。
步骤 3：将 6再乘以 4,得 24。
步骤 4：将 24再乘以 5,得 120。
这样的算法虽然正确,但太繁 。
改进的算法：
S1,使 t=1
S2,使 i=2
S3,使 t× i,乘积仍然放在在变量 t中,可表示为 t× i→t
S4,使 i的值 +1,即 i+1→i
S5,如果 i≤ 5,返回重新执行步骤 S3以及其后的 S4和 S5；
否则，算法结束。
如果该求 1× 3× 5× 7× 9× 11,算法也只需做很少的改动：
S1,1→t
S2,3→i
S3,t× i→t
S4,i+2→t
S5:若 i≤11,返回 S3,否则,结束 。
该算法不仅正确,而且是计算机较好的算法,
因为计算机是高速运算的自动机器,实现循环轻而易举 。
思考：若将 S5写成,S5:若 i＜ 11,返回 S3;否则，
结束。
【 例 2.2】 有 50个学生,要求将他们之中成绩在 80
分以上者打印出来 。
如果,n表示学生学号,ni表示第个学生学号； g
表示学生成绩,gi表示第个学生成绩；
则算法可表示如下：
S1,1→i
S2,如果 gi≥80,则打印 ni和 gi,否则不打印
S3,i+1→i
S4:若 i≤50,返回 S2,否则,结束 。
【 例 2.3】 判定 2000 — 2500年中的每一年是否闰年,将结果输出 。
润年的条件：
1) 能被 4整除,但不能被 100整除的年份；
2) 能被 100整除,又能被 400整除的年份；
设 y为被检测的年份,则算法可表示如下：
S1,2000→y
S2:若 y不能被 4整除,则输出 y“不是闰年,,然后转到 S6
S3:若 y能被 4整除,不能被 100整除,则输出 y“是闰年,,然后转到 S6
S4:若 y能被 100整除,又能被 400整除,输出 y“是闰年,否则输出 y“不是闰年,,然后转到 S6
S5:输出 y“不是闰年,。
S6:y+1→y
S7:当 y≤ 2500时,返回 S2继续执行，否则，结束。
【 例 2.4】 求算法可表示如下：
S1,sigh=1
S2,sum=1
S3,deno=2
S4,sigh=(-1)× sigh
S5,term= sigh× (1/deno )
S6,term=sum+term
S7,deno= deno +1
S8:若 deno≤100,返回 S4；否则,结束 。
【 例 2.5】 对一个大于或等于 3的正整数,判断它是不是一个素数 。
算法可表示如下：
S1,输入 n的值
S2,i=2
S3,n被 i除,得余数 r
S4:如果 r=0,表示 n能被 i整除,则打印 n“不是素数,,算法结束；否则执行 S5
S5,i+1→i
S6:如果 i≤n-1,返回 S3；否则打印 n“是素数,；然后算法结束 。
改进：
S6:如果 i≤,返回 S3；否则打印 n“是素数,;然后算法结束。
2.3 算法的特性
l有穷性：一个算法应包含有限的操作步骤而不能是无限的 。
l确定性：算法中每一个步骤应当是确定的,而不能应当是含糊的,模棱两可的 。
l有零个或多个输入 。
l有一个或多个输出 。
l有效性：算法中每一个步骤应当能有效地执行,并得到确定的结果 。
对于程序设计人员,必须会设计算法,并根据算法写出程序 。
2.4 怎样表示一个算法
2.4.1 用自然语言表示算法除了很简单的问题，一般不用自然语言表示算法。
2.4.2 用流程图表示算法流程图表示算法，直观形象，易于理解。
5的阶乘
2.4.4 用 N-S流程图表示算法
1973年美国学者提出了一种新型流程图,N-S
流程图 。
顺序结构：
选择结构：
循环结构,
2.4.5 用伪代码表示算法伪代码使用介于自然语言和计算机语言之间的文字和符号来描述算法 。
2.4.6 用计算机语言表示算法
l任务是用计算机解题,就是用计算机实现算法；
l用计算机语言表示算法必须严格遵循所用语言的语法规则 。
【 例 2.20】 求 1× 2× 3× 4× 5用 C语言表示 。
main()
{ int i,t;
t=1;
i=2;
while(i<=5)
{t=t*i;
i=i+1;
}
printf(“%d”,t);
}
2.5 结构化程序设计方法自顶向下；
逐步细化；
模块化设计；
结构化编码第一、二章作业
【 题 1.1】 一个 C程序的执行是从 。
A） 本程序的 main函数开始,到 main函数结束
B） 本程序文件的第一个函数开始,到本程序文件的最后一个函数结束
C） 本程序的 main函数开始,到本程序文件的最后一个函数结束
D） 本程序文件的第一个函数开始,到本程序 main函数结束
【 题 1.2】 以下叙述正确的是 。
A） 在 C程序中,main函数必须位于程序的最前面
B） C程序的每行中只能写一条语句
C） C语言本身没有输入输出语句
D） 在对一个 C程序进行编译的过程中,可发现注释中的拼写错误
【 题 1.3】 以下叙述不正确的是 。
A） 一个 C源程序可由一个或多个函数组成
B） 一个 C源程序必须包含一个 main函数
C） C程序的基本组成单位是函数
D） 在 C程序中,注释说明只能位于一条语句的后面
【 题 1.4】 C语言规定：在一个源程序中,main函数的位置 。
A） 必须在最开始
B） 必须在系统调用的库函数的后面
C） 可以任意
D） 必须在最后
【 题 1.5】 一个 C语言程序是由 。
A） 一个主程序和若干子程序组成
B） 函数组成
C） 若干过程组成
D) 若干子程序组成
【 题 1.6】 C源程序的基本单位是 【 】 。
【 题 1.7】 一个 C源程序至少应包括一个 【 】 。
【 题 1.8】 在一个 C源程序中,注释部分两侧的分界符分别为 【 1】 和 【 2】 。
【 题 1.9】 在 C语言中,输入操作是由库函数 【 1】 完成的,输出操作是由库函数 【 2】 完成的 。
P37 2.4 2.8
【 题 1.1-1.5】 ACDCB
【 题 1.6】 函数
【 题 1.7】 主函数 （ 或,main函数 ）
【 题 1.8】 【 1】 /* 【 2】 */
【 题 1.9】 【 1】 scanf 【 2】 printf
