第2章 算法的概念和特性介绍

《第2章 算法的概念和特性介绍》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第二章算法主讲福州大学数学与计算机学院韩老师E-mail:hxy@fjtv.net2第二章算法第一节程序的灵魂-----算法第二节算法的概念第三节简单算法举例第四节算法的特性第五节算法的表示方法第六节结构化程序设计方法3第一节程序的灵魂----算法程序应包括对数据的描述和对数据处理的描述1．对数据的描述，即数据结构。数据结构是计算机学科的核心课程之一，在C语言中，系统提供的数据结构，以数据类型的形式出现2．对数据处理的描述，即计算机算法。算法是为解决一个问题而采取的方法和步骤，是程序的灵魂。为此，著名计算机科学家沃思（Nikiklaus

2、Wirth）提出一个公式：数据结构+算法=程序4第一节程序的灵魂----算法3．实际上，应采用结构化程序设计方法进行设计，并用某一种计算机语言表示。可以表示如下：程序=算法+数据结构+程序设计方法+语言工具和环境5第二节算法的概念算法是为解决一个问题采取的方法和步骤。计算机算法分类数值算法求方程的根求函数的定积分非数值算法图书检索人事管理6第三节简单算法举例例2.1求1*2*3*4*5今设p为被乘数，i为乘数。用自然语言表示算法如下：S1：使p=1S2：使i=2S3：使p*i，乘积仍放在变量p中，可表示为p*i→pS4：使i的值加1，即i

3、+1→iS5：如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和步骤S5；否则，算法结束。最后得到的p的值就是5！的值。7第三节简单算法举例如果题目改为求1*3*5*7*9*11：算法只须稍做如下改动即可：S1：使p=1S2：使i=3S3：使p*i，乘积仍放在变量p中，可表示为p*i→pS4：使i的值加1，即i+2→iS5：如果i不大于11，返回重新执行步骤S3以及其后的步骤S4和步骤S5；否则算法结束。8第三节简单算法举例例2.2有50个学生，要求将他们之中成绩在80分以上者打印出来。用N表示学生学号，N1代表第一个学生的学号，N

4、i代表第i个学生的学号。用G代表学生成绩，Gi代表第i个学生的成绩。算法可表示如下：S1：使i=1S2：如果gi≥80，则打印ni和gi，否则不打印。S3：i+1→iS4：如果i≤50，返回S2，继续执行，否则，算法结束。9第三节简单算法举例例2.3判定2000—2500年中的每一年是否闰年，并将结果输出。闰年的条件是：①能被4整除，但不能被100整除。如1996年，2004年；②能被100整除，又能被400整除。如1600年，2000年。不符合这两个条件的年份就不是闰年。10第三节简单算法举例算法可表示如下：S1：2000→yS2：若y

5、不能被4整除，输出y“不是闰年”。转S5S3：若y能被4整除，不能被100整除，则输出y“是闰年”。然后转S5S4：若y能被100整除，又能被400整除，则输出y“是闰年”，否则输出y“不是闰年”。S5：y+1→yS6：当y≤2500时，转S2继续执行，否则，算法结束。11第三节简单算法举例例2.4求1-1/2+1/3-1/4+……+1/99-1/100用自然语言表示算法如下：S1：sign=1S2：sum=1S3：deno=2S4：sign=(-1)*signS5：term=sign*(1/deno)S6:sum=sum+termS7:

6、deno=deno+1S8:若deno≤100返回S4；否则算法结束。12第三节简单算法举例例2.5对一个大于或等于3的正整数，判断它是不是一个素数。用自然语言表示算法如下：S1：输入n的值S2：i=2S3：n被i除，得余数rS4：如果r=0，表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5S5：i+1→iS6:如果i≤n-1,返回S3；否则打印n“是素数”。算法结束。13第四节算法的特性有穷性算法要包含有限的步骤确定性每一步必须明确有零个或多个输入需要从外界获取必要的信息有一个或多个输出需要把求得得解进行输出有效性每一步都

7、能有效地执行14第五节算法的表示方法设计算法3.1自然语言（前面就是用自然语言表示的）3.2传统流程图3.3改进的流程图3.4N-S图（盒图）3.5PAD图（问题分析图）3.6伪代码实现算法3.7计算机语言153.2传统流程图优点：描绘直观，容易掌握缺点：对流程线没有严格控制163.2传统流程图将例2.1求5！的算法用传统流程图表示如下：173.2传统流程图将例2.2的算法用传统流程图表示如下：183.2传统流程图将例2.3的算法用传统流程图表示如下：193.2传统流程图将例2.4的算法用传统流程图表示如下：203.2传统流程图将例2.5

8、的算法用传统流程图表示如下：213.3改进的流程图顺序选择(分支)ABABp真假pA真循环pA假假真ABpG223.3改进的流程图将例2.5的算法用改进的流程图可表示如右：233.4N-S图（