算法的概念及程序框图

1、算法的概念,简单地说，算法就是解决问题的程序或步骤。,例1：设计一个算法，判断7是否为质数。,算法：,第一步，用2除7，得到余数1。因为余数不为0，所以2不能整除7。,第二步，用3除7，得到余数1。因为余数不为0，所以3不能整除7。,第三步，用4除7，得到余数3。因为余数不为0，所以4不能整除7。,第四步，用5除7，得到余数2。因为余数不为0，所以5不能整除7。,第五步，用6除7，得到余数1。因为余数不为0，所以6不能整除7。因此，7是质数。,例2：设计一个算法，判断53是否为质数。,第一步，用2除53，得到余数1。因为余数不为0，所以2不能整除53。,第二步，用3除53，得到余数2。因为余数

2、不为0，所以3不能整除53。,第三步，用4除53，得到余数1。因为余数不为0，所以4不能整除53。,第五十一步，用52除53，得到余数1。因为余数不为0，所以52不能整除53。因此，53是质数。,算法的基本特征:,明确性与有效性:算法对每一个步骤都有确切的,能有效执行且得到确定结果的,不能模棱两可。 有限性:算法应由有限步组成, 应在有限多步内结束,并给出计算结果 顺序性:算法从初始步骤开始,分为若干明确的步骤,每一步都只能有一个确定的继任者,只有执行完前一步才能进入到后一步,并且每一步都确定无误后,才能解决问题。 不唯一性:求解某一个问题的解法不一定是唯一的,对于同一个问题可以有不同的解法,

3、算法的表示,描述算法可以有不同的方式,常用的有自然语言、程序框图、程序设计语言等.,自然语言就是人们日常使用的语言,可以是汉语、英语或数学语言等.用自然语言描述算法的优点是通俗易懂,当算法中的操作步骤都是顺序执行时比较容易理解.缺点是如果算法中包含判断和转向,并且操作步骤较多时,就不那么直观清晰了.,(1)自然语言,(2)程序框图,(3)程序设计语言,1.1.2程序框图中讲解,1.2基本算法语句中讲解,、一位商人有9枚银元，其中有1枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？,按照这样的理解,我们可以设计出很多具体数学问题的算法.下面看几个例子:,1,第一步:将9枚银元平均分成三

4、组,将其中两组放在天平的两边. 如果天平平衡, 则假的银元必定在另外一组;如果天平不平衡,则假的银元必定在较轻的一组;,第二步:将有假银元的一组金币中,取出两枚银元,分别放在天平的两边.如果天平平衡,则假的银元必定是剩余的;如果天平不平衡,则假的银元必定在较轻的一边.,、一个农夫带着一条狼、一头山羊和一篮蔬菜要过河,但只有一条小船.乘船时,农夫只能带一样东西.当农夫在场的时候,这三样东西相安无事.一旦农夫不在,狼会吃羊,羊会吃菜.请设计一个算法,使农夫能安全地将这三样东西带过河.,第一步:农夫带羊过河;,第二步:农夫独自回来;,第三步:农夫带狼过河;,第四步:农夫带羊回来;,第五步:农夫带蔬菜

5、过河;,第六步:农夫独自回来;,第七步:农夫带羊过河.,2,、给出求1+2+3+4+5+6的一个算法.,解法1.按照逐一相加的程序进行.,第一步:计算1+2,得3;,第二步:将第一步中的运算结果3与3相加得6;,第三步:将第二步中的运算结果6与4相加得10;,第四步:将第三步中的运算结果10与5相加得15;,第五步:将第四步中的运算结果15与6相加得21.,3,解法2.可以运用下面公式直接计算.,第一步:取 n =6;,第二步:计算 ;,第三步:输出计算结果.,点评:解法1繁琐,步骤较多; 解法2简单，步骤较少. 找出好的算法是我们的追求目标.,例2.写出用“二分法”求方程 x2-2=0（x0

6、） 的近似解的算法.,第一步，令f(x)=x2-2，给定精确度d;,第二步，确定区间a，b，满足f(a)f(b)0;,第三步，取区间中点m= ;,第四步，若f(a)f(m) 0，则含零点的区间为a，m; 否则,含零点的区间为m，b. 将新得到的含零点的区间仍记为a，b.,第五步，判断a，b的长度是否小于d或f(m)是否等于0, 若是,则m是方程的近似解;否则,返回第三步.,算法步骤：,评析:实际上,上述步骤就是在求 的近似值.,1.任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.,课堂练习,(P5练习1),2.任意给定一个大于1 的正整数n,设计一个算法求出n的所有因数.,课堂练习

