《CHAR02 算法》由会员分享，可在线阅读，更多相关《CHAR02 算法（16页珍藏版）》请在金锄头文库上搜索。
1、靳润昭 C语言教程讲义 2001年2月17日2程序的灵魂算法12.1算法的概念12.2简单算法举例12.3算法的的特性42.4怎样表表示一个算法法42.4.1用用自然语言表表示算法42.4.2用用流程图表示示算法42.4.3三三种基本结构构和改进的流流程图82.4.4用用N-S流程图图表示算法92.4.5用用伪代码表示示算法102.4.6用用计算机语言言表示算法112.5结构化化程序设计方方法112 程序的灵魂算算法一个程序应包括括：l 对数据的描述。在在程序中要指指定数据的类类型和数据的的组织形式，即即数据结构（data structure）。l 对操作的描述。即即操作步骤，也也就是算法（a
2、lgorithm）。Nikiklaaus Wiirth提出出的公式：数据结构+算法法=程序教材认为：程序=算法+数数据结构+程序设计方方法+语言工具和和环境这4个方面是一一个程序涉及及人员所应具具备的知识。本课程的目的是是使同学知道道怎样编写一一个C程序，进行行编写程序的的初步训练，因因此，只介绍绍算法的初步步知识。2.1 算法的概念做任何事情都有有一定的步骤骤。为解决一一个问题而采采取的方法和和步骤，就称称为算法。l 计算机算法：计计算机能够执执行的算法。l 计算机算法可分分为两大类：n 数值运算算法：求解数值；n 非数值运算算法法：事务管理理领域。2.2 简单算法举例【例2.1】求求123
3、45。最原始方法：步骤1：先求112，得到结果果2。步骤2：将步骤骤1得到的乘积积2乘以3，得到结果果6。步骤3：将6再再乘以4，得24。步骤4：将244再乘以5，得120。这样的算法虽然然正确，但太太繁。改进的算法：S1: 使t=1S2: 使i=2S3: 使ti, 乘积积仍然放在在在变量t中，可表示示为titS4: 使i的的值+1，即i+1iS5: 如果ii5, 返回重重新执行步骤骤S3以及其后后的S4和S5；否则，算算法结束。如果计算1000！只需将S55:若i5改成i100即可。如果该求13357911，算法也也只需做很少少的改动：S1: 1ttS2: 3iiS3: tiitS4: i+
4、22tS5:若i111, 返回回S3，否则，结结束。该算法不仅正确确，而且是计计算机较好的的算法，因为为计算机是高高速运算的自自动机器，实实现循环轻而而易举。思考：若将 SS5写成：S5:若i11, 返回回S3;否则，结结束。【例2.2】有有50个学生，要要求将他们之之中成绩在880分以上者者打印出来。如果，n表示学学生学号，nni表示第个学学生学号；gg表示学生成成绩，gi表示第个学学生成绩；则算法可表示如如下：S1: 1iiS2: 如果ggi80，则打印印ni和gi，否则不打打印S3: i+11iS4:若i550, 返回回S2，否则，结结束。【例2.3】判判定20000 25000年中的每
5、一一年是否闰年年，将结果输输出。润年的条件：1) 能被4整除，但但不能被1000整除的年年份；2) 能被100整除除，又能被4400整除的的年份；设y为被检测的的年份，则算算法可表示如如下：S1: 20000yS2:若y不能能被4整除，则输输出y“不是闰年”，然后转到到S6S3:若y能被被4整除，不能能被100整除，则则输出y“是闰年”，然后转到到S6S4:若y能被被100整除，又又能被4000整除，输出出y“是闰年” 否则输出y“不是闰年”，然后转到到S6S5:输出y“不是闰年”。S6:y+1yS7:当y22500时, 返回S2继续执行行，否则，结结束。【例2.4】求求。算法可表示如下下：S
6、1: siggh=1S2: summ=1S3: denno=2S4: siggh=(-11)siggh S5: terrm= siigh(11/denoo )S6: terrm=summ+termmS7: denno= deeno +11S8:若denno100，返回回S4；否则，结结束。【例2.5】对对一个大于或或等于3的正整数，判判断它是不是是一个素数。算法可表示如下下：S1: 输入nn的值S2: i=22S3: n被ii除，得余数数rS4:如果r=0，表示n能被i整除，则打打印n“不是素数”，算法结束束；否则执行行S5S5: i+11i S6:如果in-1，返回回S3；否则打打印n“是素
7、数”；然后算法法结束。改进：S6:如果i，返回S3；否则打打印n“是素数”;然后算法结结束。2.3 算法的特性l 有穷性：一个算算法应包含有有限的操作步步骤而不能是是无限的。 l 确定性：算法中中每一个步骤骤应当是确定定的，而不能能应当是含糊糊的、模棱两两可的。l 有零个或多个输输入。l 有一个或多个输输出。l 有效性：算法中中每一个步骤骤应当能有效效地执行，并并得到确定的的结果。对于程序设计人人员，必须会会设计算法，并并根据算法写写出程序。2.4 怎样表示一个算算法2.4.1 用自然语言表示示算法除了很简单的问问题，一般不不用自然语言言表示算法。2.4.2 用流程图表示算算法流程图表示算法法
8、，直观形象象，易于理解解。【例2.6】将将例2.1求5!的算用流流程图表示。【例2.7】将将例2.2的算用用流程图表示示。【例2.8】将将例2.3判定闰闰年的算用流流程图表示。【例2.9】将将例2.4求的算用流程程图表示。一个流程图包括括：1. 表示相应操作的的框；2. 带箭头的流程线线；3. 框内外必要的文文字说明。2.4.3 三种基本结构和和改进的流程程图1. 顺序结构：2. 选择结构：3. 循环结构三种基本结构的的共同特点：l 只有一个入口；l 只有一个出口；l 结构内的每一部部分都有机会会被执行到；l 结构内不存在“死循环”。2.4.4 用N-S流程图图表示算法1973年美国国学者提出
9、了了一种新型流流程图：N-S流程图。顺序结构：选择结构：循环结构：2.4.5 用伪代码表示算算法伪代码使用介于于自然语言和和计算机语言言之间的文字字和符号来描描述算法。2.4.6 用计算机语言表表示算法l 我们的任务是用用计算机解题题，就是用计计算机实现算算法；l 用计算机语言表表示算法必须须严格遵循所所用语言的语语法规则。【例2.20】求求12345用C语言表示。main()int i,t; t=1; i=2; while(i=5)t=t*i;i=i+1; printff(“%d”,t); 【例2.21】求求级数的值。main()int siggh=1;float ddeno=22.0,suum=1.00,termm;while(ddeno=100) sigh= -siggh; term= ssigh/ deno;sum=summ+termm;deno=deeno+1; printff(“%f”,sum);2.5 结构化程序设计计方法l 自顶向下；l 逐步细化；l 模块化设计；l 结构化编码。第11页
