辗转相处法与更相减损术.ppt
1.3 算法案例,【学习目标】,1.理解辗转相除法与更相减损术求最大公约数的方法.2.理解秦九韶算法中求多项式的值的步骤原理.3.能利用除 k 取余法把十进制数化为 k 进制数.,1.辗转相除法的算法步骤第一步，给定两个正整数 m，n(mn).第二步，计算_除以_所得的_数 r.第三步，mn，nr.第四步，若 r0，则 m，n 的最大公约数等于_；否,则，返回第二步.,m,n,余,n,2.更相减损术的算法步骤第一步，任意给定两个正整数，判断它们是否都是偶数.若是用 2 约简；若不是，执行第二步.第二步，以较大的数减去较小的数，接着把所得的差与_比较，并以大数减小数.继续这个操作，直到所得的数_为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.,较小的数,相等,3.秦九韶算法把一个n次多项式f(x)anxnan1xn1a1xa0改写,成如下形式：,(anxn1an1xn2a1)xa0,f(x)anxnan1xn1a1xa0_(anxn2an1xn3a2)xa1)xa0_.,(anxan1)xan2)xa1)xa0,求多项式的值时，首先计算最内层括号内的一次多项式的值，即v1anxan1，然后由内向外逐层计算一次多项式的值，,即：,n,这样，求 n 次多项式 f(x)的值就转化为求_个一次多项式的值.,v1anxan1，v2_，v3v2xan3，vn_，,v1xan2,vn1xa0,4.进位制,(1)k进制数anan1a1a0(k)转化为十进制数为_.(2)把十进制数化为 k 进制数用“_”，即把所给的十进制数除以_，得到商数和余数，再用商数除以 k，得到商数和余数，直到商数为_，把上面各步所得的_从右到左排列，即得到 k 进制数.,除 k 取余法,k,0,余数,anknan1kn1a1ka0,【问题探究】,用秦九韶算法求多项式的值有什么优点？,答案：减少了做乘法运算的次数，优化了求多项式的值的,算法.,题型 1 最大公约数的求法【例 1】用辗转相除法求下面两数的最大公约数，并用更相减损术检验你的结果：,(1)80,36；,(2)294,84.,思维突破：辗转相除法的结束条件是余数为 0，更相减损术的结束条件是差与减数相等.,解：(1)803628，36844，8420，,即 80 与 36 的最大公约数是 4.验证：803644，,44368,36828,28820，20812,1284,844，80 与 36 的最大公约数是 4.,(2)29484342,84422，即 294 与 84 的最大公约数是 42.,验证：294 与 84 都是偶数可同时除以2，即取147 与42,的最大公约数后再乘 2.,14742105,1054263，634221,422121，,294 与 84 的最大公约数为 21242.,辗转相除法求最大公约数的步骤较少，而更相减,损术运算简易，因此解题时要灵活运用.,【变式与拓展】,1.试用算法程序表示用辗转相除法求 144 与 60 的最大公约,数的算法.,解：程序如下：,m144n60,DO,rm MOD nmnnr,LOOP UNTIL r0,PRINT mEND,题型 2 秦九韶算法的应用,【例 2】当 x3 时，求多项式 f(x)x5x3x2x1 的,值.,解：根据秦九韶算法，把多项式改写成如下形式：,f(x)x50 x4x3x2x1(x0)x1)x1)x1)x1.,按照从内到外的顺序，依次计算一次多项式当 x3 时的,值：v01，,v11303，v233110，v3103131，v4313194，v59431283.,所以当 x3 时，多项式的值为 283.,当多项式函数的中间出现空项时，应先补上系数为 0 的相应项.解题时关键是能正确地改写多项式，然后由内向外逐项计算.由于后项计算用到前项的结果，故要认真确保每一项计算的准确性.,【变式与拓展】2.利用秦九韶算法计算多项式 f(x)115x3x27x3 在,x 23 的值时，不会用到下列哪个值(,),D,A.161,B.3772,C.86 641,D.85 169,解析：f(x)115x3x27x3(7x3)x5x11.所以当x23时，v07；v172331613164；v2164235377253767；v33767231186 6411186 652.,题型 3 进制数之间的转化,【例 3】(1)将 101 111 011(2)转化为十进制数；(2)将 1231(5)转化为七进制数.,思维突破：k进制数anan1a2a1a0(k)(0aik)转化为十进制数：anan1a2a1a0(k)anknan1kn1a2k2a1ka01.要将k进制数转化为n进制数(n，k10)，可先将 k 进制数转化为十进制数，然后再转化为所求的n进制数.,解：(1)101 111 011(2)128027126125124123022121120379(10).(2)1231(5)153252351191(10)，1231(5)362(7).,【变式与拓展】,3.填空：,248,130,(1)11 111 000(2)_(10)；(2)154(6)_(7).,【例4】已知f(x)x52x43x34x25x6，用秦九韶算法求这个多项式当 x2 时的值时，做了几次乘法运算？几次加法运算？,解：共做了 5 次乘法运算，5 次加法运算.,易错分析：用秦九韶算法计算多项式f(x)anxnan1xn1a1xa0.当xx0时，首先将多项式改写成f(x)(anxan1)xan2)xa1)xa0形式，然后再计算v1anxan1，v2v1xan2，vnvn1xa0.因此，尽管an是1，但仍进行了5次乘法.,方法规律小结,1.辗转相除法与更相减损术求最大公约数的区别与联系.,2.秦九韶算法的优点.,(1)减少乘法运算的次数.,(2)规律性强，便于利用循环语句实现.,(3)不用对 x 做幂的运算，每次都是计算一个一次多项式的,值，提高了计算精度.,3.进位制的理解.,进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值.使用数字符号的个数称为基数，基数为 n，即称为n 进位制，简称 n 进制.现在最常用的是十进制，通常使用 10 个阿拉伯数字 09 进行记数.,对于任何一个数，我们可以用不同的进位制来表示.比如：十进数 57，可以用二进制表示为 111 001，也可以用八进制表示为 71，用十六进制表示为 39，它们所代表的数值都是一样的.表示各种进制数时，一般要在数字右下角加注来表示.如111 001(2)表示二进制数，34(5)表示五进制数.电子计算机一般都使用二进制.,
