算法与程序框图改j.ppt

1.1算法与程序框图,1.1.1 算法的概念,学习目标：1理解算法是描述处理有有限多个步骤的问题的方法的一种“语言”；2会用自然语言描述解方程组等数学问题的算法。学习重点：能从整体上把握具体问题的解题步骤。学习难点：会用明确的语言描述算法的每一个步骤。,对于一般的二元一次方程组也可以按照上述步骤求解.,第一步:2+得:5x=1 第二步:解得:x=1/5第三步:将x=1/5代入得:y=3/5第四步:得到方程组的解为:,这些步骤就构成了解二元一次方程组的算法，我们可以根据这一算法编制计算机程序，“教会”计算机解二元一次方程组。,算法的概念与特征,算法(algorithm)这个词出现于12世纪，指的是用阿拉伯数字进行算术运算的过程。,在数学上,“算法”通常是指按照一定规则解决某一类问题的明确和有限的步骤。算法具有程序性、有限性、构造性、精确性的特点。现在，算法通常可以编成计算机程序，让计算机执行并解决问题。,算法学的发展,随着科学技术的日新月异,算法学也得到了前所未有的发展,现在已经发展到了各个领域.有遗传算法,排序算法,加密算法,蚁群算法等,与生物学,计算机科学等有着很广泛的联系,尤其是在现在的航空航天中,更是有着更广泛的应用.很多复杂的运算都是借助计算机和算法来完成的,在高端科学技术中有着很重要的地位.,科学家王小云主导破解两大密码算法获百万大奖杨振宁教授为获得“求是杰出科学家奖”的山东大学特聘教授王小云颁发了获奖证书和奖金100万元人民币，表彰其密码学领域的杰出成就。,例1:任意给定一个大于2的整数n，试设计一个程序或步骤对n是否为质数做出判定。,算法分析:,第一步:给定大于2的整数n,第二步：令i=2,第三步:用i除n，得到余数r,第四步:判断r=0是否成立，若是，则n不是质数，结束算法；若否，i=i+1;,第五步:判断in-1是否成立，若是，则n是质数，结束算法；若否，则返回第三步。,若是,则m为所求;,例2:用二分法设计一个求方程x2-2=0（x0)的近似根的算法.,算法分析:,设所求近似根与精确解的差的绝对值不超过=0.005.,第一步:令f(x)=x2-2.,因为f(1)0,所以设a=1,b=2.,第二步:令,判断f(m)是否为0.,第四步:判断|a-b|是否成立?若是,则a或b为满足条件的近似根;若否,则返回第二步.,点评:(1)上述算法也是求 的近似值的算法.,(2)与一般的解决问题的过程比较，算法有以下特征:设计一个具体问题的算法时，与过去熟悉的解数学题的过程有直接的联系，但这个过程必须被分解成若干个明确的步骤。算法要“面面俱到”，不能省略任何一个细小的步骤，不能忽略任何一种特别的情况，否则在计算机执行算法的过程中就可能出现各种错误，甚至造成不可挽回的损失。,计算机解决任何问题都要依赖于算法。只有将解决问题的过程分解为若干个明确的步骤，即算法，并用计算机能够接受的“语言”准确地描述出来，计算机才能够解决问题。,练习一：任意给定一个正实数r，设计一个求以r为半径的圆的面积的算法。,算法分析:,第一步:（用键盘向计算机）输入一个具体的正实数r;第二步:计算S=r2;第三步:（计算机在屏幕上显示）输出圆的面积S.,练习二:任意给定一个大于1的正整数n，设计一个能求出n的所有因数的算法。,算法分析:,第一步：输入正整数n。第二步:依次以2(n-1)为除数去除n，判断余数是否为0。若是，则该除数是n的因数；若不是，则该除数不是n的因数。第三步:在n的因数中加入1和n。第四步:输出n的所有因数。,练习三:为了加强居民的节水意识，某市制订了以下生活用水收费标准：每户每月用水未超过7m3时，每立方米收费1.0元，并加收0.2元的城市污水处理费；超过7m3的部分，每立方米收费1.5元，并加收0.4元的城市污水处理费，请你写出某户居民每月应交纳的水费y(元)与用水量x(m3)之间的函数关系，然后设计一个求该函数值的算法。,解:y与x之间的函数关系为:,(当0 x7时)(当x7时),解:y与x之间的函数关系为:,(当0 x7时)(当x7时),求该函数值的算法分析:,第一步:输入每月用水量x；第二步:判断x是否大于7。若是，则y=1.9x4.9；若否，则y=1.2x。第三步:输出应交纳的水费y。,作业:课本P51页复习参考题B组T3：设计一个算法，判断一个正的n(n2)位数是不是回文数？(只需用自然语言写出算法步骤)注：回文数是指从左到右读与从右到左读都是一样的正整数，如121，94249等。,1.1.2 程序框图（1）,学习目标：1了解程序框图的顺序结构、条件结构的画法及功能；2能在“人肉计算机”中运行程序框图描述的算法。学习重点：启动“人肉计算机”，运行大量简单程序。学习难点：如何用多重条件结构处理复杂的分类讨论问题。,从上节课我们知道:算法可以用自然语言来描述.如例1：,为了使算法的程序或步骤表达得更为直观,我们更经常地用图形方式来表示它.,任意给定一个大于1的整数n，试设计一个程序或步骤对n是否为质数做出判定。,算法分析:,第一步:判断n是否等于2.,若n=2,则n是质数;,若n2,则执行第二步.,第二步:依次检验从2到(n-1)这些数能否整除n。若有这样的数，则n不是质数；若没有这样的数，则n是质数。,设n是一个大于2的整数.,一般用i=i+1表示.,i=i+1,说明:i表示从2(n-1)的所有正整数,用以判断例1步骤2是否终止,i是一个计数变量,有了这个变量,算法才能依次执行.逐步考察从2(n-1)的所有正整数中是否有n的因数存在.,思考：比较自然语言和程序框图这两种不同的表达方式，你觉得用程序框图来表达算法有哪些优点?,答：更加简洁，直观，执行的流程更清晰。,程序框图又称流程图，是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形。,基本的程序框和它们各自表示的功能如下:,终端框(起止框),表示算法的起始和结束,输入、输出框,表示算法输入和输出的信息,处理框(执行框),根据某条件是否成立改变程序执行的流向,判断框,赋值、计算等,流程线,连接程序框,连接点,连接程序框图的两部分,程序框图的三种基本的逻辑结构,顺序结构,条件结构,循环结构,顺序结构,用程序框图来表示算法，有三种不同的基本逻辑结构：,条件结构,循环结构,(1)顺序结构-是由若干个依次执行的处理步骤组成的。这是任何一个算法都离不开的基本结构。,例1:已知一个三角形的三边边长分别为2，3，4，利用海伦-秦九韶公式设计一个算法，求出它的面积，画出算法的程序框图。,已知三角形三边长分别为a,b,c,则三角形的面积为 其中 这个公式被称为海伦秦九韶公式.,算法分析:,第二步:计算p的值。,第三步:计算S=,第四步:输出S的值。,程序框图:,开始,输出S,结束,(2)条件结构-在一个算法中，经常会遇到一些条件的判断，算法的流向根据条件是否成立有不同的流向。条件结构就是处理这种过程的结构。,例2:任意给定3个正实数，设计一个算法，判断分别以这3个数为三边边长的三角形是否存在。画出这个算法的程序框图。,算法分析:,第一步:输入3个正实数a，b，c；,第二步:判断a+bc，a+cb，b+ca是否同时成立。若是，则能组成三角形；若否，则组不成三角形。,程序框图:,开始,输入a,b,c,a+bc,a+cb,b+ca是否同时成立?,是,存在这样的三角形,不存在这样的三角形,否,结束,例3:（上节课已经做过此题）为了加强居民的节水意识，某市制订了以下生活用水收费标准：每户每月用水未超过7m3时，每立方米收费1.0元，并加收0.2元的城市污水处理费；超过7m3的部分，每立方米收费1.5元，并加收0.4元的城市污水处理费，请你写出某户居民每月应交纳的水费y(元)与用水量x(m3)之间的函数关系，然后设计一个求该函数值的算法,并画出程序框图。,解:y与x之间的函数关系为:,(当0 x7时)(当x7时),解:y与x之间的函数关系为:,(当0 x7时)(当x7时),算法分析:,第一步:输入每月用水量x;第二步:判断x是否大于7。若是，则y=1.9x4.9；若否，则y=1.2x。第三步:输出应交纳的水费y.,开始,输入x,x7?,是,y=1.9x4.9,否,y=1.2x,输出y,结束,程序框图,是,练习1.设计一个求任意数的绝对值的算法，并画出程序框图。,算法分析:,第一步:输入数x;第二步:判断x0是否成立?若是,则|x|=x;若否,则|x|=-x.,程序框图:,开始,输入x,x0?,输出x,否,输出-x,结束,返回,例4.(课本P50复习参考题A组T1(1)画程序框图,对于输入的x值,输出相应的y值.,开始,程序框图,x0?,是,y=0,否,x1?,是,y=1,否,y=x,输出y,结束,输入x,作业:课本P20页习题11 A组T3;课本P50页复习参考题A组T1(2),1.1.2 程序框图（2）,学习目标：1了解程序框图的循环结构的画法及功能；2“人肉计算机”运行更快速顺畅；3能写出程序框图中缺少的关键语句（多为循环结构中的条件语句）。学习重点：启动“人肉计算机”，运行大量程序（含循环结构）。学习难点：1当型和直到型循环结构的结束循环的条件。2写出程序框图中缺少的关键语句（多为循环结构中的条件语句）。,(3)循环结构-在一些算法中，也经常会出现从某处开始，按照一定条件，反复执行某一步骤的情况，这就是循环结构。,反复执行的步骤称为循环体.,注意:循环结构不能是永无终止的“死循环”，一定要在某个条件下终止循环，这就需要条件结构来作出判断，因此，循环结构中一定包含条件结构。,例5:设计一个计算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来表示每一步的计算结果,从而把第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,结束,当型循环结构,说明:(1)一般地，循环结构中都有计数变量和累加变量。计数变量用于记录循环次数，同时它的取值还用于判断循环是否终止，累加变量用于输出结果。累加和计数操作一般是在循环体中都作一次，即累加一次，并且记数一次。,(2)循环结构分为两种-当型和直到型.,当型循环在每次执行循环体前对循环条件进行判断，当条件满足时执行循环体，不满足则停止；(当条件满足时反复执行循环体),直到型循环在执行了一次循环体之后，对控制循环的条件进行判断，当条件不满足时执行循环体，满足则停止。(反复执行循环体，直到条件满足),程序框图:,开始,i=1,S=0,S=S+i,i=i+1,i100?,是,输出S,结束,否,直到型循环结构,开始,i=1,S=0,i100?,是,S=S+i,i=i+1,否,输出S,结束,当型循环结构,以下判断n是否为质数的程序框图中用虚线框住的循环结构是当型循环，还是直到型循环？,循环结构,直到型循环结构,若是,则m为所求;,（备用，参考上上节课例题2）例6:画出用二分法求方程x2-2=0的近似根(精确度为0.005)的程序框图。,算法分析:,第一步:令f(x)=x2-2.,因为f(1)0,所以设a=1,b=2.,第二步:令,判断f(m)是否为0.,第四步:判断|a-b|是否成立?若是,则a或b为满足条件的近似根;若否,则返回第二步.,否,是,是,否,程序框图,开始,f(x)=x2-2,输入误差和初值a,b,f(m)=0?,a=m,否,b=m,|a-b|?,1,2,2,输出a和b,结束,输出m,3,1,3,是,是,是,否,程序框图,开始,f(x)=x2-2,输入误差和初值a,b,a=m,否,b=m,|a-b|或f(m)=0?,输出m,结束,课堂小结,本节主要讲述了程序框图的基本知识:包括常用的图形符号、算法的基本逻辑结构。算法的基本逻辑结构有三种，即顺序结构、条件结构和循环结构。其中顺序结构是最简单的结构，也是最基本的结构，循环结构必然包含条件结构，所以这三种基本逻辑结构是相互支撑的，它们共同构成了算法的基本结构，无论怎样复杂的逻辑结构，都可以通过这三种结构来表达。,作业:课本P20页习题1.1A组T2;P50页复习参考题A组T4.,习题练习参考答案,开始,i=1,S=0,S=S+i2,i=i+1,i100?,是,输出S,结束,否,直到型循环结构,开始,i=1,S=0,i100?,是,S=S+i2,i=i+1,否,输出S,结束,当型循环结构,P20页A组T2.,是,(P20页A组T3),程序框图:,开始,输入x,x3?,否,结束,输入y,y=5,y=1.2x+1.4,算法分析:,第一步:判断a1是否等于0.,如果a10,由+u,得(b2+b1u)y=c2+c1u;,如果a1=0,执行第三步.,第二步:解,得,输出y.,第三步:将y值代入,得,输出x.,P20B组T1,开始,程序框图,输入a1,b1,c1,a2,b2,c2,a10?,是,u=-a2/a1,b=b2+b1u,c=c2+c1u,y=c/b,x=(c2-b2y)/a2,否,y=c1/b1,.某高中男子体育小组的50m跑成绩(单位:s)为:6.4,6.5,7.0,6.8,7.1,7.3,6.9,7.4,7.5.设计一个算法,从这些成绩中搜出小于6.8s的成绩.,算法分析:,第一步:把计数变量n的初值设为1.第二步:输入一个成绩r,判断r与6.8的大小.若r6.8,则执行下一步;若r9,则结束.,P20BT2,开始,n=1,程序框图,输入r,r6.8?,是,n=n+1,n9?,是,否,输出r,否,结束,直到型循环结构,(P50页A组T1(1),开始,程序框图,x0?,是,y=0,否,0 x1?,是,y=1,否,y=x,输出y,结束,输入x,(P50页A组T1(2),开始,程序框图,x0?,是,y=(x+2)2,否,x=0?,是,y=4,否,输出y,结束,输入x,y=(x-2)2,否,(P50页A组T3),程序框图:,开始,输入t,t3?,是,结束,输入y,y=0.2,y=0.1t,注：t表示不大于t的最大整数。例如：3=3，3.5=3，4.2=4。,开始,i=1,S=0,S=S+,i=i+1,in?,是,输出S,结束,否,直到型循环结构,开始,i=1,S=0,in?,是,S=S+,i=i+1,否,输出S,结束,当型循环结构,P50页A组T4.,输入n,输入n,(P51页B组T3)设计一个算法,判断一个正的n(n2)位数是不是回文数,用自然语言描述算法步骤.,算法步骤:第一步:输入一个正整数x和它的位数.第二步:判断n是不是偶数,如果是偶数,令m=n/2;如果是奇数,令m=(n-1)/2.第三步:当i从1取到m值时,依次判断x的第i位与第(n+1-i)位上的数字是不是相等,如果都相等,则x是回文数;否则,x不是回文数.,回文数是指从左到右读与从右到左读都是一样的正整数,如121，676，94249，234432等。,开始,程序框图,输入正整数x和它的位数n,n是偶数？,是,m=n/2,否,m=(n-1)/2,第i位与第(n+1-i)(i=1,2,m)位上的数字相等?,是,x是回文数,否,x不是回文数,结束,