7、,(P5练习2),3.你要乘火车去外地办一件急事,请你写出从自己房间出发到坐在车厢内的三步主要算法.,第一步:去车站；,第二步:买车票;,第三步:凭票上车对号入座.,课堂练习,1.知识结构,算法的概念,算法的步骤,算法的特点,算法,课堂小结,2.算法的特点:思路简单清晰,叙述复杂,步骤繁琐,计算量大,完全依靠人力难以完成.而这些恰恰就是计算机的特长,它能不厌其烦地完成枯燥的、重复的繁琐的工作. 正因为这些,现代算法的作用之一就是使计算机代替人完成某些工作,这也是我们学习算法的重要原因之一.,3.设计算法的注意事项: (1)认真分析问题,联系解决此问题的一般数学方法; (2)综合考虑此类问题中可

8、能涉及的各种情况; (3)借助有关的变量或参数对算法加以表达; (4)将解决问题的过程划分为若干个步骤; (5)然后用简练的语言将各个步骤表示出来.,课堂小结,现有有限个实数，怎样从中找出最大值？,先假定这些实数中的第一个数为“最大值”。,将这些实数中的下一个数与“最大值”比较，如果它大于此“最大值”，这时就假定“最大值”是这个实数。,如果还有其他实数，重复第二步。,一直到没有可比的数为止，这时假定的“最大值”就是这有限个实数的最大值。,第一步:,第二步:,第三步:,第四步:,思 考,算法1：,第二步：计算10150；,第三步：写出运算结果,算法2：,第一步：取n=100；,第二步：计算,第三

9、步：写出运算结果,写出求1+2+3+ +100的一个算法,(1+100)+(2+99)+ +(50+51)；,第一步：将原式变形为,你会了吗？,点评:解法1繁琐,步骤较多; 解法2简单，步骤较少. 找出好的算法是我们的追求目标.,问题:,如果现在让你向全班同学介绍一个陌生人的外表形象,有两种方法你可以选择:一种方法是用语言向大家描述,另一种方法是就将陌生人的照片拿给大家看,你们会选择哪一种 ?,1.1.2程序框图和 算法的基本逻辑结构(1),程序框图又称流程图，是一种用程序框、流程线及文字说明来表示算法的图形。,思考1:“判断整数n（n2）是否为质数”的算法步骤如何？,第一步，给定一个大于2的

10、整数n；,第二步，令i=2；,第三步，用i除n，得到余数r；,第四步，判断“r=0”是否成立.若是，则n 不是质数，结束算法；否则，将i 的值增加1，仍用i表示；,第五步，判断“i(n-1)”是否成立，若是， 则n是质数，结束算法；否则，返回 第三步.,思考2:我们将上述算法用下面的图形表示：,输入n,i=2,r=0?,是,n不是质数,n是质数,否,求n除以i的余数r,i=i+1,in-1或r=0?,否,是,(1),(2),(3),问:这些分解框图各有什么特点?,顺序结构,条件结构,循环结构,算法的三种基本逻辑结构,解：求面积的算法: 第一步:输入三角形三条边的边长a,b,c 第二步:计算 第

11、三步:计算 第四步:输出三角形的面积S,图示:,输出S,例3、已知一个三角形的三边边长分别是a,b,c,利用海伦-秦九韶面积公式,求三角形的面积.,顺序结构是任何一个算法都不可缺少的基本结构，它由若干个依次执行的处理步骤组成。,开始,结束,输入a,b,c,例1 一个笼子里装有鸡和兔共m只，且鸡和兔共n只脚，设计一个计算鸡和兔各有多少只的算法，并画出程序框图表示.,理论迁移,算法分析：,第一步，输入m，n.,第二步，计算鸡的只数 .,第三步，计算兔的只数y=m-x.,第四步，输出x，y.,程序框图：,顺序结构的程序框图的基本特征：,小结作业,（2）各程序框从上到下用流程线依次连接.,（1）必须有

12、两个起止框，穿插输入、输出框和处理框，没有判断框.,（3）处理框按计算机执行顺序沿流程线依次排列.,条件结构:在算法流程中需根据条件是否成立有不同的流向的结构.,双 分 支 的 条 件 结 构,非 对 称 的 条 件 结 构,否,图示:,开始,存在这样 的三角形,结束,解：判断三角形存在的算法: 第一步:输入正实数a,b,c 第二步:判断a+bc,b+ca,c+ab是否都成立,若是,则存在这样的三角形,若不是,则不存在这样的三角形.,a+bc,b+ca, c+ab是否同 时成立?,输入a,b,c,是,不存在这样 的三角形,例4、任意给定3个正实数,判断以这3个数为三边边长的三角形是否存在.,例

