教育专题：13算法案例

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,主备人,：唐强 王廷伟 向妍燕,审,核人：牟必继,善于奋飞的人天上有路，敢于攀登的人山中有路，,勇于远航的人海里有路，勤于学习的人脚下有路!,1.3算法案例,案例,1,辗转相除法与更相减损术,（第,一课时,）,3 5,9 15,问题,1,：在小学，我们已经学过求最大公约数的知识，你能求出,18,与,30,的最大公约数吗？,创设情景，揭示课题,18 30,2,3,18,和,30,的最大公约数是,23=6.,先用两个数公有的,质因数,连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来,.,问题,2:,我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求,8251,与,6105,的最大公约数,?,研探新知,1.,辗转相除法,:,例,1,求两个正数,8251,和,6105,的最大公约数。,分析：,8251,与,6105,两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数,.,解：,8251,6105,1,2146,显然,8251,与,6105,的最大公约数也必是,2146,的约数，同样,6105,与,2146,的公约数也必是,8251,的约数，所以,8251,与,6105,的最大公约数也是,6105,与,2146,的最大公约数。,研探新知,1.,辗转相除法,:,例,1,求两个正数,8251,和,6105,的最大公约数。,解：,8251,6105,1,2146;,6105,21462,1813;,2146,18131,333;,1813,3335,148;,333,1482,37;,148,374,0.,则,37,为,8251,与,6105,的最大公约数。,以上我们求最大公约数的方法就是,辗转相除法,。也叫,欧几里德算法,，它是由欧几里德在公元前,300,年左右首先提出的。,利用辗转相除法求最大公约数的步骤如下：,第一步：用较大的数,m,除以较小的数,n,得到一个商,q,0,和一个余数,r,0,；,(m=nq,0,+r,0,),第二步：若,r,0,0,，则,n,为,m,，,n,的最大公约数；若,r,0,0,，则用除数,n,除以余数,r,0,得到一个商,q,1,和一个余数,r,1,；,(n=r,0,q,1,+r,1,),第三步：若,r,1,0,，则,r,0,为,m,，,n,的最大公约数；若,r,1,0,，则用除数,r,0,除以余数,r,1,得到一个商,q,2,和一个余数,r,2,；,(r,0,=r,1,q,2,+r,2,),依次计算直至,r,n,0,，此时所得到的,r,n-1,即为所求的最大公约数。,第一步,给定两个正数,m,n,第二步,计算,m,除以,n,所得到余数,r,第三步,m=,n,n,=r,第四步,若,r=0,则,m,n,的最大公约数等于,m;,否则返回第二步,.,辗转相除法求最大公约数算法：,否,4.,辗转相除法的程序框图及程序,:,开始,输入两个正数,m,n,mn?,r=m MOD n,r0?,输出,n,结束,m=x,m=n,n=r,否,是,是,INPUT,m,n,IF mn,第二步,若,m,n,都是偶数,则不断用,2,约简,使他们不同时是偶数,约简后的两个数仍记为,m,n,第三步,d=,m-n,第四步,判断,”,d0”,是否成立,若是,则将,n,d,中较大者记为,m,较小的记为,n,返回第三步,;,否则,2k*,d(k,是约简整数的,2,的个数,),为所求的最大公约数,.,更相减损术算法,开始,输,m,n(m,n),K=0,M,n,为偶数,?,K=k+1,M=m/2,N=n/2,D=,m-n,Dn?,Dn?,是,否,M=n,N=d,D=,m-n,M=d,是,输出,2k d,结束,是,否,INPUT “,m,n,=“;,m,n,IF mn then,m=d,ELSE,m=n,n=d,End if,d=,m-n,Wend,d=2k*d,PRINT d,End,3.,辗转相除法与更相减损术的比较,:,（,1,）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主,;,计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。,（,2,）从结果体现形式来看，辗转相除法体现结果是以相除余数为,0,则得到，而更相减损术则以减数与差相等而得到,.,作业,:,课本,P45,页练习,T1;,P48,页,A,组,T1.,案例,2,秦九韶算法,（第二课时）,教学设计,问题,1,设计求多项式,f(x,)=2x,5,-5x,4,-4x,3,+3x,2,-6x+7,当,x=5,时的值的算法,并写出程序,.,x=5,f=2,x5-5,x4-4,x3+3,x2-6,x+7,PRINT f,END,程序,点评,:,上述算法一共做了,15,次乘法运算,5,次加法运算,.,优点是简单,易懂,;,缺点是不通用,不能解决任意多项多求值问题,而且计算效率不高,.,这析计算上述多项式的值,一共需要,9,次乘法运算,5,次加法运算,.,问题,2,有没有更高效的算法,?,分析,:,计算,x,的幂时,可以利用前面的计算结果,以减少计算量,即先计算,x,2,然后依次计算,的值,.,第二种做法与第一种做法相比,乘法的运算次数减少了,因而能提高运算效率,.,而且对于计算机来说,做一次乘法所需的运算时间比做一次加法要长得多,因此第二种做法能更快地得到结果,.,问题,3,能否探索更好的算法,来解决任意多项式的求值问题,?,f(x,)=2x,5,-5x,4,-4x,3,+3x,2,-6x+7,=(,2x,4,-5x,3,-4x,2,+3x-6)x+7,=(2x,3,-5x,2,-4x+3)x-6)x+7,=(2x,2,-5x-4)x+3)x-6)x+7,=(2x-5)x-4)x+3)x-6)x+7,v,0,=2,v,1,=v,0,x-5=25-5=5,v,2,=v,1,x-4=55-4=21,v,3,=v,2,x+3,=215+3=108,v,4,=v,3,x-6,=1085-6=534,v,5,=v,4,x+7=5345+7=2677,所以,当,x=5,时,多项式的值是,2677.,这种求多项式值的方法就叫,秦九韶算法,.,例,1:,用秦九韶算法求多项式,f(x,)=2x,5,-5x,4,-4x,3,+3x,2,-6x+7,当,x=5,时的值,.,解法一,:,首先将原多项式改写成如下形式,:,f(x,),=(2x-5)x-4)x+3)x-6)x+7,v,0,=2 v,1,=v,0,x-5=25-5=5,v,2,=v,1,x-4=55-4=21,v,3,=v,2,x+3=215+3=108,v,4,=v,3,x-6=1085-6=534,v,5,=v,4,x+7=5345+7=2677,所以,当,x=5,时,多项式的值是,2677.,然后由内向外逐层计算一次多项式的值,即,2 -5 -4 3 -6 7,x=5,10,5,25,21,105,108,540,534,2670,2677,所以,当,x=5,时,多项式的值是,2677.,原多项式的系数,多项式的值,.,例,1:,用秦九韶算法求多项式,f(x,)=2x,5,-5x,4,-4x,3,+3x,2,-6x+7,当,x=5,时的值,.,解法二,:,列表,2,2 -5 0 -4 3 -6 0,x=5,10,5,25,25,125,121,605,608,3040,3034,所以,当,x=5,时,多项式的值是,15170.,练一练,:,用秦九韶算法求多项式,f(x,)=2x,6,-5x,5,-4x,3,+3x,2,-6x,当,x=5,时的值,.,解,:,原多项式先化为,:,f(x,)=2x,6,-5x,5,+,0,x,4,-4x,3,+3x,2,-6x+,0,列表,2,15170,15170,注意,:n,次多项式有,n+1,项,因此缺少哪一项应将其系数补,0.,f(x,)=a,n,x,n,+a,n-1,x,n-1,+a,n-2,x,n-2,+a,1,x+a,0,.,我们可以改写成如下形式,:,f(x,)=(a,n,x+a,n-1,)x+a,n-2,)x+a,1,)x+a,0,.,求多项式的值时,首先计算最内层括号内一次多项式的值,即,v,1,=a,n,x+a,n-1,然后由内向外逐层计算一次多项式的值,即,一般地,对于一个,n,次多项式,v,2,=v,1,x+a,n-2,v,3,=v,2,x+a,n-3,v,n,=v,n-1,x+a,0,.,这样,求,n,次多项式,f(x,),的值就转化为求,n,个一次多项式的值,.,这种算法称为,秦九韶算法,.,点评,:,秦九韶算法是求一元多项式的值的一种方法,.,它的特点是,:,把求一个,n,次多项式的值转化为求,n,个一次多项式的值,通过这种转化,把运算的次数由至多,n(n+1)/2,次乘法运算和,n,次加法运算,减少为,n,次乘法运算和,n,次加法运算,大大提高了运算效率,.,v,1,=a,n,x+a,n-1,v,2,=v,1,x+a,n-2,v,3,=v,2,x+a,n-3,v,n,=v,n-1,x+a,0,.,观察上述秦九韶算法中的,n,个一次式,可见,v,k,的计算要用到,v,k-1,的值,.,若令,v,0,=a,n,得,v,0,=a,n,v,K,=v,K-1,x+a,n-k,(k=1,2,n,这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现,.,问题,画出程序框图,表示用秦九韶算法求,5,次多项式,f(x,)=a,5,x,5,+a,4,x,4,+a,3,x,3,+a,2,x,2,+a,1,x+a,0,当,x=x,0,(x,0,是任意实数,),时的值的过程,然后写出程序,.,否,程序框图,开始,输入,a,0,a,1,a,2,a,3,a,4,a,5,输入,x,0,n5?,n=1,v=a,5,v=vx,0,+a,5-n,n=n+1,输出,v,结束,是,INPUT a,0,a,1,a,2,a,3,a,4,a,5,INPUT x,0,n=1,v=a,5,WHILE n=5,v=vx,0,+a,5-n,n=n+1,WEND,PRINT v,END,程序,课本,P45,页练习,T2;,P48,页,A,组,T2.,问题,1,我们常见的数字都是十进制的,但是并不是生活中的每一种数字都是十进制的,.,比如时间和角度的单位用六十进位制,电子计算机用的是二进制,.,那么什么是进位制,?,不同的进位制之间又有什么联系呢,?,进位制是人们为了计数和运算的方便而约定的一种记数系统，约定满二进一,就是二进制,;,满十进一,就是十进制,;,满十六进一,就是十六进制,;,等等,.,“满几进一”,就是几进制,几进制的,基数,就是几,.,可使用数字符号的个数称为基数,.,基数都是大于,1,的整数,.,如二进制可使用的数字有,0,和,1,基数是,2;,十进制可使用的数字有,0,1,2,8,9,等十个数字,基数是,10;,十六进制可使用的数字或符号有,09,等,10,个数字以及,AF,等,6,个字母,(,规定字母,AF,对应,1015),十六进制的基数是,16.,注意,:,为了区分不同的进位制,常在数字的右下脚标明基数,.,如,111001,(2),表示二进制数,34,(5),表示,5,进制数,.,十进制数一般不标注基数,.,问题,2,十进制数,3721,中的,3,表示,3,个千,7,表示,7,个百,2,表示,2,个十,1,表示,1,个一,从而它可以写成下面的形式,:,3721=310,3,+710,2,+210,1,+110,0,.,想一想二进制数,1011,(2),可以类似的写成什么形式,?,1011,(2),=12,3,+02,2,+12,1,+12,0,.,同理,:,3421,(5),=35,3,+45,2,+25,1,+1