高中数学(算法)课件11 北师大版必修3 课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,算法案例,2,广义地说：,为了解决某一问题而,采取的方法和步骤，就称之为算法。,算法的概念,:,一般而言，,对一类问题的机械,的、统一的求解方法称为算法,。,知识回顾,流程图：是由一些图框和流程线组成的，其中图框表示各种操作的类型，图框中的文字和符号表示操作的内容，流程线表示操作的先后次序。,流程图的概念,顺序结构及框图表示,1.,顺序结构,:,依次,进行多个处理的结构,称为顺序结构,.,语句,A,语句,B,2.,顺序结构的流程图,顺序结构是最简单,、最基本,的算法结构,语句与语句之间,框与框之间是按从上到下的顺序进行的,.,它是由若干个处理步骤组成的,这,是任何一个算法都离不开的基本结构,.,选择结构,也叫条件结构，是指在算法中通过对条件的,判断，根据条件是否成立而选择不同流向的算法结构,右图此结构中包含一个判断框，根据给定的条件,P,是否成立而选择执行,A,框或,B,框无论,P,条件是否成立，只能执行,A,框或,B,框之一，不可能同时执行,A,框和,B,框，也不可能,A,框、,B,框都不执行,开始,S,1,结束,输出,S,i,1,S,S,i,i,1,i,100,N,Y,直到型循环,p,A,Y,N,当型循环,p,A,Y,N,结束,输出,S,S,0,开始,i,i,+1,S,S,+,i,i,10,Y,N,i,0,先执行，后判断：,先判断，后执行：,“N”,进入循环,“Y”,进入循环,循环结构,已学过的伪代码中的几种基本算法语句,:,(1),赋值语句,:,变量表达式或变量或常数,(2),输入语句,:,Read a,b,(3),输出语句,:,(4),条件语句,:,Print,a,b,If,A,Then,B,Else,C,End If,当型语句,:,While,p,循环体,End while,直到型语句,:,Do,循环体,Until,p,End Do,(5),循环语句,伪代码中的,:,p,A,Y,N,p,A,Y,N,当循环的次数已经确定，可用“,For”,语句表示,“,For,”,语句伪代码格式：,For I From “,初值”,To“,终值”,step“,步长”,End For,(6)For,语句,:,3 5,9 15,在小学，我们学过求两个正整数的最大公约数的方法，先用两个数公有的质因数连续去除，一直到所得的商是互质数为止，然后把所以的除数乘起来，例如，求,18,与,30,的最大共约数：,18 30,2,3,所以，,18,与,30,的最大共约数是：,23=6.,引入课题,利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如,求,8251,与,6105,的最大公约数,？,观察上面的式子，你有什么发现？你的发现，对我们解决,“,求,8251,与,6105,的最大公约数”的问题有什么帮助？,8251,61051,2146;,求,8251,与,6105,最大共约数 求,6105,与,2146,最大共约数,化归,6105,21462,1813;,2146,18131,333;,1813,3335,148;,333,1482,37;,148,374,0.,148,与,37,的最大共约数是,37,8251,与,6105,的最大共约数是,37,以上我们求最大公约数的方法就是,辗转相除法,，也叫欧几里德算法，它是由欧几里德在公元前,300,年左右首先提出的,.,练习,:,用,辗转相除法,求,204,与,85,的最大公约数,你能把辗转相除法求最大共约数的过程，写成算法吗？,该算法中，要用到什么主要的算法结构？,每一次循环中所进行的是什么样的运算,？,循环何时结束？下一次循环的输入整数应该是什么？,循环结构,rmod(a,，,b),r=0,ab,br,这样交换数据的方式，前面我们学习过吗？,在求斐波拉契数列中的数,请用自然语言描述该算法,!,S1,输入两个正整数,a,b,（,a,b,）；,S2,若,Mod,（,a,b,）,0,，则输出最大公约数,b,，算法结束；,否则,r,Mod,（,a,b,），,a,b,，,b,r,，转,S2,S1,输入两个正整数,a,，,b,（,a,b,）；,S2 r,Mod,（,a,b,）,S3,a,b,S4,b,r,，,S5,若,r,不等于,0,，转,S2,S6,输出最大公约数,a,.,.,Y,开始,Mod(,a,b,)0,rMod(,a,，,b,),输出,b,结束,N,a,b,b,r,输入,a,b,N,开始,r,0,rMod(,a,，,b,),输出,a,结束,Y,a,b,b,r,输入,a,b,将自然语言描述的算法改写为伪代码,!,Read,a,b,While Mod(,a,b,),0,r,mod(,a,b,),a,b,b,r,End While,Print,b,Read,a,b,Do,r,mod(,a,b,),a,b,b,r,Until r=0,Print,a,