《同步讲义算法与程序框图》由会员分享,可在线阅读,更多相关《同步讲义算法与程序框图(13页珍藏版)》请在金锄头文库上搜索。
1、算法与程序框图一、程序框图与算法基本逻辑结构:1.程序框图符号及作用:程序框图又称流程图,是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形.图形符号名称功能终端框(起止框)表示一个算法的起始和结束,是任何算法程序框图不可缺少的输入、输出框表示一个算法输入和输出的信息,可用在算法中任何需要输入、输出的位置处理框(执行框)赋值、计算.算法中处理数据需要的算式、公式等,它们分别写在不同的用以处理数据的处理框内判断框判断某一条件是否成立,成立时出口处标明“是”或“Y”;不成立时标明“否”或“N”流程线连接程序框,表示算法进行的前进方向以及先后顺序连接点如果一个流程图需要分开来画,要在断
2、开处画上连接点,并标出连接的号码例:解一元二次方程:2.画程序框图的规则:为了使大家彼此之间能够读懂各自画出的框图,必须遵守一些共同的规则,下面对一些常用的规则做一简要介绍.(1)实用标准的框图符号.(2)框图一般按从上到下、从左到右的方向画.(3)一个完整的程序框图必须有终端框,用于表示程序的开始和结束.(4)除判断框外,大多数框图符号只有一个进入点和一个退出点,判断框是具有超过一个退出点的唯一符号,另外,一种判断框是“是”与“不是”两分支的判断,而且有且仅有两个结果;还有一种是多分支判断,有几个不同的结果.(5)在图形符号内用于描述的语言要非常简练清楚.3.算法的三种基本逻辑结构:步骤n步
3、骤n+1(1)顺序结构顺序结构是最简单的算法结构,语句与语句之间,框与框之间是按从上到下的顺序进行的,它是由若干个依次执行的处理步骤组成的,它是任何一个算法离不开的基本结构.如图,只有在执行完步骤n后,才能接着执行步骤n+1.例:.已知梯形的上底、下底和高分别为5、8、9,写出求梯形的面积的算法,画出流程图.解:算法如下:S1a5;S2b8;S3h9;S4S(a+b)h/2;S5输出S.流程图如下:(2)条件结构一些简单的算法可以用顺序结构来实现,顺序结构中所表达的逻辑关系是自然串行,线性排列的.但这种结构无法描述逻辑判断,并根据判断结果进行不同的处理的操作,(例如遇到十字路口看信号灯过马路的
4、问题)因此,需要另一种逻辑结构来处理这类问题.条件结构的结构形式如图,在此结构中含有一个判断框,算法执行到此判断框给定的条件P时,根据条件P是否成立,选择不同的执行框(步骤A,步骤B),无论条件P是否成立,只能执行步骤A或步骤B之一,不可以两者都执行或都不执行.步骤A和步骤B中可以有一个是空的.例:某铁路客运部门规定甲、乙两地之间旅客托运行李的费用为 其中(单位:)为行李的重量 试给出计算费用(单位:元)的一个算法,并画出流程图 输入行李的重量; 如果,那么,否则; 输出行李的重量和运费(3)循环结构在一些算法中要求重复执行同一操作的结构称为循环结构.即从算法某处开始,按照一定条件重复执行某一
5、处理过程.重复执行的处理步骤称为循环体.例:北京成功举办了2008年第29届奥运会.你知道在申奥的最后阶段,国际奥委会是如何通过投票决定主办权归属的吗?对筛选出的5个申办城市进行表决的操作程序是:首先进行第一轮投票,如果有一个城市得票超过总票数的一半,那么该城市就获得举办权;如果所有申办城市得票数都不超过总票数的一半,则将得票数最少的城市淘汰,然后重复上述过程,直到选出一个申办城市为止.怎样用算法结构表述上面的操作过程? 解:算法为: 投票; 统计票数,如果有一个城市得票超过总票数的一半,那么该城市就获得举办权,转,否则淘汰得票数最少的城市,转; 宣布主办城市这里,“投票”就是一个循环体循环结
6、构有两种形式:直到型循环结构(until型)和当型循环结构(while型)(1)直到型循环结构如图,直到型循环在执行一次循环体A之后,对控制循环的条件P进行判断,如果条件P不成立则返回继续执行循环体A,执行后,再判断条件P是否成立,依次重复操作,直到某一次给定的判断条件P成立为止.此时,不再返回来执行循环体A,离开循环结构,继续执行下面的结构.直到型循环,因其先执行一次循环体,再对控制循环的条件进行判断,然后根据判断的结果决定是否继续执行循环体.当条件不成立时继续执行循环体,当条件成立时,跳出循环结构,所以,我们也把直到型循环称为“后测试型”循环.(2)当型循环结构如图,每次执行循环体A前,先
7、对控制循环的条件P进行判断,当条件P成立时执行循环体A,循环体A执行完毕后,返回来再判断条件P是否成立,如果条件P仍然成立,那么再执行循环体A,如此反复执行循环体A,直到某一次返回来判断条件P不成立时为止,此时不再执行循环体A,离开循环结构,继续执行下面的结构.也正因为当型循环结构先对条件P进行判断,当条件P成立时,执行循环体;当条件不成立时,跳出循环结构,我们常常把当型循环结构还称为“前测试型”循环.区别:“当型循环”结构中的循环条件时维持循环的;“直到型循环”结构中的循环条件时终止循环的.联系:两个循环形式不同但功能和作用相同,一般情况下可以相互转化.例:写出计算的算法及程序框图(分别用直
8、到型循环和当型循环)(全解P15)解:第一步:设i的值为1; 第二步:设sum的值为0; 第三步:如果i100执行第四步,否则转去执行第七步; 第四步:计算sumi并将结果代替sum; 第五步:计算i1并将结果代替i; 第六步:转去执行第三步; 第七步:输出sum的值并结束算法.循环结构的应用:(1) 确定循环变量和初始条件;(2) 确定算法中反复执行的部分,即循环体;(3) 确定循环的条件;(4) 注意不要出现“死循环”.二、基本算法语句1、输入语句2、输出语句3、赋值语句4、条件语句IF-THEN-ELSE格式IF-THEN格式5、循环语句(1)WHILE语句(2)UNTIL语句三、算法案
9、例1任何一种程序设计语言都包含五种基本的算法语句,它们是输入语句 , 输出语句, 赋值语句,条件语句,循环语句2.输入语句的一般格式是;输出语句的一般格式是; 赋值语句的一般格式是; 条件语句的一般格式是 或 ; 循环语句的一般格式是 和 .输入语句、 输出语句、 赋值语句基本对应于程序框图中的顺序结构;条件语句、循环语句分别用来表达程序框图中的条件结构和循环结构.3.常用符号运算符号:加_+_,减-_,乘*_,除/_,乘方ab,整数取商,求余数MOD.逻辑符号:且AND,或OR,大于,等于=,小于=,小于等于=,不等于.常用函数:绝对值ABS,平方根SQR,取整INT.4.算法案例(1)辗转
10、相除法和更相减损术辗转相除法和更相减损术都是求两个正整数的最大公约数的方法.(1)辗转相除法就是对于给定的两个正整数,用大数除以小数,若余数不为0,则将小数和余数构成新的一对数,继续上面的除法,反复执行此步骤,直到大数被小数除尽,则这时较小的数就是原来两个数的最大公约数.(2)更相减损术就是对于给定的两个正整数,若它们都是偶数,则将它们反复除以2(假设进行了k次),直到它们至少有一个不是偶数后,将大数减小数,然后将差和较小的数构成一对新数,继续上面的减法,反复执行此步骤,直到差和较小的数相等,此时相等的数再乘以原来约简的即为所求两数的最大公约数.(2)秦九韶算法秦九韶算法是求多项式值的优秀算法
11、.设,改写为如下形式:设这样求n次多项式的值就转化为求n个一次多项式的值.当多项式中有些项不存在时,可将这几项看做,补齐后再利用秦九韶算法进行计算.对于一个n次多项式,只需做n次乘法和n次加法运算即可.(3)进位制K进制数的基数为k,k进制数是由之间的数字构成的.将十进制的数转化为k进制数的方法是除k取余法.典例精析例1写出用循环语句描述求的值的算法程序.解:算法程序如下:(1)当型循环 (2)直到型循环 评注: 在编写算法的程序时,可先画出程序框图,抓住程序框图表示算法这个核心.注意分别用当型循环和直到型循环语句编写的程序中,循环条件的区别与联系. 例2、某市对排污水进行综合治理,征收污水处
12、理费,系统对各厂一个月内排出的污水量吨收取的污水处理费元,运行程序如下所示:请写出y与m的函数关系,并求排放污水150吨的污水处理费用.解: 这个程序反映的是一个分段函数因为所以,故该厂应缴纳污水处理费1400元.评注: 解决分段函数要用条件语句来处理.本题可画出程序框图帮助理解.例3求三个数72,120,168的最大公约数.解法1:用辗转相除法先求120,168的最大公约数,因为所以120,168的最大公约数是24.再求72,24的最大公约数,因为,所以72,24的最大公约数为24,即72,120,168的最大公约数为24.解法2:用更相减损术先求120,168的最大公约数,168-120=
13、48,120-48=72,72-48=24,48-24=24所以120,168的最大公约数为24.再求72,24的最大公约数,72-24=48,48-24=2472,24的最大公约数为24,即72,120,168的最大公约数为24.评注: 辗转相除法与更相减损术均是求两个正整数的最大公约数的方法,要理解和掌握它们的操作步骤.变式:试写出求正整数的最小公倍数的算法程序.解: 例4.用秦九韶算法求多项式在时的值.分析:先改写多项式,再由内向外计算.评注: 用秦九韶算法求多项式值,关健是正确将多项式改写,然后由内向外计算求得.本题也可简写为下式:例5.完成下列进制的转化解: (2)用8反复去除101,直到商为0止,所得的余数(从末位读起)就是十进制数101的8进制表示所以评注:将进制的数转化为进制的数的方法是先将进制的数转化为十进制的数,再将这个数转化为进制的数.变式训练:下面是把二进制数化为十进制数的一个程序框图,判断框内应填入的条件是( )