程序框图与算法的基本逻辑结构

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,程序框图与算法的根本逻辑结构,从上节课的例子中可以看出，,用自然语言表示算法的步骤有明显的顺序性，但在处理条件结构和循环结构这样的问题时会显得有点困难，不够直观。,因此，我们有必要探究使算法表达得更加直观、准确的方法。,即,程序框图,判断一个正整数,n,是否是质数的算法,自然语言描述,图形描述,第一步：给定大于,2,的整数,n,第二步,:,令,i=2,第三步,:,用,i,除,n,得到余数,r,第四步:判断r=0是否成立。,假设是，那么n不是质数结束算法。,否那么，将i的值加1，仍用i表示,第五步:判断in-1是否成立。,假设是，那么n是质数，结束算法。,假设不成立，那么返回第三步,开始,输入,n,i=2,求,n,除以,i,的余数,r,r=0?,i=i+1,i(n-1)?,n,不是质数,n,是质数,结束,否,是,是,否,一,、程序框图,1,、程序框图的概念,程序框图又称流程图，是一,种用,程序框,、,流程线,及,文字说,明,来表示算法的图形。,在程序框图中，一个或几个程序,框的组合表示算法中的一个步骤；,带有方向箭头的流程线将程序框,连接起来，表示算法步骤的执行,程序,结束,输入,n,i,=2,求,n,除以,i,的余数,r,i,n-1,或,r,=0?,n,不是质数,n,是质数,否,是,是,否,r,=0?,i,的值增加,1,，仍用,i,表示,开始,表示相应操作的程序框；,带箭头的流程线；,程序框内外必要的文字说明。,思考1：一个程序框图包括几局部呢？,思考,2,：右面的程序框图中，程序框的形状不尽相同，那么不同形状的程序框具有什么不同的功能呢？,结束,输入,n,i,=2,求,n,除以,i,的余数,r,i,n-1,或,r,=0?,n,不是质数,n,是质数,否,是,是,否,r,=0?,i,的值增加,1,，仍用,i,表示,开始,终端框（起止框），,表示一个算法的起始和结束,结束,输入,n,i,=2,求,n,除以,i,的余数,r,i,n-1,或,r,=0?,n,不是质数,n,是质数,否,是,是,否,r,=0?,i,的值增加,1,，仍用,i,表示,开始,输入、输出框,表示一个算法输入和输出的信息,结束,输入,n,i,=2,求,n,除以,i,的余数,r,i,n-1,或,r,=0?,n,不是质数,n,是质数,否,是,是,否,r,=0?,i,的值增加,1,，仍用,i,表示,开始,处理框执行框,赋值、计算,结束,输入,n,i,=2,求,n,除以,i,的余数,r,i,n-1,或,r,=0?,n,不是质数,n,是质数,否,是,是,否,r,=0?,i,的值增加,1,，仍用,i,表示,开始,判断框,判断某一条件是否成立，成立时在出口处标明“是或“Y；不成立时标明“否或“N,结束,输入,n,i,=2,求,n,除以,i,的余数,r,i,n-1,或,r,=0?,n,不是质数,n,是质数,否,是,是,否,r,=0?,i,的值增加,1,，仍用,i,表示,开始,流程线：连接程序框,结束,输入,n,i,=2,求,n,除以,i,的余数,r,i,n-1,或,r,=0?,n,不是质数,n,是质数,否,是,是,否,r,=0?,i,的值增加,1,，仍用,i,表示,开始,流程图一般从上至下“竖着画。但对于一些较大的事件或者过程比较复杂的活动，就会出现“画不下而要换页继续画的现象，那么页与页之间“继续画用什么方式来表示呢？-这就需要用到“连接点了。,例如：从早晨起床到上学这段时间要做的事情，用流程图,表示如下：,图,2,中的小圆圈,O,表示连接点，当一个流程图中有多处需要用到它时，可以在小圆圈内标上序号,连接点,连接点,2.,常见的程序框、流程线及各自表示的功能,O,3.画程序框图的规那么：,1使用标准的框图符号；,2框图一般按从上到下，从左到右的方向画,3除判断框外，大多数框图符号只有一个进入点和一个退出点。判断框是唯一具有超过一个退出点的框图符号；,4在程序框图形内描述语言要简练、清楚。,二、算法的根本逻辑结构,用程序框图表示算法时，算法的逻辑结构展现得非常清楚。例如前面例子中的程序框图中就包含下面三种逻辑结构：,输入,n,i,=2,输出,n,不是质数,输出,n,是质数,是,否,r,=0?,求,n,除以,i,的余数,r,i,n-1,或,r,=0?,否,i,的值增加,1,，仍用,i,表示,是,顺序结构,条件结构,循环结构,尽管算法千差万别,但它们都是由三种根本的逻辑结构构成的。,顺序结构,循环结构,条件结构,结束,输入,n,i,=2,求,n,除以,i,的余数,r,i,n-1,或,r,=0?,n,不是质数,n,是质数,否,是,是,否,r,=0?,i,的值增加,1,，仍用,i,表示,开始,思考：你能说出这三种根本逻辑结构的特点吗？,1.顺序结构：,它是任何一个算法都离不开的一种根本算法结构。,顺序结构是由假设干个依次执行的步骤组成的。,顺序结构可以用程序框图表示为：,步骤,n,步骤,n+1,例,1,(1),写出图中程序框图的运行结果：,开始,输入,a,，,b,a,2,b,4,S,a,/,b,b,/,a,输出,S,结束,图中输出,S,；,5/2,(2)写出以下算法的功能。,开始,输入,a,，,b,d,a,2,b,2,c,输出,c,结束,左图算法的功能,是,；,求两数平方和的算术平方根,例,2,设计一算法：,输入圆的半径,输出圆的面积，,并画出程序框图表示。,算法分析：,第一步：,输入圆的半径,R,第三步：,输出圆的面积,。,开始,结束,输入半径,R,计算S=,R,2,输出面积,S,第二步：,利用公式,“圆的面积,=,圆周率,（半径的平方）”,即,计算圆的面积；,注意：,顺序结构按照从上到下的顺序不能“回头；,例3 一个三角形的三边分别为a，b，c，利用海伦-秦九韶公式设计一个算法，求出它的面积，画出算法的程序框图,程序框图：,开始,结束,输入,a,，,b,，,c,输出,S,算法步骤：,第一步：,输入三角形的三条边长,a,b,c,第二步：,计算,第三步：,计算,第四步：,输出面积,S,。,练习：,1.就1逻辑结构，说出,它的算法功能,开始,输入,a,，,b,结束,sum=a+b,输出,sum,1,2.梯形上底为2，下底为4，高为5，求其面积，设计出该问题的程序框图,开始,输出,结束,答案：1求两个数的和,任意给定一个大于,1,的正整数,n,，设计一个算法求出,n,的所有因数。,算法步骤：,第四步：判断“r=0是否成立，假设是，那么i是 n 的因数；否那么，i不是 n 的因数；,第五步：,i=i+1,第六步：判断“in是否成立，假设是，结束算法；否那么，返回第三步,第一步：,输入一个大于,1,的正整数,n,第二步：,令,i=1,第三步：,用,i,除,n,得到余数,r,2.,条件结构：,在一个算法中，经常会遇到一些条件的判断，算法的流程根据条件是否成立有不同的流向条件结构就是处理这种过程的结构,常见的条件结构可以用程序框图表示为下面两种形式：,满足条件,?,步骤,A,步骤,B,是,否,1.,两个步骤,A,、,B,根据条件选择一个执行,满足条件,?,步骤,A,是,否,2.,根据条件选择是否执行步骤,A,例,4,任意给定,3,个正实数，设计一个算法，判断分别,以这,3,个数为三边边长的三角形是否存在画出这个,算法的程序框图,开始,输入,是否同时成立？,存在这样的三,角形,结束,不存在这样的三,角形,是,否,程序框图：,算法步骤：,第一步：,输入三个正实数,a,b,c,第二步：判断a+bc,b+ca,c+ab是否同时成立。,假设是，那么存在这样的三角形,否那么，不存在这样的三角形,算法：,程序框图,：,开始,输入,a,，,b,，,c,=b,2,-,4,a,c,0,？,=0,？,否,x,1,=p+q,输出,x,1,，,x,2,结束,否,是,x,2,=p,-,q,输出,x,1,=x,2,=p,是,输出“方程没有实数根”,练习：,1.,就逻辑结构，,说出其算法功能,开始,结束,输入,x,x3?,y=x-2,输出,y,y=4-x,否,是,开始,max=a,输入,b,maxb,？,输出,max,结束,max=b,是,否,2.此为某一函数的求值程序图，那么满足该流程图的函数解析式为 不能写成分段函数,3.求函数,的值的算法流程图,开始,输入,x,X6成立，那么输出S，结束算法；,第二步，计算,S=S+i.,第三步，计算,i=i+1.,假设不成立，那么返回第二步,结束,开始,？,是,否,直到型循环结构,还可以这样写算法：,第一步，令,i=1,S=0.,第二步，假设i6成立，那么执行第三步；,第三步，计算,S=S+i.,第四步，计算,i=i+1,，返回第二步。,假设不成立，那么输出S，结束算法,开始,？,结束,是,否,当型循环结构,由于,i,同时记录了循环的次数，所以也称为,计数变量,直到型循环结构与当型循环结构的区别：,1.,直到型先执行循环体后判断条件；,当型先判断条件，然后看是否执行循环体,3.对解决同一问题，如果既可用直到型，又可用当型，那么直到型与当型的条件互为,2.,直到型至少执行一次循环体，,而当型可以不执行循环体。,反条件,直到总循环,当型是循环,练习：,1.如图1为循环结构中的 循环，,？,a,图,(1),是,否,a,？,是,否,2.,如图,(2),的算法输出结果是,_,算法功能是,_,结束,开始,(,图,2),是,否,?,当型,求积为,48,的相邻偶数,.,直到型,把它换成另外一种循环的框图,6,，,8,3.,指出程序框图的运算结果,开始,?,结束,是,否,当箭头指向处时,输出,;,指向处时,输出,.,5,15,4.以以下图为求11000的所有的偶数的和而设计的一个程序框图,将空白处补上,并指明它是循环结构中的哪一种类型,并画出它的另一种循环结构框图,开始,i=2,S=0,i,1000,？,输出,S,结束,S=S+i,i=i+2,是,否,5.,设计求,1+4+7+10+.+40,的值的一个算法,并画出程序框图,.,结束,开始,？,是,否,开始,？,结束,是,否,直到型循环结构,当型循环结构,三、概念形成,概念,1.,程序框图的概念,开始,输入,无实根,结束,起止框,起止框,输入输出框,输入输出框,处理框,判断框,流程线,Y,N,开始,输入,n,i=2,求,n,除以,i,的余数,r,i,的值增加,1,，仍用,i,表示,in-1,或,r=0?,r=0?,N,不是质数,N,是质数,结束,是,否,是,否,判断整数nn2)是否为质数,程序框图范例：,in-1,且,r0,in-1，r 0,i n-1，r=0,in-1，r=0,