高中数学第一章算法初步13算法案例课件必修.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,1.3,算法案例,【,知识提炼,】,1.,辗转相除法与更相减损术,(1),辗转相除法,：,辗转相除法：又叫,_,算法，是一种求两个正整数的,_,的古老有效的算法,.,欧几里得,最大公约数,程序,INPUT,m,，,n,DO,r,=_,m=n,n=r,LOOP UNTIL,r=0,PRINT,m,END,m MOD n,(2),更相减损术：,我国古代数学专著,九章算术,中介绍的一种求两个正整数的,_,的算法,.,运算过程,第一步，任意给定两个正整数，判断它们是否都是偶数，若是，,_,；若不是，执行第二步,.,最大公约数,用,2,约简,第二步，以较大的数减去较小的数，接着把所得的差与,_,比,较，并以大数减小数,.,继续这个操作，直到所得的数,_,为止，则,这个数,(,等数,),或这个数与约简的数的乘积就是所求的最大公约数,.,较小的数,相等,2.,秦九韶算法,功能,计算,n,次多项式,f(x)=a,n,x,n,+a,n-1,x,n-1,+a,1,x+a,0,的值,改写后,的形式,f(x)=a,n,x,n,+a,n-1,x,n-1,+a,1,x+a,0,=(a,n,x+a,n-1,)x+a,n-2,)x+a,1,)x+a,0,(2),不同进位制之间的互化：,k,进制,化为十进制的方法：,a,n,a,n-1,a,1,a,0(k),=_(a,n,，,a,n-1,，,，,a,1,，,a,0,N,，,0a,n,k,，,0a,n-1,，,，,a,1,，,a,0,n),，,(1),用,m,除以,n,，若商为,q,1,，余数为,r,1,(0r,1,n),，则,m=n,q,1,+r,1,，显然若,x,是,m,和,n,的公约数，即,x,能整除,m,和,n,，则,x,也必然能整除,r,1,，这样,x,也是,n,和,r,1,的公约数，故求,m,和,n,的公约数就是求,n,和,r,1,的公约数,.,(2),用,n,除以,r,1,，得,n=r,1,q,2,+r,2,(0r,2,nr,1,r,2,，所以到某一步必然有,r,i,=r,i+1,q,i+2,，即,r,i,恰能被,r,i+1,整除，这时,r,i+1,是,r,i,和,r,i+1,的公约数，它也必然是,r,i-1,和,r,i,，,r,i-2,和,r,i-1,，,，,r,1,与,r,2,，,n,和,r,1,，,m,和,n,的最大公约数,.,2.,更相减损术求最大公约数的程序设计,【,知识拓展,】,更相减损术与辗转相除法的区别与联系,辗转相除法,更相减损术,区别,以除法为主,两个整数差值较大时运算次数较少,相除余数为零时得结果,以减法为主,两个整数的差值较大时，运算次数较多,相减，差与减数相等得结果,相减前要做是否都是偶数的判断,联系,都是求最大公约数的方法,二者的实质都是递归的过程,二者都要用循环结构来实现,知识点,2,秦九韶算法,观察如图所示内容，回答下列问题：,问题,1,：秦九韶算法的计数原理是怎样的,?,问题,2,：应按照怎样的步骤进行秦九韶算法,?,【,总结提升,】,1.,秦九韶算法的计数原理,秦九韶算法是按照从内到外的顺序依次计算求值的,.,设,f(x)=a,n,x,n,+a,n-1,x,n-1,+,+a,1,x+a,0,，,则该算法先计算,v,1,=a,n,x+a,n-1,，再计算,v,2,=v,1,x+a,n-2,，,，,最后计算,v,n,=v,n-1,x+a,0,.,2.,秦九韶算法的步骤,知识点,3,进位制,观察如图所示内容，回答下列问题：,问题,1,：进位制应如何表示,?,问题,2,：常见的进位制有哪些,?,【,总结提升,】,1.,进位制的表示,若一个数为十进制数，则其基数可以省略不写，若是其他进位制的数，在没有特别说明的前提下，其基数必须写出，常在数的右下角标明基数,.,2.,常见的进位制,(1),二进制：,只使用,0,和,1,两个数字；满二进一，如,1+1=10,(2),.,(2),八进制：,使用,0,，,1,，,2,，,3,，,4,，,5,，,6,，,7,八个不同的数字；满八进一，如,7+1=10,(8),.,(3),十六进制：,使用,0,，,1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,，,9,，,A,，,B,，,C,，,D,，,E,，,F,这十六个不同的数码，其中,A,，,B,，,C,，,D,，,E,，,F,分别代表十进制中的,10,，,11,，,12,，,13,，,14,，,15,；满十六进一，如,F+1=2+E=10,(16),.,【,题型探究,】,类型一,求最大公约数,【,典例,】,1.(2015,大同高一检测,),用辗转相除法求,378,与,90,的最大公约数为,.,2.(2015,衡水高一检测,),用更相减损术求,294,与,84,的最大公约数时，需做减法的次数是,.,3.,求,104,与,65,的最大公约数,.,【,解题探究,】,1.,典例,1,中应将两数怎样进行相除,?,提示：,应将,294,除以,84,，用较大的数除以较小的数依次进行,.,2.,典例,2,中应用更相减损术时要做的第一步工作是什么,?,提示：,由于,294,与,84,都是偶数，因此应先将两数都除以,2,再进行,.,3.,典例,3,中如何探求两数的最大公约数,?,提示：,可采用辗转相除法或更相减损术求两数的最大公约数,.,【,解析,】,1.378=904+18,，,90=185+0,，,所以,378,与,90,的最大公约数是,18.,答案：,18,2.,因为,294,与,84,是偶数，首先除以,2,得到,147,，,42,，再求,147,与,42,的最大公约数,147-42=105,，,105-42=63,，,63-42=21,，,42-21=21,，共做了,4,次减法,.,答案：,4,3.,方法一,(,辗转相除法,),第一步：,10465=165+39,第二步：,65=139+26,第三步：,39=126+13,第四步：,26=213+0,所以,104,和,65,的最大公约数为,13.,方法二,(,更相减损术,),由于,65,不是偶数，把,104,和,65,以大数减小数，并辗转相减，即,104-65=39,，,65-39=26,，,39-26=13,，,26-13=13,，,所以,104,和,65,的最大公约数为,13.,【,方法技巧,】,1.,辗转相除法的算法步骤,第一步，输入两个正整数,m,，,n(mn).,第二步，计算,m,除以,n,所得的余数,r.,第三步，,m=n,，,n=r.,第四步，若,r=0,，则,m,，,n,的最大公约数等于,m,；,否则，返回第二步,.,第五步，输出最大公约数,m.,2.,更相减损术的求解步骤,第一步，给定两个正整数,m,，,n(mn,且,m,，,n,不全是偶数,).,第二步，计算,m-n,所得的差,k.,第三步，比较,n,与,k,的大小，其中大者用,m,表示，小者用,n,表示,.,第四步，若,m=n,，则,m,，,n,的最大公约数等于,m,；否则，返回第二步,.,【,拓展延伸,】,三个数的最大公约数的求解方法,(1),从三个数中任取两个数，用辗转相除法或更相减损术求它们的最大公约数,.,(2),根据辗转相除法或更相减损术求所求得的最大公约数和第三个数的最大公约数,.,(3),求得的最大公约数即为这三个数的最大公约数,.,【,变式训练,】,1.,用辗转相除法求,225,和,135,的最大公约数,.,2.,用更相减损术求,1734,，,816,的最大公约数,.,【,解析,】,1.225=1351+90,，,135=901+45,，,90=452,，,所以,45,是,225,和,135,的最大公约数,.,2.,因为两数皆为偶数，首先除以,2,得到,867,，,408,，再求,867,与,408,的最大公约数,.,867-408=459,，,459-408=51,，,408-51=357,，,357-51=306,，,306-51=255,，,255-51=204,，,204-51=153,，,153-51=102,，,102-51=51,，,所以,1734,与,816,的最大公约数是,512=102.,类型二,秦九韶算法的应用,【,典例,】,1.,用秦九韶算法计算多项式,f(x)=3x,6,+4x,5,-5x,4,+6x,3,-7x,2,+8x+1,当,x=2,时的值时，需要做乘法和加法的次数分别是,(,),A.6,，,6,B.5,，,6,C.5,，,5,D.6,，,5,2.,用秦九韶算法求多项式,f(x)=8x,7,+5x,6,+3x,4,+2x+1,，当,x=2,时的值,.,【,解题探究,】,1.,典例,1,中多项式的最高次数是几，多少项相加,?,2.,典例,2,中不含,x,5,，,x,3,及,x,2,项怎么办,?,【,探究提示,】,1.,典例,1,中多项式的最高次数是,6,，共,7,项相加,.,2.,先把多项式,f(x)=8x,7,+5x,6,+3x,4,+2x+1,变形为,f(x)=8x,7,+5x,6,+0,x,5,+3,x,4,+0,x,3,+0,x,2,+2x+1.,【,解析,】,1.,选,A.,由秦九韶算法将多项式改成如下形式：,f(x)=(3x+4)x-5)x+6)x-7)x+8)x+1,，,按由内到外的顺序，依次计算,x=2,时的值,.,v,0,=3,，,v,1,=32+4=10.,v,2,=102-5=15,，,v,3,=152+6=36,，,v,4,=362-7=65,，,v,5,=652+8=138,，,v,6,=1382+1=277.,这样求多项式的值时，是通过求,6,个一次多项式的值得到的，故进行了,6,次乘法和,6,次加法,.,2.,根据秦九韶算法，把多项式改写成如下形式：,f(x)=8x,7,+5x,6,+0,x,5,+3,x,4,+0,x,3,+0,x,2,+2x+1,=(8x+5)x+0)x+3)x+0)x+0)x+2)x+1.,而,x=2,，所以有,v,0,=8,，,v,1,=82+5=21,，,v,2,=212+0=42,，,v,3,=422+3=87,，,v,4,=872+0=174,，,v,5,=1742+0=348,，,v,6,=3482+2=698,，,v,7,=6982+1=1397.,所以当,x=2,时，多项式的值为,1397.,【,延伸探究,】,典例,2,中需要做乘法和加法的次数是多少,?,【,解析,】,根据秦九韶算法，把多项式改写成如下形式：,f(x)=8x,7,+5x,6,+0,x,5,+3,x,4,+0,x,3,+0,x,2,+2x+1=(8x+5)x+0)x+3)x+0)x+2)x+1.,而,x=2,，所以有,v,0,=8,，,v,1,=82+5=21,，,v,2,=212+0=42,，,v,3,=422+3=87,，,v,4,=872+0=174,，,v,5,=1742+0=348,，,v,6,=3482+2=698,，,v,7,=6982+1=1397.,所以当,x=2,时，多项式的值为,1397.,这样求多项式的值时，是通过求,7,个一次多项式的值得到的，故进行了,7,次乘法和,7,次加法,.,【,方法技巧,】,应用秦九韶算法计算多项式的值应注意的问题,(1),要正确将多项式的形式进行改写,.,(2),计算应由内向外依次计算,.,(3),当多项式函数中间出现空项时，要以系数为零的齐次项补充,.,【,变式训练,】,1.,已知,f(x)=x,5,+2x,3,+3x,2,+x+1,，应用秦九韶算法计算当,x=3,时，,v,2,的值为,(,),A.27,B.11,C.109,D.36,2.(2015,福州高一检测,),用秦九韶算法写出当,x=3,时,f(x)=2x,5,-4x,3,+3x,2,-5x+1,的值,.,【,解析,】,1.,选,B.,将多项式改写成如下形式：,f(x)=(x+0)x+2)x+3)x+1)x+1,，,由内向外依次计算：,v,0,=1,，,v,1,=13+0=3,，,v,2,=33+2=11.,2.,因为,f(x)=(2x-0)x-4)x+3)x-5)x+1,，,v,0,=2,，,v,1,=23+0=6,，,v,2,=63-4=14,，,v,3,=143+3=45,，,v,4,=453-5=130,，,v,5,=1303+1=391,，,所以,f(3)=391.,类型三,进位制及其转化,【,典例,】,1.(2015,抚顺高一检测,),把二进制数,101101,(2),化为十进制数为,.,2.,将十进制数,458,转化为四进制数为,.,3.,比较,85,(9),和,210,(6),的大小,.,【,解题探究,】,1.,典例,1,中二进制数右数第,i,位数字,a,i,化为十进制数是什么数,?,提示：,a,i,2,i-1,.,2.,典例,2,中应按照怎样的方法将,458,转化为四进制的数,?,提示：,用,4,连续去除该十进制数得到商，直到商为零为止，然后把每次所得的余数倒着排成一个数，就是相应的四进制数,.,3.,典例,3,中比较,85,(9),和,210,(6),的大小的关键是什么,?,提示：,比较这两个数的关键是统一进位制，可将两个数转化为十进制数进行比较,.,【,解析,】,1.101101,(2),=12,5,+02,4,+12,3,+12,2,+02,1,+12,0,=32+8+4+1=45,，,所以二进制数,101101,(2),转化为十进制的数为,45.,答案：,45,2.,458=13022,(4),.,答案：,13022,(4),3.,因为,85,(9),=5+89=77,，,210,(6),=0+16+26,2,=78,，而,7877,，,所以,210,(6),85,(9),.,【,延伸探究,】,1.(,改变问法,),把典例,2,中的数转化成六进制的数，结果如何,?,【,解析,】,458=2042,(6),.,2.(,改变问法,),把典例,2,中的数转化成八进制的数，结果如何,?,【,解析,】,所以,458=712,(8),.,【,方法技巧,】,十进制数转化为其他进制数的方法步骤,【,补偿训练,】,将,235,(7),转化为八进制数,.,【,解题指南,】,先将非十进制数转化为十进制数，再向其他,k,进制数转化，注意十进制数的中间作用,.,【,解析,】,235,(7),=27,2,+37+57,0,=124,(10),，,所以,124,(10),=174,(8),，即,235,(7),=174,(8).,【,延伸探究,】,1.(,变换条件,),若将,“,235,(7),”,变为,“,235,(6),”,，如何转化为八进制数,?,【,解析,】,因为,235,(6),=26,2,+36,1,+56,0,=95,(10),所以,95,(10),=137,(8),故,235,(6),=137,(8),2.(,改变问法,),如何将,235,(7),转变成四进制数,?,【,解析,】,因为,235,(7),=27,2,+37+57,0,=124,(10),所以,237,(7),=1330,(4),.,易错案例,利用秦九韶算法求多项式的值,【,典例,】,(2015,哈尔滨高一检测,),已知,f(x)=x,5,+x,3,+x,2,+x+1,，用秦九韶算法求,f(3),的值,.,【,失误案例,】,【,错解分析,】,分析解题过程，你知道错在哪里吗,?,提示：,错误的根本原因在于当多项式中间出现空项时，用秦九韶算法求函数值时没有补上系数为,0,的相应相项,.,【,自我矫正,】,原多项式可化为：,f(x)=(x+0)x+1)x+1)+1)x+1,，,当,x=3,时，,v,0,=1,，,v,1,=13+0=3,，,v,2,=33+1=10,，,v,3,=103+1=31,，,v,4,=313+1=94,，,v,5,=943+1=283,，所以，当,x=3,时，,f(3)=283.,【,防范措施,】,1.,多项式改写要恰当、正确,利用秦九韶算法计算多项式的值之前，必须先对多项式进行改写，多项式各项的次数按从高到低进行排列，如果有系数为,0,的项，要补全，然后再进行改写，否则容易出现如本题中,f(x)=(x+1)x+1)x+1)x+1,的错误,.,2.,计算要准确,利用秦九韶算法计算多项式值的过程中，要进行多次计算，每一步中间结果要准确，如本题中,v,0,，,v,1,，,v,2,，,v,3,，,v,4,，,v,5,的计算都要准确无误，否则就可能导致错误出现,.,