1算法与程序框图.ppt

,算法与程序框图,1.1,主要内容,1.1.1算法的概念,1.1.2程序框图,1.1.3程序框图的画法,算法的概念,1.1.1,第一步:-2得:5y=3,第二步:解得:,对于一般的二元一次方程组其中也可以按照上述步骤求解.,这些步骤就构成了解二元一次方程组的算法,我们可以根据这一算法编制计算机程序,让计算机来解二元一次方程组.,算法的概念与特征,算法(algorithm)这个词出现于12世纪,指的是用阿拉伯数字进行算术运算的过程.,在数学上,现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤,这些程序或步骤必须是明确和有效的,而且能够在有限步之内完成.,1、有穷性:算法的有穷性是指算法必须能在执行有限个步骤之后终止;2、确切性:算法的每一步骤必须有确切的定义；3、输入项:一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；4、输出项:一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；5、可行性:算法中执行的任何计算步都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成。（也称之为有效性）,算法的概念与特征,（1）设计一个算法，判断7是否为质数；（2）设计一个算法，判断35是否为质数.,例1：,算法分析：,（1）根据质数的定义，可以这样判断：依次用26除7，如果它中有一个能整除7，则7不是质数，否则7是质数.（2）同理，也可以按上述方法判断.,思考：任意给定一个大于1的整数n,你能设计一个程序或步骤对n是否为质数做出判定吗？,算法分析:,第一步:判断n是否等于2.,若n=2,则n是质数;,若n2,则执行第二步.,第二步:依次检验2(n-1)这些整数是不是n的因素,即是不是整除n的数.若有这样的数,则n不是质数;若没有这样的数,则n是质数.,说明:用语言描述一个算法,最便捷的方式就是按解决问题的步骤进行描述.每一步做一件事情.,例2:用二分法设计一个求方程x2-2=0的近似根的算法.,算法分析:,设所求近似根与精确解的差的绝对值不超过=0.005.,第一步:令f(x)=x2-2.因为f(1)0,所以设a=1,b=2.,第二步:令m=(a+b)/2判断f(m)是否为0.若是,则m为所求;若否,则继续判断f(a)f(m)大于0还是小于0.,第四步:判断|a-b|7时),求该函数值的算法分析:,第一步:输入每月用水量x;第二步:判断x是否不超过7.若是,则y=1.2x;若否,则y=1.9x-4.9.第三步:输出应交纳的水费y.,知识小结,1、理解算法的概念和特征2、学会使用自然语言描述一个算法的步骤,程序框图,1.1.2,算法步骤有明确的顺序性，而且有些步骤只有在一定条件下才会被执行，有些步骤在一定条件下会被重复执行.算法可以用自然语言来描述，但为了使算法的程序或步骤表达得更为直观、准确，我们更经常地用图形方式来表示它。程序框图又称流程图，是一种用程序框、流程线及文字说明来表示算法的图形一个程序框图包括以下几部分：表示相应操作的程序框；带箭头的流程线；程序框外必要的文字说明。,1.程序框图,程序框图的概念及其组成,构成程序框的图形符号及其作用,开始,输入n,i=2,求n除以i的余数r,i的值增加1，仍用i表示,in-1或r=0?,r=0?,N不是质数,N是质数,结束,否,判断整数n（n2)是否为质数,程序框图范例：,in-1且r0,in-1，r0in-1，r=0in-1，r=0,学习这部分知识的时候，要掌握各个图形的形状、作用及使用规则，画程序框图的规则如下：1、使用标准的图形符号。2、框图一般按从上到下、从左到右的方向画。3、除判断框外，大多数流程图符号只有一个进入点和一个退出点。判断框是具有超过一个退出点的唯一符号。4、判断框分两大类，一类判断框是“是”与“否”两分支的判断，而且有且仅有两个结果；另一类是多分支判断，有几种不同的结果。5、在图形符号内描述的语言要非常简练清楚。,循环结构,条件结构,开始,输入n,i=2,求n除以i的余数r,i的值增加1，仍用i表示,in-1或r=0?,r=0?,N不是质数,N是质数,结束,否,顺序结构,算法的三种基本逻辑结构,算法的三种基本逻辑结构,否,顺序结构,循环结构,条件结构,算法千差万别，但都是由这三种基本逻辑结构构成的.,你能说出这三种基本逻辑结构的特点吗？条件结构与循环结构有什么区别和联系？,思考：,（1）顺序结构顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的，它是由若干个依次执行的处理步骤组成的，它是任何一个算法都离不开的一种基本算法结构。顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来，按顺序执行算法步骤。,步骤n,步骤n1,例3、已知一个三角形的三边分别为a、b、c，利用海伦-秦九韶公式设计一个算法，求出它的面积，并画出算法的程序框图。算法步骤：（自然语言）第一步,输入三角形三条边的边长a、b、c.第二步,计算p.第三步,计算S,第四步，输出S.,顺序结构举例,开始,输入a,b,c,结束,p,S,输出S,算法步骤：（自然语言）,第一步,输入三角形三条边的边长a,b,c.,第二步,计算p.第三步,计算S.第四步，输出S.,（2）条件结构在一个算法中，经常会遇到一些条件的判断，算法的流程根据条件是否成立有不同的流向.条件结构就是处理这种过程的结构.分类是算法中经常发生的事情，条件结构的主要作用就是表示分类.条件结构可用程序框图表示为下面两种形式.,步骤A,步骤B,满足条件？,否,是,步骤A,满足条件？,否,是,例4任意给定3个正实数,设计一个算法,判断分别以这3个数为三边边长的三角形是否存在.画出这个算法的程序框图.,开始,输入a，b，c,a+bc，a+cb，b+ca是否同时成立？,存在这样的三角形,不存在这样的三角形,结束,否,是,条件结构举例,算法步骤如下：第一步，输入3个正实数a,b,c.第二步，判断a+bc，a+cb，b+ca是否同时成立.若是，则存在这样的三角形;否则，不存这样的三角形.,程序框图1,输入a，b，c,存在这样的三角形,否,是,不存在这样的三角形,c+ab？,b+ca？,a+bc？,是,是,开始,结束,否,否,程序框图2,例5设计一个求解一元二次方程,算法步骤：,第一步，输入a，b，c.,第二步，计算判别式=b24ac.,第三步，判断0是否成立.若是，则计算p,q的值.否则，输出“方程没有实数根”，结束算法.,开始,输入a，b，c,=b24ac,x1=p+qx2=p-q,0?,0?,输出x1,x2,输出p,方程无实数根,结束,是,否,是,否,的算法，并画出程序框图表示.,（3）循环结构,循环结构指的是按照一定的条件反复执行的某些算法步骤.,反复执行的步骤称为循环体.,执行一次循环体后，对条件进行判断，如果条件不满足，就继续执行循环体，直到条件满足时终止循环.,在每次执行循环体前，对条件进行判断，当条件满足，执行循环体，否则终止循环.,直到型,当型,例6设计一个计算1+2+3+100的值的算法，并画出程序框图.,第一步：确定首数a，尾数b，项数n；,第二步：利用公式“S=n(a+b)/2”求和；,第三步：输出求和结果。,算法1：,条件结构举例,开始,i=1,S=0,i=i+1,S=S+i,i100?,输出S,结束,否,是,例6：设计一个计算1+2+3+100的值的算法，并画出程序框图.,第1步，011.第2步，123.第3步，336.第4步，6410.第100步，49501005050.,算法2：第一步，令i1，S0.第二步，若i100成立，则执行第三步;否则，输出S，结束算法.第三步，SSi.第四步，i=i+1,返回第二步.,当型循环结构,循环结构,直到型结构,当型结构,P15.思考：设计一个算法，表示输出1，12，123，123(n-1)+n(nN*)的过程.,结束,开始,S=0,i=1,S=S+i,i=i+1,in,Y,N,输入n,输出S,第一步，令i=1,S=0.第二步，计算S=S+i.第三步，计算i=i+1.第四步，判断in是否成立，若是，则输出S;否则返回第二步.,算法：,例7某工厂2005年的年生产总值为200万元，技术革新后预计以后每年的年生产总值都比上一年增长5.设计一个程序框图，输出预计年生产总值超过300万元的最早年份.,算法步骤：,第一步，输入2005年的年生产总值.,第二步，计算下一年的年生产总值.,第三步，判断所得的结果是否大于300.若是，则输出该年的年份;否则，返回第二步.,结束,开始,输出n,a=200,t=0.05a,a=a+t,n=n+1,a300?,Y,（1）确定循环体：设a为某年的年生产总值，t为年生产总值的年增长量，n为年份，则循环体为t=0.05a,a=a+t,n=n+1.,（2）初始化变量：n=2005，a=200.,（3）循环控制条件：a300,结束,开始,输入n,a=200,t=0.05a,a=a+t,n=n+1,a300?,Y,结束,开始,输入n,a=200,t0.05a,aa+t,nn+1,a300?,N,Y,直到型,当型,知识小结,顺序结构的程序框图的基本特征：,1、必须有两个起止框，穿插输入、输出框和处理框，没有判断框.2、各程序框从上到下用流程线依次连接.,知识小结,条件结构的程序框图的基本特征：,1、程序框图中必须有两个起止框，穿插输入、输出框和处理框，一定有判断框.2、条件结构的程序框图各有两种形式.,知识小结,循环结构的程序框图的基本特征：,1、循环结构中包含条件结构，条件结构中不包含循环结构.2、循环结构的程序框图各有两种形式.,程序框图的画法,1.1.3,例:写出用“二分法”求方程x220(x0)的近似解的算法.,第一步：令f(x)=x2-2,给定精确度d,第二步：确定区间a,b,满足f(a)f(b)0,第四步：若f(a)f(m)0,则含零点的区间为a,m,否则含零点的区间为m,b,将新得到的含零点的区间仍记为a,b,第五步：判断a,b的长度是否小于d或f(m)是否等于零,若是,则m是方程的近似解，否则返回第三步.,程序框图的画法举例,(1)算法步骤中的“第一步”、“第二步”、“第三步”可以用顺序结构来表示。,(2)算法步骤中的“第四步”，可以用条件结构来表示。,是,否,(3)算法步骤中的“第五步”包含一个条件结构，这个条件结构与“第三步”，“第四步”构成一个循环结构。,第三步,第四步,输出m,是,否,(4)将各步骤的程序框图连接起来，并画出“开始”和“结束”两个终端框，就得到了表示整个算法的程序框图（下图）,是,否,输出m,开始,结束,是,否,设计一个算法的程序框图的步骤:,第一步,用自然语言表述算法步骤.,第二步,确定每一个算法步骤所包含的逻辑结构,并用相应的程序框图表示,得到该步骤的程序框图.,第三步,将所有步骤的程序框图用流程线连接起来,并加上终端框,得到表示整个算法的程序框图.,输出,开始,i=i+1,i