循环结构专题.ppt

算法的基本逻辑结构,-,循环结构,顺序结构,按照步骤依次执行,复习回顾,复习回顾,条件结构,需要对给定的条件进行判断，条件为真时，执行步骤,A,，否则执行步骤,B,。,步骤,A,步骤,B,满足条件？,是,否,步骤,A,满足条件？,是,否,生活情境,北京取得,2008,奥运会主办权的投票过程：,对选出的五个城市进行投票表决的流程是：首先进行第一轮投票，如果有一个城市得票超过一半，那么这个城市取得主办权；如果没有一个城市得票超过一半，那么将其中得票最少的城市淘汰，然后,重复,上述过程，再进行投票，直到选出一个城市为止。,奥运会主办权投票过程的算法步骤为：,1.,投票；,2.,计票：如果有一个城市得票超过一半，那么这个城市取得主办权，转入步骤,3,；否则淘汰掉得票最少的城市，,返回步骤,1,，继续执行后继步骤；,3.,宣布主办城市。,奥运会主办权投票表决流程图：,选出该城市,有一城市过半数,投票,淘汰得票最少者,结束,开始,是,否,循环结构,循环结构是指在算法中从某处开始，按照一定的条件,反复执行,某一处理步骤的结构。,循环结构的概念,反复执行的步骤称为循环体,.,注意,:,循环结构不能是永无终止的“死循环”,一定要在某个条件下终止循环,这就需要条件结构来作出判断,因此,循环结构中一定包含条件结构,.,某些循环结构用程序框图可以表示为：,循环体,满足条件？,是,否,这种循环结构称为直到型循环结构,在执行了一次循环体后，对条件进行判断，如果条件不满足，就继续执行循环体，直到条件满足时终止循环,.,还有一些循环结构用程序框图可以表示为：,循环体,满足条件？,是,否,这种循环结构称为,当型循环结构,在每次执行循环体前，对条件进行判断，如果条件满足，就执行循环体，否则终止循环,.,说明,:(1,),在循环结构中都有一个计数变量和累加变量,(,或累乘变量,),。计数变量用于记录循环次数，累加（或累乘）变量用于输出结果。计数变量和累加（或累乘）变量一般是同步执行的，累加或累乘一次，计数一次。,(2),循环结构分为两种,-,当型和直到型,.,当型循环,在每次执行循环体前对循环条件进行判断,当条件满足时执行循环体,不满足则停止,;(,当条件满足时反复执行循环体,),直到型循环,在执行了一次循环体之后,对控制循环条件进行判断,当条件不满足时执行循环体,满足则停止,.(,反复执行循环体,直到条件满足,),例,6:,设计一个计算,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,步结果,=,第,i-1,步结果,+1,每一步中不变的是加法运算，变化的只是参与运算,的量。,上述算法可改写成：,S,1,=0+1,S,2,=S,1,+2,S,3,=S,2,+3,S,100,=S,99,+100,S,i,=S,i-1,+i,问题：（,1,）在上述算法过程中，每步中不变的操作,是什么？变化的是什么？有什么规律？,(,一,),确定循环体,S=5,S=3,S=7,S=5,最后需要输出的是,S,100,，而,S,1,至,S,99,无需保留。,因此用变量,S,来存放每次的计算结果。,即：,S=,S+i(S,称为累加变量）,S=,S+i,是如何运算的？,S=S+2,问题,：,（,2,）,i,如何变化？,变量,i,从第,1,步开始每次增加,1,，直至,100,故可视为计数变量。,由此，可以得出循环体是：,S=,S+i,i,=i+1,S=0,i=1,S=1,i=1,S=1,i=2,S=3,i=2,S=3,i=3,S=,S+i,i=i+1,问题：（,3,）,S,的初始值是什么？,i,的初始值是什么？,问题：（,4,）何时结束循环？,由第,1,步可知,S,的初始值可定为,0,，,i,的初始值可定为,1.,（二）初始化变量,（三）设定控制循环的条件,i,从,1,变到,100,，均要累加，变为,101,则不再加，所以，,i100,时即退出循环。,程序框图,:,开始,i=1,S=0,S=,S+i,i=i+1,是,输出,S,结束,否,i100?,初始值还可以是什么，程序框图相应怎么变？,结束,输出,S,S=1,开始,否,是,i=1,S=S+i,i=i+1,i=100?,例如：,开始,i=1,S=0,是,S=,S+i,i=i+1,否,输出,S,结束,i100?,开始,i=1,S=0,S=,S+i,i=i+1,是,输出,S,结束,否,i100?,设计算法表示,（,1,）输出,2+4+6+,+100,的算法。,（,2,）输出,1,2399100,的算法。,变式训练，深化理解,例,7,、某工厂,2005,年的年生产总值为,200,万元，技术革新,预计以后每年的年生产总值都比上一年增长,5%,，设计一,个程序框图，输出预计年生产总值超过,300,万元的最早,年份,。,合作探究，知识应用,算法分析：,第一步，输入,2005,年的年生产总值。,第二步，计算下一年的年生产总值。,第三步，判断所得结果是否大于,300.,若是，则输出,该年的年份；否则，返回第二步。,（,1,）确定循环体：设,a,为某年的年生产总值，,t,为年,生产总值的年增长量，,n,为年份，循环体为：,t=0.05a,a=,a+t,n=n+1,（,2,）初始化变量：若将,2005,年的年生产总值看成计,算的起点，则,n,的初始值为,2005,，,a,的初始值为,200.,（,3,）设定循环控制条件：当“年生产总值超过,300,万,元”时终止循环，所以可以通过判断“,a300”,是否成立来控制循环。,结束,输出,n,a300?,n=n+1,a=,a+t,t=0.05a,a=200,n=2005,开始,是,否,程序框图：,开始,n100,？,n=1,S=0,n,是偶数,?,S=S,-,nn,S=,S,+,nn,n=n+1,输出,S,结束,是,是,否,否,思考,:,该程序框图反映的实际问题是什么？,求,1,2,-2,2,+3,2,-4,2,+,+99,2,-100,2,的值,.,思考,1,：用,“,二分法,”,求方程 的近似解的算法如何设计？,知识探究：程序框图,第一步，令,f(x,)=x,2,-2,，给定精确度,d.,第二步，确定区间,a,，,b,，满足,f(a),f(b,)0.,第三步，取区间中点,m=(a+b)/2,.,第四步，若,f(a),f(m,),0,，则含零点的区间为,a,，,m,；否则，含零点的区间为,m,，,b.,将新得到的含零点的区间仍记为,a,，,b.,第五步，判断,a,，,b,的长度是否小于,d,或,f(m,),是否等于,0.,若是，则,m,是方程的近似解；否则，返回第三步,.,思考,1:,该算法中哪几个步骤可以用顺序结构来表示？这个顺序结构的程序框图如何？,f(x,)=,x,2,-,2,输入精确度,d,和初始值,a,，,b,思考,2:,该算法中第四步是什么逻辑结构？这个步骤用程序框图如何表示？,f(,a,)f(m,)0?,a=m,b=m,是,否,思考,3:,该算法中哪几个步骤构成循环结构？这个循环结构用程序框图如何表示？,第三步,第四步,|a,-,b|d,或,f(m,)=0?,输出,m,是,否,思考,4:,根据上述分析，,你能画出表示,整个算法的,程序框图吗？,开始,结束,f(,a,)f(m,)0?,？,a=m,b=m,是,否,|a,-,b|n,Y,N,输入,n,输出,S,第一步，令,i=1,S=0.,第二步，计算,S=,S+i,.,第三步，计算,i=i+1.,第四步，判断,in,是否成立，若是，则输出,S;,否则返回第二步,.,开始,输入50米跑成绩r,r6.8,n9？,结束,N,Y,Y,N,P.20习题1.1B组第2题,算法步骤：,第一步，令计算变量n1.,第二步，输入一个成绩r，判断r与,6.8的大小，若r6.8，则执行下一步；,若r6.8，则输出r，并执行下一步.,第三步，令nn1.,第四步，判断计数变量n与成绩个数,9的大小，若n9，则返回第二步，若,n9，则结束算法.,n1,nn1,输出r,