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