《1111算法的概念及程序框图》由会员分享，可在线阅读，更多相关《1111算法的概念及程序框图（54页珍藏版）》请在金锄头文库上搜索。
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。因为余数不为。
2、因为余数不为0，所以，所以6不能整除不能整除7。因此，。因此，7是质数。是质数。例例2：设计一个算法，判断：设计一个算法，判断53是否为质数。是否为质数。第一步，用第一步，用2除除53，得到余数，得到余数1。因为余数不为。因为余数不为0，所以，所以2不能整除不能整除53。第二步，用第二步，用3除除53，得到余数，得到余数2。因为余数不为。因为余数不为0，所以，所以3不能整除不能整除53。第三步，用第三步，用4除除53，得到余数，得到余数1。因为余数不为。因为余数不为0，所以，所以4不能整除不能整除53。第五十一步，用第五十一步，用52除除53，得到余数，得到余数1。因为余数不为。因为余数不为0
3、，所以所以52不能整除不能整除53。因此，。因此，53是质数。是质数。算法的基本特征算法的基本特征:明明确确性性与与有有效效性性:算算法法对对每每一一个个步步骤骤都都有有确确切切的的,能有效执行且得到确定结果的能有效执行且得到确定结果的,不能模棱两可。不能模棱两可。有限性有限性:算法应由有限步组成算法应由有限步组成, 应在有限多步内结应在有限多步内结束束,并给出计算结果并给出计算结果顺序性顺序性:算法从初始步骤开始算法从初始步骤开始,分为若干明确的步分为若干明确的步骤骤,每一步都只能有一个确定的继任者每一步都只能有一个确定的继任者,只有执行只有执行完前一步才能进入到后一步完前一步才能进入到后一
4、步,并且每一步都确定无并且每一步都确定无误后误后,才能解决问题。才能解决问题。不不唯唯一一性性:求求解解某某一一个个问问题题的的解解法法不不一一定定是是唯唯一一的的,对于同一个问题可以有不同的解法对于同一个问题可以有不同的解法算法的表示算法的表示 描描述述算算法法可可以以有有不不同同的的方方式式, ,常常用用的的有有自自然语言、程序框图、程序设计语言等然语言、程序框图、程序设计语言等. . 自自然然语语言言就就是是人人们们日日常常使使用用的的语语言言, ,可可以以是是汉汉语语、英英语语或或数数学学语语言言等等. .用用自自然然语语言言描描述述算算法法的的优优点点是是通通俗俗易易懂懂, ,当当算
5、算法法中中的的操操作作步步骤骤都都是是顺顺序序执执行行时时比比较较容容易易理理解解. .缺缺点点是是如如果果算算法法中中包包含含判判断断和和转转向向, ,并并且且操操作作步步骤骤较较多多时时, ,就就不不那那么么直直观观清晰了清晰了. .(1)(1)自然语言自然语言(2)(2)程序框图程序框图(3)(3)程序设计语言程序设计语言1.1.21.1.2程序框图程序框图中讲解中讲解1.21.2基本算法语句基本算法语句中讲解中讲解 、一位商人有、一位商人有9枚银元，其中有枚银元，其中有1枚略轻的是假银元。你能用天平（不用枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？砝码）将假银元找出来吗？
6、 按照这样的理解按照这样的理解, ,我们可以设计出很多具我们可以设计出很多具体数学问题的算法体数学问题的算法. .下面看几个例子下面看几个例子: :第第一一步步: :将将9 9枚枚银银元元平平均均分分成成三三组组, ,将将其其中中两两组组放放在在天天平平的的两两边边. . 如如果果天天平平平平衡衡, , 则则假假的的银银元元必必定定在在另另外外一一组组; ;如如果果天天平平不不平平衡衡, ,则则假假的的银银元元必定在较轻的一组必定在较轻的一组; ;第第二二步步: :将将有有假假银银元元的的一一组组金金币币中中, ,取取出出两两枚枚银银元元, ,分分别别放放在在天天平平的的两两边边. .如如果果
7、天天平平平平衡衡, ,则则假假的的银银元元必必定定是是剩剩余余的的; ;如如果果天天平平不不平平衡衡, ,则则假假的的银元必定在较轻的一边银元必定在较轻的一边. . 、一一个个农农夫夫带带着着一一条条狼狼、一一头头山山羊羊和和一一篮篮蔬蔬菜菜要要过过河河,但但只只有有一一条条小小船船.乘乘船船时时,农农夫夫只只能能带带一一样样东东西西.当当农农夫夫在在场场的的时时候候,这这三三样样东东西西相相安安无无事事.一一旦旦农农夫夫不不在在,狼狼会会吃吃羊羊,羊羊会会吃吃菜菜.请请设设计计一一个个算算法法,使使农农夫夫能能安安全全地地将将这这三三样样东东西西带带过河过河.第一步第一步: :农夫带羊过河农
8、夫带羊过河; ;第二步第二步: :农夫独自回来农夫独自回来; ;第三步第三步: :农夫带狼过河农夫带狼过河; ;第四步第四步: :农夫带羊回来农夫带羊回来; ;第五步第五步: :农夫带蔬菜过河农夫带蔬菜过河; ;第六步第六步: :农夫独自回来农夫独自回来; ;第七步第七步: :农夫带羊过河农夫带羊过河. . 、给出求、给出求1+2+3+4+5+6的一个算法的一个算法.解法解法1.1.按照逐一相加的程序进行按照逐一相加的程序进行. .第一步第一步:计算计算1+2,得得3;第二步第二步:将第一步中的运算结果将第一步中的运算结果3与与3相加得相加得6;第三步第三步:将第二步中的运算结果将第二步中的运
9、算结果6与与4相加得相加得10;第四步第四步:将第三步中的运算结果将第三步中的运算结果10与与5相加得相加得15;第五步第五步:将第四步中的运算结果将第四步中的运算结果15与与6相加得相加得21.解法解法2.2.可以运用下面公式直接计算可以运用下面公式直接计算. .第一步第一步: :取取 n = =6; ;第二步第二步: :计算计算 ; ;第三步第三步: :输出计算结果输出计算结果. .点点评评: :解解法法1 1繁繁琐琐, ,步步骤骤较较多多; ; 解解法法2 2简简单单，步步骤较少骤较少. . 找出好的算法是我们的追求目标找出好的算法是我们的追求目标. .例例2.2.写出用写出用“二分法二
10、分法”求方程求方程 x2-2=0（x0） 的近似解的算法的近似解的算法. .第一步，令第一步，令f(x)=x2-2，给定精确度，给定精确度d;第二步，确定区间第二步，确定区间a，b，满足，满足f(a)f(b)0;第三步，取区间中点第三步，取区间中点m= ;第四步，若第四步，若f(a)f(m) 2 2）是否为质数）是否为质数”的的算法步骤如何？算法步骤如何？第一步第一步，给定一个大于，给定一个大于2 2的整数的整数n n； 第二步第二步，令，令i=2i=2； 第三步第三步，用，用i i除除n n，得到余数，得到余数r r； 第四步第四步，判断，判断“r=0r=0”是否成立是否成立. .若是，则若
11、是，则n n 不是质数，结束算法；否则，将不是质数，结束算法；否则，将i i 的值增加的值增加1 1，仍用，仍用i i表示；表示； 第五步第五步，判断，判断“i i(n-1)(n-1)”是否成立，若是，是否成立，若是， 则则n n是质数，结束算法；否则，返回是质数，结束算法；否则，返回 第三步第三步. . Copyright 2004-2009 版权所有 盗版必究思考思考2:2:我们将上述算法用下面的图形表示：我们将上述算法用下面的图形表示：开始开始r=0？输输出出“n是是质质数数”输出输出“n不是质数不是质数”求求n除以除以i的余数的余数i=2输入输入ni的值增加的值增加1，仍用，仍用i表示
12、表示i in-1n-1或或r=0r=0？是是是是结束结束否否否否输入输入n i=2 =2 r=0?是是n不是质数不是质数n是质数是质数否否求求n除以除以i的余数的余数ri=i+1 +1 in-1或或r=0?否否是是(1)(1)(2)(2)(3)(3)问问: :这些分解框图各有什么特点这些分解框图各有什么特点? ?顺序顺序结构结构条件条件结构结构循环循环结构结构算法的三种基本逻辑结构解：求面积的算法解：求面积的算法:第一步第一步:输入三角形三条边的边长输入三角形三条边的边长a,b,c第二步第二步:计算计算第三步第三步:计算计算第四步第四步:输出三角形的面积输出三角形的面积S图示图示:输出S例例3
13、、已知一个三角形的、已知一个三角形的三边边长分别是三边边长分别是a,b,c,利利用海伦用海伦-秦九韶面积公式秦九韶面积公式,求三角形的面积求三角形的面积.顺序结构顺序结构是任何一个算法都不可缺少的基本结是任何一个算法都不可缺少的基本结构，它由若干个构，它由若干个依次执行依次执行的处理步骤组成。的处理步骤组成。开始开始结束结束输入a,b,cCopyright 2004-2009 版权所有 盗版必究 例例1 1 一个笼子里装有鸡和兔共一个笼子里装有鸡和兔共m m只，且只，且鸡和兔共鸡和兔共n n只脚，设计一个计算鸡和兔各有多只脚，设计一个计算鸡和兔各有多少只的算法，并画出程序框图表示少只的算法，并
14、画出程序框图表示. .理论迁移理论迁移算法分析：算法分析： 第一步，输入第一步，输入m m，n.n.第二步，计算鸡的只数第二步，计算鸡的只数 . .第三步，计算兔的只数第三步，计算兔的只数y=m-x.y=m-x.第四步，输出第四步，输出x x，y.y.Copyright 2004-2009 版权所有 盗版必究开始开始结束结束输出输出x，y输入输入m，ny y= m-xm-x程序框图：程序框图： Copyright 2004-2009 版权所有 盗版必究顺序结构的程序框图的基本特征：顺序结构的程序框图的基本特征：小结作业小结作业（2 2）各程序框从上到下用流程线依次）各程序框从上到下用流程线依次
15、连接连接. .（1 1）必须有两个起止框，穿插输入、输）必须有两个起止框，穿插输入、输出框和处理框，没有判断框出框和处理框，没有判断框. .（3 3）处理框按计算机执行顺序沿流程线）处理框按计算机执行顺序沿流程线依次排列依次排列. .条件结构条件结构:在算法流程中需根据条件是否成立有在算法流程中需根据条件是否成立有不同的流向的结构不同的流向的结构.双分支的条件结构非对称的条件结构满足条件？满足条件？步骤步骤A步骤步骤B满足条件？满足条件？步骤步骤ANNYY否否图示图示:开始开始存在这样存在这样的三角形的三角形结束结束解：判断三角形存在的算法解：判断三角形存在的算法:第一步第一步:输入正实数输入
16、正实数a,b,c第二步第二步:判断判断a+bc,b+ca,c+ab是否是否都成立都成立,若是若是,则存在这样则存在这样的三角形的三角形,若不是若不是,则不存则不存在这样的三角形在这样的三角形.a+bc,b+ca,c+ab是否同是否同时成立时成立?输入输入a,b,c是是不存在这样不存在这样的三角形的三角形例例4、任意给定、任意给定3个正实个正实数数,判断以这判断以这3个数为三边个数为三边边长的三角形是否存在边长的三角形是否存在.例例5.5.设计算法设计算法, ,求一元二求一元二次方程次方程axax2 2+bx+c=0,+bx+c=0,画出相画出相应的流程图应的流程图 解决这一问题的算法步骤如下:
17、第一步:输入3个系数a,b,c第二步:计算=b2-4ac第三步:判断0是否成立.若是,则计算p=- ,q= ;否则, 输出“方程没有实数根”,结束算法.第四步:判断=0是否成立.若是,则输出x1=x2=p;否则,计算x1=p+q, x2=p-q,并输出x1,x2b2a2a开始输入a,b,c=b2-4ac0? P=- q=0?b2a2ax1=p+qx2=p-q输出x1,x2结束输出“方程没有实数根”输出p否是是否例例5.5.设计算法设计算法, ,求一元二求一元二次方程次方程axax2 2+bx+c=0,+bx+c=0,画出相画出相应的流程图应的流程图 解决这一问题的算法步骤如下:第一步:输入3个
18、系数a,b,c第二步:计算=b2-4ac第三步:判断0，则原方程无实数解；否则（0）x1 = x2=第四步:输出x1,x2或无实数解信息-b+2a-b-2a开始输入a,b,c=b2-4ac100?是是输出输出S结束结束否否直到直到型循型循环结环结构构开始开始i=1S=0i100?是是S=S+ii=i+1否否输出输出S结束结束当型循环当型循环结构结构直到型循环直到型循环在执行了在执行了一次循环体之后一次循环体之后,对对控制循环条件进行判控制循环条件进行判断断,当条件不满足时当条件不满足时执行循环体执行循环体,满足则满足则停止停止.(反复执行循环反复执行循环体体,直到条件满足直到条件满足)开始开始
19、i=1S=0S=S+ii=i+1i100?是是输出输出S结束结束否否直到直到型循型循环结环结构构说明说明:(1)一般地一般地,循环结构中都循环结构中都有一个有一个计数变量计数变量和和累加变量累加变量.计计数变量用于记录循环次数数变量用于记录循环次数,同时同时它的取值还用于判断循环是否终它的取值还用于判断循环是否终止止,累加变量用于输出结果累加变量用于输出结果.累加累加变量和计数变量一般是同步执行变量和计数变量一般是同步执行的的,累加一次累加一次,记数一次记数一次.当型循环当型循环在每次执在每次执行循环体前对循环行循环体前对循环条件进行判断条件进行判断,当当条件满足时执行循条件满足时执行循环体环
20、体,不满足则停不满足则停止止;(当条件满足时当条件满足时反复执行循环体反复执行循环体)开始开始i=1S=0i100?是是S=S+ii=i+1否否输出输出S结束结束当型循环当型循环结构结构例例2. 画出计算画出计算 值的一个算法值的一个算法程序框图程序框图.开始开始输出输出s结束结束i10s=s+1/ii=i+1i=1s=0是是否否例例3. 设计一个求满足设计一个求满足“1+3+5+i2008” 的的i的最小值的算的最小值的算法，并画出程序框图法，并画出程序框图解解:在这个问题中，需要累加多少次，事先在这个问题中，需要累加多少次，事先并不知道，为此我们采用并不知道，为此我们采用直到型直到型的循环
21、的循环. 例例4. 画出对画出对x=1，2，3，10，求求x2的算法的程序的算法的程序框图框图.开始开始结束结束x10y=x2x=x+1x=1是是否否输出输出y例例5、某工厂、某工厂2005年生产总值年生产总值200万元，技术革新后万元，技术革新后预计以后每年的年生产总值比上一年增长预计以后每年的年生产总值比上一年增长5%，设计，设计一个程序框图，输出预计年生产总值超过一个程序框图，输出预计年生产总值超过300万元万元的最早年份的最早年份。（1）确定循环体）确定循环体 t=0.05a设设a为某年的年生产总值，为某年的年生产总值，t为年生产总值的年为年生产总值的年增长量，增长量，n为年份，则为年
22、份，则循环体循环体为：为：a=a+tn=n+1(2)初始变化量：初始变化量：2005年生产总值看成计年生产总值看成计算起点，则算起点，则n=2005，a=200（3）设定循环控制条件：）设定循环控制条件：当年生产总值超过当年生产总值超过300万元时终止循环，可万元时终止循环，可以通过判断以通过判断“a300”是否成立来控制循环是否成立来控制循环n = 2005开始开始a300?a= 200YN结束结束输出输出nt= 0.05aa= a+tn= n+1例例6.设计计算设计计算13+33+53+993的算法程序，的算法程序，并画出相应的流程图。并画出相应的流程图。 p=0i=1p= p+i3i=i
23、+2i 99YN输出输出p算法如下算法如下: p=0; i =1;S1S2S3 p=p +i 3;S4 i =i+2;S5若若i 99,则输出则输出p,否则转否则转S3.程序框图的画法下面，我们根据例的算法步骤，利用三种基本逻辑结构画出程序框图，表示用“二分法”求方程x2-2=0(x0)的近似解的算法(1)算法步骤中的“第一步”“第二步”和“第三步”可以用下面顺序结构来表示f(x)=x2-2输入精确度d和初始值a,bm= a+b2(2)算法步骤中的“第四步”可以用条件结构来表示在这个条件结构中，“否”分支用“a=m”表示含零点的区间为m,b，并把这个区间仍记成a,b；“是”分支用“b=m”表示
24、含零点的区间为a,m，同样把这个区间仍记成a,bb= m f(a)f(m)0a= m NY(3)算法步骤中的“第五步”包含一个条件结构，这个条件结构与“第三步”“第四步”构成一个循环结构，循环体由“第三步”和“第四步”组成，终止循环的条件是“a-bd或f(m)=0”在“第五步”中，还包含循环结构与“输出m”组成的顺序结构第四步 |a-b|d或f(m)=0第三步 NY输出m(4)将各步骤的程序框图连接起来，并画出“开始”与“结束”两个终端框，就得到了表示整个算法的程序框图f(x)=x2-2输入精确度d和初始值a,bm= a+b2b= m f(a)f(m)n-1或或r=0?否否是是r=0?是是n不是质数不是质数n是质数是质数否否结束结束
