1[1].1.2程序框图与算法的基本逻辑结构梦幻一

1.11.1.2程序框图与算法的基本逻辑结构第一章算法复习回顾：算法一词出现在12世纪，指的是用阿拉伯数字进行算术运算的过程，在数学中，算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。现在，算法通常可以编成计算机程序，让计算机执行并解决。1.算法定义：2、算法的基本特征：明确性:算法中的每一个步骤都是确切的,能有效的执行且得到确定的结果,不能模棱两可。有序性:算法从初始步骤开始,分为若干明确的步骤,每一步都只能有一个确定的继任者,只有执行完前一步才能进入到后一步,并且每一步都确定无误后,才能解决问题。不唯一性:求解某一个问题的解法不一定是唯一的,对于同一个问题可以有不同的解法,但算法有优劣之分,好的算法是我们追求的目标.普适性:写出的算法必须能解决一类问题,并且能重复使用,这是设计算法的一条基本原则,这样才能使算法更有价值.有限性:算法应由有限步组成,必须在有限操作之后停止,并给出计算结果。•我们为什么要学习算法？•在解决某些问题时，需要设计出一系列可操作或可计算的步骤来解决问题，这些步骤称为解决这些问题的算法，也就是说算法实际上就是解决问题的一种程序性方法。算法一般是机械的，它的优点是一种通法，只要按部就班的去做，总能得到结果。因此算法式计算科学的基础。•21世纪信息社会的两个主要特征：•“计算机无处不在”•“数学无处不在”••21世纪信息社会对科技人才的要求：••--会用“数学”解决实际问题•--会用计算机进行科学计算11.521.251.3752+2+1.5+1-ab︱a-b︱11211.50.51.50.251.251.50.1251.375………………12+1.5+1.251.375---2+1.5+1.251--22xy1--例2用二分法设计一个求方程x2–2=0的近似根的算法。旧知识回顾：用二分法求函数的零点解决问题×第四步,若f(a)·f(m)0,则含零点的区间为［a,m］；第一步,令.给定精确度d.2()2fxx第二步,给定区间［a,b］,满足f(a)·f(b)＜0．第三步,取中间点．2abm第五步,判断［a,b］的长度是否小于d或者f(m)是否等于０.将新得到的含零点的仍然记为［a,b］.否则，含零点的区间为［m,b］.若是，则m是方程的近似解;否则，返回第三步．算法在数学中，按照一定规则解决某一类问题的明确和有限的步骤称为算法.我们可以用自然语言表述一个算法，但往往过程复杂，缺乏简洁性，因此，我们有必要探究使算法表达得更加直观、准确的方法，可以通过程序框图来实现.“判断整数n（n2）是否为质数”的算法步骤如何？如何将这些步骤更直观的表达出来呢？知识探究：算法的程序框图：第一步，给定一个大于2的整数n；第二步，令i=2；第三步，用i除n，得到余数r；第四步，判断“r=0”是否成立.若是，则第五步，判断“i(n-1)”是否成立，若是，n不是质数，结束算法；将i的值增加1，仍用i表示；否则，则n是质数，结束算法；否则，返回第三步.开始r=0？输出“n是质数”输出“n不是质数”求n除以i的余数ri=2输入nin-1或r=0？是是结束否否i的值增加1，仍用i表示开始r=0？输出“n是质数”输出“n不是质数”求n除以i的余数ri=2输入nin-1或r=0？是是结束否否这种表示算法的图形称为算法的程序框图又称流程图，其中的多边形叫做程序框，带方向箭头的线叫做流程线，你能指出程序框图的含义吗？---用程序框、流程线及文字说明来表示算法的图形.i的值增加1，仍用i表示在上述程序框图中，有4种程序框，2种流程线，它们分别有何特定的名称和功能？图形符号名称功能终端框（起止框）输入、输出框处理框（执行框）判断框流程线表示一个算法的起始和结束表示一个算法输入和输出的信息赋值、计算判断某一条件是否成立，成立时在出口处标明“是”或“Y”；不成立时标明“否”或“N”连接程序框，表示算法步骤的执行顺序开始r=0？输出“n是质数”输出“n不是质数”求n除以i的余数ri=2输入ni的值增加1，仍用i表示in-1或r=0？是是结束否否在逻辑结构上，“判断整数n（n2）是否为质数”的程序框图由几部分组成？顺序结构循环结构条件结构算法的顺序结构：步骤n步骤n+1是由若干个依次执行的步骤组成的.这是任何一个算法都离不开的基本结构，用程序框图可以表示为：i=2输入n若一个三角形的三条边长分别为a，b，c，令，则三角形的面积.你能利用这个公式设计一个计算三角形面积的算法步骤吗？第一步，输入三角形三条边的边长a，b，c.第二步，计算.第三步，计算.第四步，输出S.2abcp()()()Sppapbpc2abcp()()()Sppapbpc开始结束输出S输入a，b，c2abcp++=()()()Sppapbpc=---例3：上述算法的程序框图如何表示？1、任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.第一步：第二步：第三步：给定一个正实数r；计算以r为半径的圆的面积S=πr2;得到圆的面积S.教材5页练习你能画出这个算法的程序框图吗？开始结束输出S输入r2Srp=课内巩固训练1：已知P0（x0,y0）和直线l:Ax+By+C=0,写出求点P0到直线l的距离d的算法，并用程序框图来描述。第一步：第二步：第三步：输入x0,y0,A,B,C.计算输出d.开始结束输出d输入x0,y0,A,B,C0022||AxByCdAB0022||AxByCdAB算法的条件结构：在某些问题的算法中，有些步骤只有在一定条件下才会被执行，算法的流程因条件是否成立而变化.在算法的程序框图中，由若干个在一定条件下才会被执行的步骤组成的逻辑结构，称为条件结构，用程序框图可以表示为下面两种形式：满足条件?是否步骤A步骤B满足条件?是否步骤Aa+b＞c，a+c＞b，b+c＞a是否同时成立？任意给定3个正实数,设计一个算法,判断以这3个数为三边边长的三角形是否存在.画出这个算法的程序框图.第一步:输入3个正实数a,b,c;第二步:判断a+bc,a+cb,b+ca是否同时成立,若是,则存在这样的三角形;否则，不存在这样的三角形.例4：算法步骤如下：开始输入a，b，c存在这样的三角形不存在这样的三角形结束否是设计一个求解一元二次方程ax2+bx+c=0的算法，并画出程序框图。例5：3,,abc第一步：输入个系数24bac第二步：计算算法步骤如下：0,;22bpqaa第三步：判断是否成立。若是，则计算否则，输出“方程没有实数根”，结束算法。1212120;,,,xxpxpqxpqxx第四步：判断是否成立。若是，则输出否则，计算并输出开始输入a，b，cacb42?0abp2aq2?0x1=p+qx2=p-q输出x1,x2输出“方程没有实数根”输出p结束否是否是写出过P(a1,b1)、Q(a2,b2)两点直线斜率的算法：第一步：第二步：第三步：取x1=a1，y1=b1，x2=a2，y2=b2；若x1=x2,输出斜率不存在；若x1≠x2,计算2121;yykxx第四步：输出结果。练习3你能画出这个算法的程序框图吗？x1=x2?是否开始结束输入x1,y1,x2,y22121yykxx输出斜率不存在在算法的程序框图中，由按照一定的条件反复执行的某些步骤组成的逻辑结构，称为循环结构，反复执行的步骤称为循环体，那么循环结构中一定包含条件结构吗？算法的循环结构：循环体满足条件？是否循环体满足条件？是否在执行了一次循环体后，对条件进行判断，如果条件不满足，就继续执行循环体，直到条件满足时终止循环.—直到型循环.在每次执行循环体前，对条件进行判断，如果条件满足，就执行循环体，否则终止循环—当型循环.思考4:计算1+2+3+…+100的值可按如下过程进行：第1步，0+1=1.第2步，1+2=3.第3步，3+3=6.第4步，6+4=10.……第100步，4950+100=5050.第四步，判断i100是否成立.若是，则输出S，结束算法；否则，返回第二步.第一步，令i=1，S=0.第二步，计算S+i，仍用S表示.第三步，计算i+1，仍用i表示.解决这一问题的算法是：思考:用直到型循环结构，这个算法的程序框图如何表示？用当型循环呢？直到型循环：开始i=1i100？是输出S结束S=0i=i+1S=S+i否开始i=1输出S否是S=0S=S+ii≤100？i=i+1当型循环：结束练习1：当型循环结构是i≤6？开始输出S结束i=i+1S=S*i否i=2,S=1开始i6？是输出S结束i=i+1S=S*i否直到型循环结构i=2,S=1画出1×2×3×4×5×6的程序框图练习：教材20页习题A组2:当型循环结构是i≤100？开始输出S结束i=i+1S=S+S*i2否i=1,S=0开始i100？是输出S结束i=i+1S=S+S*i2否直到型循环结构i=1,S=0作业直到型循环：开始i=1i100？是结束S=0i=i+1S=S+i否开始i=1否是S=0S=S+ii≤100？i=i+1当型循环：结束输入n输入n输出S输出S某工厂2005年的年生产总值为200万元，技术革新后预计以后每年的年生产总值都比上一年增长5%.设计一个程序框图，输出预计年生产总值超过300万元的最早年份.第三步，判断所得的结果是否大于300.若是，则输出该年的年份；否则，返回第二步.第一步，输入2005年的年生产总值.第二步，计算下一年的年生产总值.算法分析：（3）设定循环控制条件：当“a＞300”时终止循环.（1）确定循环体：设a为某年的年生产总值，t为年生产总值的年增长量，n为年份，则t=0.05a，a=a+t，n=n+1.（2）初始化变量：n=2005，a=200.循环结构：例5：开始n=2005a=200t=0.05aa=a+tn=n+1a300？结束输出n是否程序框图：作业:P20习题1.1B组：1.作业：P20习题1.1A组：2，3.在学习上，我们要求对实际问题能用自然语言设计一个算法，再根据算法的逻辑结构画出程序框图，同时，还要能够正确阅读、理解程序框图所描述的算法的含义，这需要我们对程序框图的画法有进一步的理解和认识.程序框图的画法：2()2fxx令第一步：第二步：第三步：第四步：第五步：，给定精确度d.确定区间[a，b]，满足f(a)·f(b)0.,2ab取区间中点m=若f(a)·f(m)0,则含零点的区间为否则，含零点的区间为将新得到的含零点的区间仍记为[a,b];判断|a-b|d是否成立或f(m)是否等于0.若是，则m是方程的近似解；否则，返回[a,m],[m，b].第三步.用“二分法”求方程x2-2=0(x＞0)的近似解的算法如何设计？该算法中哪几个步骤可以用顺序结构来表示？这个顺序结构的程序框图如何？2()2fxx令第一步：第二步：第三步：第四步：第五步：，给定精确度d.确定区间[a，b]，满足f(a)·f(b)0.,2ab取区间中点m=若f(a)·f(m)0,则含零点的区间为否则，含零点的区间为将新得到的含零点的区间仍记为[a,b];判断|a-b|d是否成立或f(m)是否等于0.若是，则m是方程的近似解；否则，返回[a,m],[m，b].第三步.令第一步：第二步：2()2fxx，给定精确度d.确定区间[a，b]，满足f(a)·f(b)0.f(x)=x2-2输入精确度d和初始值a，b2abm该算法中哪几个步骤可以用顺序结构来表示？这个顺序结构的程序框图如何？第三步：,2ab取区间中点m=该算法中第四步是什么逻辑结构？这个步骤用程序框图如何表示？第四步：若f(a)·f(m)0,否则，含零点的区间为将新得到的含零点的区间仍记为[a,b];[a,m],f(a)f(m)0?b=m是否a=m2()2fxx令第一步：第二步：第三步：第四步：第五步：，给定精确度d.确定区间[a，b]，满足f(a)·f(b)0.,2