资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.3,算法案例,【,学习目标,】,1.,理解辗转相除法与更相减损术求最大公约数的方法,.,2.,理解秦九韶算法中求多项式的值的步骤原理,.,3.,能利用除,k,取余法把十进制数化为,k,进制数,.,1.,辗转相除法的算法步骤,第一步，给定两个正整数,m,，,n,(,m,n,).,第二步，计算,_,除以,_,所得的,_,数,r,.,第三步，,m,n,，,n,r,.,第四步，若,r,0,，则,m,，,n,的最大公约数等于,_,；否,则，返回第二步,.,m,n,余,n,2.,更相减损术的算法步骤,第一步，任意给定两个正整数，判断它们是否都是偶数,.,若,是用,2,约简；若不是，执行第二步,.,第二步，以较大的数减去较,小的数，接着把所得的差与,_,比较，并以大数减小数,.,继续这个操作，直到所得的数,_,为止，则这个数,(,等数,),或这个数与约简的数的乘积就,是所求的最大公约数,.,较小的数,相等,3.,秦九韶算法,把一个,n,次多项式,f,(,x,),a,n,x,n,a,n,1,x,n,1,a,1,x,a,0,改写,成如下形式：,(,a,n,x,n,1,a,n,1,x,n,2,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,n,2,a,n,1,x,n,3,a,2,),x,a,1,),x,a,0,_.,(,(,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,这样，求,n,次多项式,f,(,x,),的值就转化为求,_,个一次多项,式的值,.,v,1,a,n,x,a,n,1,，,v,2,_,，,v,3,v,2,x,a,n,3,，,v,n,_,，,v,1,x,a,n,2,v,n,1,x,a,0,4.,进位制,(1),k,进制数,a,n,a,n,1,a,1,a,0(,k,),转化为十进制数为,_.,(2),把十进制数化为,k,进制数用“,_”,，即把所给,的十进制数除以,_,，得到商数和余数，再用商数除以,k,，,得到商数和余数，直到商数为,_,，把上面各步所得的,_,从右到左排列，即得到,k,进制数,.,除,k,取余,法,k,0,余数,a,n,k,n,a,n,1,k,n,1,a,1,k,a,0,【,问题探究,】,用秦九韶算法求多项式的值有什么优点？,答案：,减少了做乘法运算的次数，优化了求多项式的值的,算法,.,题型,1,最大公约数的求法,【,例,1,】,用辗转相除法求下面两数的最大公约,数，并用更,相减损术检验你的结果：,(1)80,36,；,(2)294,84.,思维突破：,辗转相除法的结束条件是余数为,0,，更相减损,术的结束条件是差与减数相,等,.,解：,(1)80,362,8,，,36,84,4,，,8,42,0,，,即,80,与,36,的最大公约数是,4.,验证：,80,36,44,，,44,36,8,36,8,28,28,8,20,，,20,8,12,12,8,4,8,4,4,，,80,与,36,的最大公约数是,4.,(2)294,843,42,84,422,，,即,294,与,84,的最大公约数是,42.,验证：,294,与,84,都是偶数可同时除以,2,，即取,147,与,42,的最大公约数后再乘,2.,147,42,105,10,5,42,63,，,63,42,21,42,21,21,，,294,与,84,的最大公约数为,212,42.,辗转相除法求最大公约数的步骤较少，而更相减,损术运算简易，因此解题时要灵活运用,.,【,变式与拓展,】,1.,试用算法程序表示用辗转相除法求,144,与,60,的最大公约,数的算法,.,解：,程序如下：,m,1,44,n,60,DO,r,m,MOD n,m,n,n,r,LOOP UNTIL r,0,PRINT m,END,题型,2,秦九韶,算法的应用,【,例,2,】,当,x,3,时，求多项式,f,(,x,),x,5,x,3,x,2,x,1,的,值,.,解：,根据秦九韶算法，把多项式改写成如下形式：,f,(,x,),x,5,0,x,4,x,3,x,2,x,1,(,x,0),x,1),x,1),x,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,时,，,多项式的值为,283.,当多项式函数的中间出现空项时，应先补上系,数为,0,的相应项,.,解题时关键是能正确地改写多项式，然后由内,向外逐项计算,.,由于后项计算用到前项的结果，故要认真确保每,一项计算的,准确性,.,【,变式与拓展,】,2.,利用秦九韶算法计算多项式,f,(,x,),11,5,x,3,x,2,7,x,3,在,x,23,的值时，不会用到下列哪个值,(,),D,A.161,B.3772,C.86 641,D.85 169,解析：,f,(,x,),11,5,x,3,x,2,7,x,3,(7,x,3),x,5,x,11.,所以当,x,23,时，,v,0,7,；,v,1,7,23,3,161,3,164,；,v,2,164,23,5,3772,5,3767,；,v,3,3767,23,11,86 641,11,86 652.,题型,3,进制数,之间的转化,【,例,3,】,(1),将,101 111 011,(2),转化为十进制数；,(2),将,1231,(5),转化为七进制数,.,思维突破：,k,进制数,a,n,a,n,1,a,2,a,1,a,0(,k,),(0,a,i,k,),转化为十进制数：,a,n,a,n,1,a,2,a,1,a,0(,k,),a,n,k,n,a,n,1,k,n,1,a,2,k,2,a,1,k,a,0,1.,要将,k,进制数转化为,n,进制数,(,n,，,k,10),，可先将,k,进制数转化为十进制数，然后再转化为所求的,n,进制数,.,解：,(1)101 111 011,(2),12,8,02,7,12,6,12,5,12,4,12,3,02,2,12,1,12,0,379,(10).,(2)1231,(5),15,3,25,2,35,1,191,(10),，,1231,(5),362,(7).,【,变式与拓展,】,3.,填空：,248,130,(1)11 111 000,(2),_,(10),；,(2)154,(6),_,(7).,【,例,4】,已知,f,(,x,),x,5,2,x,4,3,x,3,4,x,2,5,x,6,，用秦九韶,算法求这个多项式当,x,2,时的值时，做了几次乘法运算？几次,加,法运算？,解：,共做了,5,次乘法运算，,5,次加法运算,.,易错分析：,用秦九韶算法计算多项式,f,(,x,),a,n,x,n,a,n,1,x,n,1,a,1,x,a,0,.,当,x,x,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,，,v,2,v,1,x,a,n,2,，,，,v,n,v,n,1,x,a,0,.,因此，尽管,a,n,是,1,，但仍进行了,5,次乘法,.,名称,辗转相除法,更相减损术,区别,以除法为主,两个整数的差较大,时，运算次数减少,余数为,0,时结束,以减法为主,两个整数的差较大时，,运算次数多,两数相等时结束,联系,都是求最大公约数的方法 都用到递推方法,都用循环结构来实现,方法,规律,小结,1.,辗转相除法与更相减损术求最大公约数的区别与联系,.,2.,秦九韶算法的优点,.,(1),减少乘法运算的次数,.,(2),规律性强，便于利用循环语句实现,.,(3),不用对,x,做幂的运算，每,次都是计算一个一次多项式的,值，提高了计算精度,.,3.,进位制的理解,.,进位制是一种记数方式，用有限的数字在不同的位置表示,不同的数值,.,使用数字符号的个数称为基数，基数为,n,，即称为,n,进位制，简称,n,进制,.,现在最常用的是十进制，通常使用,10,个,阿拉伯数字,0,9,进行记数,.,对于任何一个数，我们可以用不同的进位制来表示,.,比如：,十进数,57,，可以用二进制表示为,111 001,，也可以用八进制表,示为,71,，用十六进制表示为,39,，它们所代表的数值都是一样的,.,表示各种进制数时，一般要在数字右下角加注来表示,.,如,111 001,(2),表示二进制数，,34,(5),表示五进制数,.,电子计算机一般都,使用二进制,.,
展开阅读全文