《算法案例辗转相除法与更相减损术秦九韶算法与进位制课件数学高一必修算法初步人教版》由会员分享，可在线阅读，更多相关《算法案例辗转相除法与更相减损术秦九韶算法与进位制课件数学高一必修算法初步人教版（48页珍藏版）》请在金锄头文库上搜索。
1、 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进制数anan1a1a0(k)转化为十进
3、制数为_.(2)把十进制数化为 k 进制数用“_”，即把所给的十进制数除以_，得到商数和余数，再用商数除以 k，得到商数和余数，直到商数为_ ，把上面各步所得的_从右到左排列，即得到 k 进制数.除 k 取余法k0余数anknan1kn1a1ka0【问题导思】 1如何求18与54的最大公约数？【提示】 短除法2要求6 750与3 492的最大公约约数，上述法还还好用吗吗？【提示】 数值太大，短除法不方便用知识1 求两个正整数最大公约数的算法(1)更相减损损之术术(等值值算法)用两个数中较较大的数减去较较小的数，再用和构成新的一对对数，对这对这 一对对数再用减，以同样样的操作一直做下去，直到产产
4、生，这这个数就是最大公约约数(2)辗转辗转 相除法(欧几里得算法)用较较大的数除以较较小的数所得的和_构成新的一对对数，继续继续 做上面的除法，直到，这这个较较小的数就是最大公约约数.差数较小的数大 数小数一对相等的数余数 较小的数大数被小数除尽【问题导思】 1怎样计算多项式f(x)x5x4x3x2x1当x5时的值呢？统计所做的计算的种类及计算次数分别是什么？【提示】 f(5)55545352513 906.根据我们的计算统计可以得出我们共需要10次乘法运算，5次加法运算知识2 秦九韶算法2我们们把多项项式变变形为为f(x)x2(1x(1x(1x)x1，再统计统计 一下计计算当x5时时的计计算
5、的种类类及计计算次数分别别是什么？【提示】 从里往外计算仅需4次乘法和5次加法运算即可得出结果(1)把一元n次多项项式P(x)anxnan1xn1a1xa0改写为为P(x)anxnan1xn1a1xa0(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1)xan2)xa1)xa0，令vk(anxan1)xan(k1)xank，(2)计计算P(x0)的方法先计计算，然后逐层计层计 算，直到，然后加上最内层括号由内向外最外层括号常数项知识3 进位制 进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值.使用数字符号的个数称为基数，基数为 n，即称为
6、n 进位制，简称 n 进制.现在最常用的是十进制，通常使用 10 个阿拉伯数字 09 进行记数.例1 .分别别用辗转辗转 相除法和等值值算法求319和261的最大公约约数【分析】 使用辗转相除法可依据mnqr，反复执行，直到r0为止；用等值算法是根据mnr，直到n1为止【解析】 辗转相除法：3192611(余58)，261584(余29)，58292(余0)所以319与261的最大公约数是29.等值算法：31926158，26158203，20358145，1455887，875829，582929.即(319，261)(261，58)(203，58)(145，58)(87，58)(58，29
7、)(29，29)所以319与261的最大公约数是29.1利用“等值算法”求给定的两个数的最大公约数，即多次利用减法，用数对中较大的数减去较小的数，直到相减的差与数对中较小的数相等为止2更相减损之术的步骤：(1)判断两数是否都为偶数，若是，则都除以2直到所得两数不全为偶数(2)用较大的数减去较小的数，将差和较小的数构成一对新数，继续用较大数减去较小数，重复执行(3)当差和较小数相等时，结束执行，此时差(或较小数)为不全为偶数的两数的最大公约数用“等值值算法”(更相减损损之术术)求下列两数的最大公约约数(1)98，280；(2)72，168.【解】 (1)(98，280)(98，182)(98，8
8、4)(14，84)(14，70)(14，56)(14，42)(14，28)(14，14)最大公约数为14.(2)(72，168)(72，96)(72，24)(48，24)(24，24)最大公约数为24.例2. 用秦九韶算法计计算多项项式f(x)x612x560x4160x3240x2192x64当x2时时的值值【分析】【解析】 将f(x)改写为f(x)(x12)x60)x160)x240)x192)x64，由内向外依次计算一次多项式当x2时的值v01，v1121210，v21026040，v340216080，v480224080，v580219232，v6322640.f(2)0，即x2时，
9、原多项式的值为0.1用秦九韶算法计算多项式的值时，要正确将多项式的形式进行改写，然后由内向外依次计算当多项式函数中间出现空项式，要以系数为零的齐次项补充2秦九韶算法的步骤：【变式训练】利用秦九韶算法计算多项式 f(x)115x3x27x3 在x 23 的值时，不会用到下列哪个值()DA.161B.3772C.86 641D.85 169解析：f(x)115x3x27x3(7x3)x5x 11.所以当x23时，v07；v172331613164；v2164235377253767；v33767231186 6411186 652.例3. 求324，243，270三数的最大公约约数【分析】 先求3
10、24和243的最大公约数，再求这个数与270的最大公约数【解析】 (324，243)(243，81)(162，81)(81，81)则324与243的最大公约数为81.又(270，81)(189，81)(108，81)(81，27)(54，27)(27，27)则270与81的最大公约数为27，故324，243，270三数的最大公约数为27.求三个数的最大公约数，可先求两个数的最大公约数a，再求a与第三个数的最大公约数b，则b为所求的三个数的最大公约数该题的解法可推广到求n个数的最大公约数用更相减损损之术术求27 090，21 672，8 127的最大公约约数【解】 先求27 090与21 672
11、的最大公约数(27 090，21 672)(21 672，5 418)(16 254，5 418)(10 836，5 418)(5 418，5 418)27 090与21 672的最大公约数是5 418.再求5 418与8 127的最大公约数(8 127，5 418)(2 709，5 418)(2 709，2 709)5 418与8 127的最大公约数为2 709.27 090，21 672，8 172的最大公约数为2 709.类型 4 进制数之间的转化例 4.(1)将 101 111 011(2)转化为十进制数；(2)将 1231(5)转化为七进制数.【分析】k进制数anan1a2a1a0(
12、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.填空：248130(1)11 111 000(2)_(10)；(2)154(6)_(7).名称辗转相除法更相减损术区别以除法为主两个整数的差较大时，运算次数减少余数为 0 时结束以减
13、法为主两个整数的差较大时，运算次数多两数相等时结束联系都是求最大公约数的方法 都用到递推方法都用循环结构来实现1.辗转相除法与更相减损术求最大公约数的区别与联系.2.秦九韶算法的优点.(1)减少乘法运算的次数.(2)规律性强，便于利用循环语句实现.(3)不用对 x 做幂的运算，每次都是计算一个一次多项式的值，提高了计算精度.3.进位制对于任何一个数，我们可以用不同的进位制来表示.比如：十进数 57，可以用二进制表示为 111 001，也可以用八进制表示为 71，用十六进制表示为 39，它们所代表的数值都是一样的.表示各种进制数时，一般要在数字右下角加注来表示.如111 001(2)表示二进制数
14、，34(5)表示五进制数.电子计算机一般都使用二进制.1用更相减损损之术术可求得78与36的最大公约约数是( )A24 B18 C12 D6【解析】 783642，42366，36630，30624，24618，18612，1266，6为78与36的最大公约数【答案】 D2用秦九韶算法计计算f(x)6x54x4x32x2x32x29x，需要加法(或减法)与乘法运算的次数分别为别为 ( )A5，4 B5，5 C4，4 D4，5【解析】 n次多项式当最高次项的系数不为1时，需进行n次乘法；若各项均不为零，则需进行n次加法，缺一项就减少一次加法运算f(x)中无常数项，故加法次数要减少一次，为514.【答案】 D3用更相减损损之术术求81与135的最大公约约数时时，要进进行_次减法运算【解析】 1358154，815427，542727，共进行了3次减法运算
