算法与程序框图上.ppt
算法与程序框图,问题的提出,有一个农夫带一条狼狗、一只羊和一筐白菜过河。如果没有农夫看管，则狼狗要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？,方法和过程：,1、带羊到对岸，返回；,2、带菜到对岸，并把羊带回；,3、带狼狗到对岸，返回；,4、带羊到对岸。,算法的基本思想,随着计算科学和信息技术的飞速发展，算法的思想已经渗透到社会的方方面。在以前的学习中，虽然没有出现算法这个名词，但实际上在数学教学中已经渗透了大量的算法思想，如四则运算的过程、求解方程的步骤等等。完成这些工作都需要一系列程序化的步骤，这就是算法的思想。,算法是什么?,算法可以理解为由基本运算及规定的运算顺序构成的完整的解题步骤，或看成按要求设计好的有限的、确切的计算序列，并且这样的步骤或序列能解决一类问题。,新课讲解,算法的概念:,算法是指解决给定问题的有穷操作步骤的描述，简单的说，算法就是解决问题的步骤和方法。,新课讲解,例1 设计一算法：输入圆的半径,输出圆的面积,算法分析：,第一步：输入圆的半径,第二步：利用公式“圆的面积=圆周率（半径的平方）”计算圆的面积；,第三步：输出圆的面积。,新课讲解,例2 设计房租收费的算法,其要求是:住房面积80平方米以内,每平方米收费3元,住房面积超过80平方米时,超过部分,每平方米收费5元.输入住房面积数,输出应付的房租.,算法分析：,第一步：输入住房面积S,第二步：根据面积选择计费方式：如果S小于或等于80，则租金为M=S3，否则为M=240+(S-80)5,第三步：输出房租M的值。,新课讲解,例3 设计一算法，求和:1+2+3+100,算法分析：,算法1：,第一步：确定首数a，尾数b，项数n；,第二步：利用公式“总和=(首数+尾数）项数/2”求和；,第三步：输出求和结果。,利用等差数列求和公式,新课讲解,例3 设计一算法，求和:1+2+3+100,算法分析：,算法2：,第一步：从1开始将自然数1、2、3、100逐个相加;,第二步：输出累加结果。,探究,如果要计算1到50的平方和,算法一是否仍适用?算法二应如何修改?,新课讲解,算法的基本特点,1、有穷性,一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束。,2、确定性,算法的计算规则及相应的计算步骤必须是唯一确定的，既不能含糊其词，也不能有二义性。,3、可行性,算法中的每一个步骤都是可以在有限的时间内完成的基本操作，并能得到确定的结果。,程序框图,（1）程序框图的概念,程序框图又称流程图，是一种用程序框、流程线及文字说明来准确、直观地表示算法的图形.,在程序框图中，一个或几个程序框的组合表示算法中的一个步骤；带有方向箭头的流程线将程序框连接起来，表示算法步骤的执行顺序。,新课讲解,终端框(起止框),输入、输出框,处理框(执行框),判断框,表示一个算法的起始和结束,表示一个算法输入和输出的信息,赋值、计算,判断某一条件是否成立,成立时在出口处标明“是”或“Y”,不成立时标明“否”或“N”.,（2）构成程序框图的图形符号及其功能,流程线,连接程序框,连结点,连接程序框图的两部分,6,例：判断“整数n(n2)是否是质数”的算法,算法步骤：,程序框图：,开始,输入n,求n除以i的余数,i的值增加1,仍用i表示,in-1或r=0?,r=0?,n不是质数,n是质数,结束,否,否,是,是,i=2,顺序结构,循环结构,条件结构,算法的三种基本逻辑结构 顺序结构、条件结构、循环结构。,例3 已知一个三角形的三边长分别为a,b,c，利用海伦-秦九韶公式设计一个计算三角形面积的算法，并画出程序框图表示.,算法步骤：,第一步，输入三角形三边长 a，b，c,第二步，计算,第三步，计算,第四步，输出s.,程序框图：,结束,开始,输入a,b,c,输出s,算法步骤为:第一步，输入圆的半径 r.第二步，计算第三步，输出s.,程序框图：,结束,开始,输入r,输出s,练习1：任意给定一个正实数，设计一个算法求以这个数为半径的圆的面积，并画出程序框图表示.,条件结构是指在算法中通过对某条件的判断,根据条件是否成立而选择不同流向的算法结构.,基本形式2,(2)条件结构,满足条件?,步骤A,否,是,满足条件?,步骤A,步骤B,是,否,基本形式1,例4 任意给定3个正实数,设计一个算法,判断分别以这三个数为三边边长的三角形是否存在.画出这个算法的程序框图.,a+bc,a+cb,b+ca是否同时成立?,开始,存在这样的三角形,结束,不存在这样的三角形,否,输入a,b,c,例5 设计一个求解一元二次方程ax2+bx+c=0的算法，并画出程序框图表示.,算法步骤：,第一步，输入3个系数a，b，c.,第二步，计算=b2-4ac.,第四步，判断=0是否成立.若是，则输出 x1=x2=p，否则，计算x1=p+q，x2=p-q，并输出x1，x2.,第三步，判断0是否成立.若是，则计 算；否则，输出“方程没有 实数根”，结束算法.,开始,程序框图：,输入a，b，c,=b2-4ac,0？,=0？,否,x1=p+q,输出x1，x2,结束,否,是,x2=p-q,输出x1=x2=p,是,输出“方程没有实数根”,设计一算法,求和:1+2+3+100.,第一步:确定首数a,尾数b,项数n；,第二步:利用公式“总和=(首数+尾数)项数/2”求和；,第三步:输出求和结果.,算法1：,新课引入,算法2：,第一步:从1开始将自然数1,2,3,100逐个相加;,第二步:输出累加结果.,1.上边的式子有怎样的规律呢？,2.怎么用程序框图表示呢？,S=S+i,设计一算法,求和:1+2+3+100.,S=0S=S+1S=S+2S=S+3S=S+100,思考：,在一些算法中,经常会出现从某处开始,反复执行某一处理步骤,这就是循环结构.,在一些算法中，经常会出现从某处开始，按照一定的条件，反复执行的某些步骤的情况，称为循环结构。反复执行的步骤称为循环体,（3）循环结构,这种循环结构称为直到型循环结构.,在执行了一次循环体后，对条件进行判断，如果条件不满足，就继续执行循环体，直到条件满足时终止循环.,循环结构可以用程序框图表示为下面两种形式：,还有一些循环结构用程序框图可以表示为：,这种循环结构称为当型循环结构.,在每次执行循环体前，对条件进行判断，如果条件满足，就执行循环体，否则终止循环.,当型循环与直到循环的区别：,当型循环可以不执行循环体，直到循环至少执行一次循环体.当型循环先判断后执行，直到型循环先执行后判断.对同一算法来说，当型循环和直到循环的条件互为反条件.,探究：循环结构与条件结构有什么关系?,(1)循环结构是通过条件结构实现的，所以循环结构里一定包含条件结构,（2）循环结构通过条件判断可反复执行；条件结构通过判断执行分支，只执行一次,例1：设计一个计算1+2+3+100的值的算法，并画出程序框图.,用直到型循环结构，上述算法的程序框图如何？解法一：算法：第一步：令i=1，S=0.第二步：计算S+i，仍用S表示.第三步：计算i+1，仍用i表示.第四步：判断i100是否成立.若是，则输出S，结束算法；否则，返回第二步.,第一步：令i=1，S=0.第二步：如果i100成立，则执行第三步，否则，输出S，结束算法.第三步：S=S+i.第四步：i=i+1，返回第二步.,解法二：,上述算法的程序框图表示为：当型循环结构,循环结构的设计步骤,(1)确定循环结构的循环变量和初始条件;(2)确定算法中需要反复执行的部分,即循环体；(3)确定循环的终止条件.,循环结构的三要素,循环变量,循环体、循环的终止条件.,1.画出求S=123100问题的程序框图.,课堂练习,开始,i 100?,否,是,输出S,结束,i=1,S=1,i=i+1,S=Si,开始,i100?,否,是,输出S,结束,i=1,S=0,i=i+1,S=S+i2,书本P.20A2,2.设计一个计算12+22+32+1002的一个程序框图.,是,否,S7？,开始,x1,S2,xxS,SS1,输出x,结束,左图输出的x=_,12367,课堂练习,1本节课主要讲述了算法的循环结构。算法的基本逻辑结构有三种，即顺序结构、条件结构和循环结构。其中顺序结构是最简单的结构，也是最基本的结构，循环结构必然包含条件结构，所以这三种基本逻辑结构是相互支撑的，它们共同构成了算法的基本结构，无论怎样复杂的逻辑结构，都可以通过这三种结构来表达。2循环结构要在某个条件下终止循环，这就需要条件结构来判断。因此，循环结构中一定包含条件结构，但不允许“死循环”。,课堂小结,3在循环结构中都有一个计数变量和累加变量。计数变量用于记录循环次数，累加变量用于输出结果。计数变量和累加变量一般是同步执行的，累加一次，计数一次。4画循环结构程序框图前：确定循环变量和初始条件；确定算法中反复执行的部分，即循环体；确定循环的转向位置；确定循环的终止条件.,课堂总结,1、循环结构的概念2、循环结构三要素：循环变量、循环体、循环终止条件3、累加求和、累乘求积,思考：改进1.1-5中的算法，表示输出1，12，123，123100的过程。,输出S,S=S+i,i=i+1,否,是,S=0,i=1,开始,i100?,结束,改：,结束,输出S,S=S+i,i=i+1,否,是,S=0,i=1,开始,输入n,in?,思考：改进1.1-5中的算法，表示输出1，12，123，123（n-1)+n的过程。,例.某工厂2005年的生产总值为200万元,技术革新后预计以后每年的生产总值比上一年增加5%.设计一个程序框图，输出预计年生产总值超过300万元的最早年份.,算法,直到型循环结构,当型循环结构,当型循环结构,直到型循环结构,程序框图的画法,一般地，一个算法的程序框图有以下几个步骤：,第一步：用自然语言表述算法步骤.,第二步：确定每一个算法步骤所包含的逻辑结构，并用相应的程序框图表示，得到该步骤的程序框图.,第三步：将所有步骤的程序框图用流程线连接起来，并加上终端框，得到表示整个算法的程序框图.,1、算法的有穷性是指（）A 算法必须包含输出 B算法中每个步骤都是可执行的C、算法的步骤必须有限 D、以上说法均不对2、在算法的逻辑结构中，要求进行逻辑判断，并根据结果进行不同处理的是哪种结构（）A、顺序结构 B、条件结构和循环结构 C、顺序结构和条件结构 D、没有任何结构,3算法是指可以用计算机来解决的某一类问题的程序或步骤，它不具有（）A有限性 B明确性 C 有效性 D无限性4程序框图是算法思想的重要表现形式，程序框图中不含（）A流程线 B判断框 C循环框 D执行框5程序框图中有三种基本逻辑结构，它不是（）A条件结构 B判断结构 C循环结构 D顺序结构6在程序框图中一般不含有条件判断框的结构是（）A顺序结构 B循环结构 C当型结构 D直到型结构,C,A,D,D,B,A,第9题,7、如图给出的是计算 的值的一个程序框图，其中判断框内应填入的条件是(）A、i10 B、i20 D、i20,A,8.(2007宁夏、海南理科)如果执行下面的程序框图，那么输出的（）,2450250025502652,【解】选C由程序知,开始,K=1,S=0,K=K+1,S=S+2K,K50?,结束,输出S,是,否,A2550，2500B2550，2550C2500，2500D2500，2550,开始,n=n-1,S=0,T=0,n=n-1,S=S+n,n2?,结束,输出S,T,是,否,输入n,T=T+n,【解】A依据框图可得：,10、右边的程序框图，能判断任意输入的数x的奇偶性：其中判断框内的条件是()A、m=0 B、x=0 C、x=1 D、m=1,第10题,A,11.(2008广东文)阅读程序框图若输入m4,n3,则输出a_,i_,此时3整除12，故输出a12,i3.,第一次循环结果：i=1,a=4;第二次循环结果：i=2,a=8;第三次循环结果：i=3,a=12;,12、如图所示的算法程序框图，表示的算法的功能是 _,计算并输出使1357 10 000成立的最小正整数。,13.,14.,15.,16.,17.,18.,19,20.,21、（本题16分）某电信部门规定：拨打市内电话时，如果通话时间不超过3分钟，则收取通话费0.2元，如果通话时间超过3分钟，则超过部分以每分钟0.1元收取通话费（通话不足1分钟时按1分钟计），试设计一个计算通话费用的算法.要求写出算法，画出程序框图，,解：该题涉及分段函数，故设c（单位：元）表示通话费，t（单位：分钟）表示通话时间，则依题意有,
