《计算机导论_算法简介_new》由会员分享，可在线阅读，更多相关《计算机导论_算法简介_new（40页珍藏版）》请在金锄头文库上搜索。
1、算 法 简 介,什么是程序? “在数据的某些特定表示方式和结构的基础上对抽象算法的具体表述” 程序: 程序 = 数据结构 + 算法,数据结构（data structure）：是操作的对象，在程序中指定的数据的类型和组织形式； 算法（algorithm）：对操作的描述，为解决一个问题而采取的方法和步骤。,著名计算机科学家沃思提出的公式,程序的灵魂算法,广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。,方法1：1+2，+3，+4， 一直加到100 方法2：(100+1)+(99+2)+(50+51) = 50*101,对同一个问题，可有不同的解题方法和步骤,例： 求,2.1 算法的概念
2、,计算的目的是对数据进行加工处理，以得到期望的结果。 其中算法是灵魂，解决“做什么”和“怎么做”的问题。 因此，认真考虑和设计数据结构和操作步骤（算法）就 一个程序设计任务的关键所在。,计算机程序是用某种程序设计语言描述的解题算法,程序,要求： 在高级语言的学习中，一方面要熟练掌握语言的 语法, 它是算法实现的基础, 另一方面必须认识到算法 的重要性，加强思维训练，以写出高质量的程序。,算法的概念 为解决一个问题而采取的方法和步骤。 如：一个交响乐的乐谱就是一个乐曲的算法，菜谱,程序设计步骤,例2.1: 求12345,步骤1：先求12，得到结果2 步骤2：将步骤1得到的乘积2再乘以3，得到结果
3、6 步骤3：将6再乘以4，得24 步骤4：将24再乘以5，得120 ,太繁琐,如果要求121000，则要写999个步骤,2.2 简单算法举例,改进的算法： S1: 使p=1 S2: 使i=2 S3: 使pi, 乘积仍然放在在变量p中，可表示为pip S4: 使i的值+1，即i+1i S5: 如果 i5, 转向S3； 否则，算法结束。,被乘数: 初值1，积的结果用p 乘数分别为 i=2, 3, 4, 5,算法简练,改进的算法：,如果计算100！只需将S5: 若 i5 改成 i100 即可。 如果该求1357911，算法也只需做很少的改动： S1: 1p S2: 3i S3: pip S4: i+
4、2i S5: 若i11, 转向S3，否则，结束。 该算法不仅正确，而且是计算机较好的算法，因为计算机是高速运算的自动机器，实现循环轻而易举。,如果再求 4914192429 呢？ S1: 4p S2: 9i S3: pip S4: i+5i S5: 若i29 ,转向S3，否则，结束。,问题：,如果，n表示学生学号，ni表示第 i个学生学号； g表示学生成绩， gi表示第 i个学生成绩； 则算法可表示如下： S1: 1i S2: 如果gi 80，则打印ni 和 gi。 S3: i+1i S4: 若i50, 转向S2，否则，结束。,【例2-2】,有50个学生，要求将他们之中成绩在80分以 上者打印
5、出来。,【例2-3】判定1985年2500年中的每一年是否闰年，将 结果输出。,1） 1985=y 2）若y能被4整除，但不能被100整除或y能被100整除，又能被400整除，则输出y“是闰年”，否则输出y“不是闰年” 3）下一年，即：y+1 = y 4) 当y=2500时，转向2）否则， 算法结束。,方法2：直接按闰年的条件进行判定,2）若y不能被4整除，则输出y“不是闰年” 否则但若y不能被100整除，则输出y“是闰年” 否则但若y能被400整除，则输出y“是闰年” 否则输出y“不是闰年”,即y能被4整除,即y能被100整除,即y不能被400整除,1）1985=y,3）下一年，即：y+1=
6、y 4）当y=2500时，转向2）；否则， 算法结束。,算法可以表示如下： 1）sign=1； 2）sum=1； 3）deno=2； 4）sign=（-1）*sign； 5）term=sign*（1/deno）； 6）sum=sum+term； 7）deno=deno+1； 8）如果 deno=100，转向4），否则算法结束。,【例2-4】求,的值。,对一个大于或等于3的正整数，判断它 是不是一个素数。,概念：所谓素数，是指除了1和该数本身之外，不能被其它任何整数整除的数。例如，13是素数。因为它不能被2，3，4，12整除。,分析：判断一个数 n(n3)是否素数的方法： 将 n作为被除数，将2
7、到 (n-1)各个整数轮流作为除数，如果都不能被整除，则n为素数。,【例2-5】,算法可表示如下： S1: 输入n的值 S2: i=2 S3: n被i 除，得余数r S4: 如果r=0，表示n能被i整除，则打印n“不是素数”， 算法结束；否则执行S5 S5: i+1i S6: 如果in-1，返回S3； 否则打印n“是素数”， 算法结束。 改进： S6: 如果i sqrt(n),【例2-6】 输入三个数，然后输出其中最大的数。 分析：首先要定义三个变量A、B、C，将三个数依次输入到A、B、C中，另外，再定义一个MAX保存最大数。首先把A与B比，大的数放在MAX中，再把MAX与C比，又把大的数放在
8、MAX中，最后把MAX输出。 算法可以描述如下： 1）输入A、B、C； 2）A与B中大的一个放在MAX中； 3）把C与MAX中大的一个放入MAX中； 4）输出MAX，MAX即为最大数。,2）若AB,则MAXA,否则 MAXB；,3）若CMAX，则 MAXC；,其中的2）、3）步无法直接转化为程序语句，可继续细化：,2.3 算法的特性,有穷性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 确定性：算法中的每一个步骤都应当是清晰的，无歧义的。 有零个或多个输入：输入是指在执行算法时需要从外界取得必要的信息。 有一个或多个输出：算法的目的是为了求解，“解” 就是输出。 有效性：算
9、法中的每一个步骤都应当能有效地执行，并得到确定的结果 。,常用的算法表示有自然语言、流程图（传统流程图、结构化流程图）、伪代码、PAD图。 1、传统流程图：利用几何图形的框来代表各种不同性质的操作，用流程线来指示算法的执行方向。 1）常见的流程图符号：,2.4 算法的表示,【例2-1】 流程图表示如下：,如果需要将最后结果打印出来，可在菱形框的下面加一个输出框。,【例2-2】 流程图表示如下：,如果包括这个输入数据的部分，流程图为,【例2-4】 流程图表示如下：,Y,【例2-5】 流程图表示如下：,将例2.5判断素数的算法用流程图表示,【例2-5 】流程图表示如下：,输出MAX,MAXC,T,
10、MAXB,MAXA,F,T,AB,开始,输入A,B,C,结束,CMAX,F,一个流程图包括： 1. 表示相应操作的框 2. 带箭头的流程线 3. 框内外必要的文字说明,2、改进的流程图 1）算法的结构化描述 经研究发现，任何复杂的算法都可以由顺序结构、选择结构和循环结构这三种基本结构组成，因此构造一个算法的时候，可以这三种结构作为基本单元，结构清晰，易于正确性验证，易于纠错，这种方法就是结构化方法。 遵循这种方法的程序设计，就是结构化程序设计。,2）三种基本结构的流程图,A、顺序结构,B、选择结构,条件,B,A,T,F,a）,A,条件,T,F,b）,派生的多分支选择,三种基本结构的共同特点：
11、l 只有一个入口； 只有一个出口； 结构内的每一部分都有机会被执行到； l 结构内不存在“死循环”。,C、循环结构 a）while型 b）do - while 型,F,条件,A,T,3）用NS图描述算法 NS图是由美国的I.Nassi和B.Shneiderman共同提出的，其依据是既然任何算法都是由前面介绍的三种结构组成，那么各基本结构之间的流程线就是多余的。NS图也是算法的一种结构化描述方法。 NS图中，一个算法就是一个大矩形框，框内又包含若干基本框。 三种基本结构的NS图描述如下： A、顺序结构 B、条件结构,C、循环结构,举例 【例2-6】 NS图,1985=y,y不能被4整除,输出y“
12、不是闰年”,是,否,y不能被100整除,是,否,输出y“是闰年”,否,是,y能被400整除,输出y“是闰年”,输出y“不是闰年”,【例2-3】 NS图表示如下：,y+1=y,直到y2500,【例2-4 】 NS图表示如下：,3.PAD（Problem Analysis Digram,HITACHI,1973）,3.PAD（Problem Analysis Digram,HITACHI,1973）,伪代码使用介于自然语言和计算机语言之间的文字和符号来描述算法。,4、用伪代码(Pseudo Code)描述算法,BEGIN sum= 0 t = 1 while t =100 sum=sum+t t
13、= t+1 print t END,5、用计算机语言表示算法,l 用计算机语言表示算法必须严格遵循所用语言的语法规则,【例2-1】求12345 用C+表示。 int main( ) int i,t; t=1; i=2; while(i=5) t=t*i; i=i+1; couttendl; return 0; ,【例2-4】求级数的值。 int main() int sigh=1; float deno=2.0, sum=1.0, term; while(deno=100) sigh= -sigh; term= sigh/ deno; sum=sum+term; deno=deno+1; cout sumendl; return 0; ,2.5 结构化程序设计方法,自顶向下逐步细化 这种过程是将问题求解由抽象逐步具体化的过程， 直到认为可以直接将各小段表达为文字语句为止 模块化设计结构化编码 尤其当程序比较复杂时，根据程序模块的功能将它划分为若干子模块，如此, 相对独立，“分而治之”，直接用与三种基本结构对应的语句，进行结构化的编程。,