13、5.设计算法,求一元二次方程ax2+bx+c=0,画出相应的流程图,例5.设计算法,求一元二次方程ax2+bx+c=0,画出相应的流程图,1.1.2程序框图和 算法的基本逻辑结构(2),三种基本逻辑结构： （1）顺序结构是由若干个依次执行的步骤组成的，这是任何一个算法都离不开的基本结构。 （2）条件结构 在一个算法中，经常会遇到一些条件的判断，算法的流程根据条件是否成立有不同的流向。 （3）循环结构 在一些算法中，经常会出现从某处开始，按照一定的条件反复执行某些步骤的情况。,(1),(2),(3),试判断下列流程图分别属于哪种逻辑结构？,条件结构,顺序结构,循环结构,反复执行的步骤称为循环体。

14、,循环体,满足条件？,是,否,满足条件？,是,否,在执行了一次循环体后，对条件进行判断，如果条件不满足，就继续执行循环体，直到条件满足时终止循环。,当型循环结构,在每次执行循环体前，对条件进行判断，当条件满足时，执行循环体，否则终止循环。,直到型循环结构,例1:设计一个计算1+2+3+100的值的算法,并画出程序框图.,算法分析:,第1步:0+1=1; 第2步:1+2=3; 第3步:3+3=6; 第4步:6+4=10 第100步:4950+100=5050.,第(i-1)步的结果+i=第i步的结果,各步骤有共同的结构:,为了方便有效地表示上述过程,我们引进一个累加变量S来表示每一步的计算结果,

15、从而把第i步表示为 S=S+i,S的初始值为0,i依次取1,2,100,由于i同时记录了循环的次数,所以i称为计数变量.,程序框图:,开始,i=1,S=0,S=S+i,i=i+1,i100?,是,输出S,结束,否,直到型循环结构,开始,i=1,S=0,i100?,是,S=S+i,i=i+1,否,输出S,结束,当型循环结构,直到型循环在执行了一次循环体之后,对控制循环条件进行判断,当条件不满足时执行循环体,满足则停止.(反复执行循环体,直到条件满足),开始,i=1,S=0,S=S+i,i=i+1,i100?,是,输出S,结束,否,直到型循环结构,说明:(1)一般地,循环结构中都有一个计数变量和累

16、加变量.计数变量用于记录循环次数,同时它的取值还用于判断循环是否终止,累加变量用于输出结果.累加变量和计数变量一般是同步执行的,累加一次,记数一次.,当型循环在每次执行循环体前对循环条件进行判断,当条件满足时执行循环体,不满足则停止;(当条件满足时反复执行循环体),开始,i=1,S=0,i100?,是,S=S+i,i=i+1,否,输出S,结束,当型循环结构,例2. 画出计算 值的一个算法 程序框图.,开始,输出s,结束,i10,s=s+1/i,i=i+1,i=1,s=0,是,否,例3. 设计一个求满足“1+3+5+i2008” 的i的最小值的算法，并画出程序框图,解:在这个问题中，需要累加多少

17、次，事先并不知道，为此我们采用直到型的循环.,例4. 画出对x=1，2，3，10， 求x2的算法的程序框图.,开始,结束,x10,y=x2,x=x+1,x=1,是,否,输出y,例5、某工厂2005年生产总值200万元，技术革新后预计以后每年的年生产总值比上一年增长5%，设计一个程序框图，输出预计年生产总值超过300万元的最早年份。,（1）确定循环体,t=0.05a,设a为某年的年生产总值，t为年生产总值的年增长量，n为年份，则循环体为：,a=a+t,n=n+1,(2)初始变化量：2005年生产总值看成计算起点，则n=2005，a=200,（3）设定循环控制条件：,当年生产总值超过300万元时终

18、止循环，可以通过判断“a300”是否成立来控制循环,例6.设计计算13+33+53+993的算法程序，并画出相应的流程图。,算法如下:,p=0;,i =1;,S1,S2,S3,p=p +i 3;,S4,i =i+2;,S5,若i 99,则输出p,否则转S3.,程序框图的画法,下面，我们根据例的算法步骤，利用三种基本逻辑结构画出程序框图，表示用“二分法”求方程x2-2=0(x0)的近似解的算法,(1)算法步骤中的“第一步”“第二步”和“第三步”可以用下面顺序结构来表示,(2)算法步骤中的“第四步”可以用条件结构来表示在这个条件结构中，“否”分支用“a=m”表示含零点的区间为m,b，并把这个区间仍记成a,b；“是”分支用“b=m”表示含零点的区间为a,m，同样把这个区间仍记成a,b,(3)算法步骤中的“第五步”包含一个条件结构，这个条件结构与“第三步”“第四步”构成一个循环结构，循环体由“第三步”和“第四步”组成，终止循环的条件是“a-bd或f(m)=0