算法案例-辗转相除法与更相减损术秦九韶算法与进位制件数学高一必修3算法初步13人教A版.pptx

1.理解辗转相除法与更相减损术求最大公约数的方法理解辗转相除法与更相减损术求最大公约数的方法.2.理解秦九韶算法中求多项式的值的步骤原理理解秦九韶算法中求多项式的值的步骤原理.3.能利用除能利用除 k 取余法把十进制数化为取余法把十进制数化为 k 进制数进制数.1.辗转相除法的算法步骤第一步，给定两个正整数 m，n(mn).第二步，计算_除以_所得的_数 r.第三步，mn，nr.第四步，若 r0，则 m，n 的最大公约数等于_；否则，返回第二步.mn余n2.更相减损术的算法步骤第一步，任意给定两个正整数，判断它们是否都是偶数.若是用 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)转化为十进制数为_.(2)把十进制数化为 k 进制数用“_”，即把所给的十进制数除以_，得到商数和余数，再用商数除以 k，得到商数和余数，直到商数为_，把上面各步所得的_从右到左排列，即得到 k 进制数.除 k 取余法k0余数anknan1kn1a1ka0【问题导思问题导思】1如何求如何求18与与54的最大公约数？的最大公约数？【提示提示】短除法短除法2要求要求6 750与与3 492的最大公约数，上述法还好用吗？的最大公约数，上述法还好用吗？【提示提示】数值太大，短除法不方便用数值太大，短除法不方便用知识知识1 求两个正整数最大公约数的算法求两个正整数最大公约数的算法(1)更相减损之术更相减损之术(等值算法等值算法)用两个数中较大的数减去较小的数，再用用两个数中较大的数减去较小的数，再用和和构成新的一对数，对这一对数再用构成新的一对数，对这一对数再用减减，以同样的操作一直做下去，直，以同样的操作一直做下去，直到产生到产生，这个数就是最大公约数，这个数就是最大公约数(2)辗转相除法辗转相除法(欧几里得算法欧几里得算法)用较大的数除以较小的数所得的用较大的数除以较小的数所得的和和_构成新的一对数，继续做上面的除法，直到构成新的一对数，继续做上面的除法，直到，这个较小的数就是最大公约数，这个较小的数就是最大公约数.差数差数较小的数较小的数大数大数小数小数一对相等的数一对相等的数余数余数较小的数较小的数大数被小数除尽大数被小数除尽【问题导思问题导思】1怎样计算多项式怎样计算多项式f(x)x5x4x3x2x1当当x5时时的值呢？统计所做的计算的种类及计算次数分别是什么？的值呢？统计所做的计算的种类及计算次数分别是什么？【提示提示】f(5)55545352513 906.根据我根据我们的计算统计可以得出我们共需要们的计算统计可以得出我们共需要10次乘法运算，次乘法运算，5次加法运次加法运算算知识知识2 秦九韶算法秦九韶算法2我们把多项式变形为我们把多项式变形为f(x)x2(1x(1x(1x)x1，再统计一下计算当，再统计一下计算当x5时的计算的种类及计算次数分别是时的计算的种类及计算次数分别是什么？什么？【提示提示】从里往外计算仅需从里往外计算仅需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，即称为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)(29，29)所以所以319与与261的最大公约数是的最大公约数是29.1利用利用“等值算法等值算法”求给定的两个数的最大公约数，即求给定的两个数的最大公约数，即多次利用减法，用数对中较大的数减去较小的数，直到相减多次利用减法，用数对中较大的数减去较小的数，直到相减的差与数对中较小的数相等为止的差与数对中较小的数相等为止2更相减损之术的步骤：更相减损之术的步骤：(1)判断两数是否都为偶数，若是，则都除以判断两数是否都为偶数，若是，则都除以2直到所得直到所得两数不全为偶数两数不全为偶数(2)用较大的数减去较小的数，将差和较小的数构成一对用较大的数减去较小的数，将差和较小的数构成一对新数，继续用较大数减去较小数，重复执行新数，继续用较大数减去较小数，重复执行(3)当差和较小数相等时，结束执行，此时差当差和较小数相等时，结束执行，此时差(或较小数或较小数)为不全为偶数的两数的最大公约数为不全为偶数的两数的最大公约数用用“等值算法等值算法”(更相减损之术更相减损之术)求下列两数的最大公约求下列两数的最大公约数数(1)98，280；(2)72，168.【解解】(1)(98，280)(98，182)(98，84)(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)x612x560 x4160 x3240 x2192x64当当x2时的值时的值【分析分析】【解析解析】将将f(x)改写为改写为f(x)(x12)x60)x160)x240)x192)x64，由内向外依次计算一次多项式当由内向外依次计算一次多项式当x2时的值时的值v01，v1121210，v21026040，v340216080，v480224080，v580219232，v6322640.f(2)0，即，即x2时，原多项式的值为时，原多项式的值为0.1用秦九韶算法计算多项式的值时，要正确将多项式的用秦九韶算法计算多项式的值时，要正确将多项式的形式进行改写，然后由内向外依次计算当多项式函数中间形式进行改写，然后由内向外依次计算当多项式函数中间出现空项式，要以系数为零的齐次项补充出现空项式，要以系数为零的齐次项补充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.求求324，243，270三数的最大公约数三数的最大公约数【分析分析】先求先求324和和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的最大公约数的最大公约数(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(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).名称名称辗转相除法辗转相除法更相减损术更相减损术区别区别以除法为主以除法为主两个整数的差较大两个整数的差较大时，运算次数减少时，运算次数减少余数为余数为 0 时结束时结束以减法为主以减法为主两个整数的差较大时，两个整数的差较大时，运算次数多运算次数多两数相等时结束两数相等时结束联系联系都是求最大公约数的方法都是求最大公约数的方法 都用到递推方法都用到递推方法都用循环结构来实现都用循环结构来实现1.辗转相除法与更相减损术求最大公约数的区别与联系.2.秦九韶算法的优点.(1)减少乘法运算的次数.(2)规律性强，便于利用循环语句实现.(3)不用对 x 做幂的运算，每次都是计算一个一次多项式的值，提高了计算精度.3.进位制进位制 对于任何一个数，我们可以用不同的进位制来表示.比如：十进数 57，可以用二进制表示为 111 001，也可以用八进制表示为 71，用十六进制表示为 39，它们所代表的数值都是一样的.表示各种进制数时，一般要在数字右下角加注来表示.如111 001(2)表示二进制数，34(5)表示五进制数.电子计算机一般都使用二进制.1用更相减损之术可求得用更相减损之术可求得78与与36的最大公约数是的最大公约数是()A24B18C12D6【解析解析】783642，42366，36630，30624，24618，18612，1266，6为为78与与36的的最大公约数最大公约数【答案答案】D2用秦九韶算法计算用秦九韶算法计算f(x)6x54x4x32x2x32x29x，需要加法，需要加法(或减法或减法)与乘法运算的次数分别为与乘法运算的次数分别为()A5，4B5，5C4，4D4，5【解析解析】n次多项式当最高次项的系数不为次多项式当最高次项的系数不为1时，需进时，需进行行n次乘法；若各项均不为零，则需进行次乘法；若各项均不为零，则需进行n次加法，缺一项就次加法，缺一项就减少一次加法运算减少一次加法运算f(x)中无常数项，故加法次数要减少一次，中无常数项，故加法次数要减少一次，为为514.【答案答案】D3用更相减损之术求用更相减损之术求81与与135的最大公约数时，要进行的最大公约数时，要进行_次减法运算次减法运算【解析解析】1358154，815427，542727，共进行了共进行了3次减法运算次减法运算【答案答案】34.将二进制数将二进制数101 101(2)化为八进制数，结果为化为八进制数，结果为_【解析解析】101 101(2)1250241231220213284145.101 101(2)55(8)【答案答案】55(8)5求当求当x2时，时，f(x)x55x4x31的函数值的函数值【解解】f(x)x55x4x31(x5)x1)x0)x0)x1，利用公式有，利用公式有v01，v11253，v2(3)215，v3(5)2010，v4(10)2020，v5(20)2141，f(2)41.