辗转相除法与更相减损术秦九韶算法

1、辗转相除法与更相减损术、秦九韶算法【问题导思】136与60的最大公约数是多少？你是如何得到的？【提示】先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数由于，故36与60的最大公约数为2×2×312.2观察下列等式8 2516 105×12 146，那么8 251与6 105这两个数的公约数和6 105与2 146的公约数有什么关系？【提示】8 251的最大约数是2 146的约数，同样6 105与2 146的公约数也是8 251的约数，故8 251与6 105的最大公约数也是6 105与2 146的最大公约数辗转相

2、除法的算法步骤第一步，给定两个正整数m、n.第二步，计算m除以n所得的余数r.第三步，mn，nr.第四步，若r0，则m、n的最大公约数等于m，否则返回第二步.更相减损术【问题导思】设两个正整数m>n(m>n)，若mnk，则m与n的最大公约数和n与k的最大公约数相等，反复利用这个原理，可求得98与63的最大公约数是多少？【提示】986335,633528,35287,28721,21714,1477，98与63的最大公约数为7.更相减损术的算法步骤第一步，任意给定两个正整数，判断它们是否都是偶数若是，用2约简；若不是，执行第二步第二步，以较大的数减去较小的数，接着把所得的差与较小的数

3、比较，并以大数减小数继续这个操作，直到所得的差与减数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.秦九韶算法将f(x)改写成如下形式：f(x)(anxan1)xan2)xa1)xa0.具体算法如下：(1)计算最内层括号内一次多项式的值，即v1anxan1.(2)由内向外逐层计算多项式的值，即v2v1xan2，v3v2xan3，vnvn1xa0. 用辗转相除法求最大公约数用辗转相除法求228与1 995的最大公约数【思路探究】使用辗转相除法可根据mnqr，反复相除直到r0为止【自主解答】1 9958×228171，2281×17157，1713

4、15;57，228与1 995的最大公约数为57.利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数用辗转相除法求779和209的最大公约数【解】779209×3152，209152×157，15257×238，5738×119，3819×2，779与209的最大公约数为19.用更相减损术求最大公约数(2013·福州高一检测)用更相减损术求154,484的最大公约数【思路探究】

5、解答本题可先将两数约简然后按更相减损术的步骤反复相减直至得出结果【自主解答】154÷277,484÷2242，下面用更相减损术，求77与242的最大公约数24277165,1657788,887711,771166,661155,551144,441133,331122,221111，故77与242的最大公约数为11，则154与484的最大公约数为11×222.更相减损术的步骤：1判断两数是否为偶数，若是，则都除以2直到所得的两数不全为偶数；2用较大的数减去较小的数，将差和较小的数构成一对新数继续用较大的数减去较小数，重复执行；3当差和较小数相等时，结束执行，此时

6、差(或较小数)为不全为偶数的两数的最大公约数注意：原先两数的最大公约数是两式相减所得公约数与约简的因数的乘积用更相减损术求576与246的最大公约数【解】用2约简576和246得288与123.288123165,16512342，1234281,814239，42393,39336,36333，33330,30327，27324,24321，21318,18315，15312,1239，936,633.576与246的最大公约数为3×26.秦九韶算法的应用用秦九韶算法求多项式f(x)7x76x64x43x32x2x5，当x3时的值【思路探究】解答本题首先要将原多项式化成f(x)(7

7、x6)x0)x4)x3)x2)x1)x5的形式其次再弄清v0，v1，v2，v7分别是多少，最后进行计算【自主解答】f(x)(7x6)x0)x4)x3)x2)x1)x5，v07，v17×3615；v215×3045；v345×34139；v4139×33420；v5420×321 258；v61 258×313 775；v73 775×3511 320.当x3时，多项式的值为11 320.秦九韶算法的步骤：用秦九韶算法计算多项式f(x)x612x560x4160x3240x2192x64，当x2时的值【解】将f(x)改写为f(

8、x)(x12)x60)x160)x240)x192)x64，由内向外依次计算一次多项式当x2时的值，v01，v11×21210，v210×26040，v340×216080，v480×224080，v580×219232，v632×2640.f(2)0，即x2时，原多项式的值为0.(见学生用书第24页)对秦九韶算法中的运算次数理解错误已知f(x)x52x43x34x25x6，用秦九韶算法求这个多项式当x2时的值时，做了几次乘法？几次加法？【错解】根据秦九韶算法，把多项式改写成如下形式f(x)(x2)x3)x4)x5)x6.按照从内到外

9、的顺序，依次计算一次多项式当x2时的值：v1224；v22v1311；v32v2426；v42v3557；v52v46120.显然，在v1中未做乘法，只做了1次加法；在v2，v3，v4，v5中各做了1次加法，1次乘法因此，共做了4次乘法，5次加法【错因分析】在v1中虽然“v1224”，而计算机还是做了1次乘法“v12×124”因为用秦九韶算法计算多项式f(x)anxnan1xn1a1xa0当xx0时的值时，首先将多项式改写成f(x)(anxan1)xa1)xa0，然后再计算v1anxan1，v2v1xan2，v3v2xan3，vnvn1xa0.无论an是不是1，这次的乘法都是要进行的

10、【防范措施】1.将多项式写成一次多项式的形式时，如果多项式中n次项不存在，可将n次项看作0·xn.2直接法乘法运算的次数最多可达，加法最多n次，秦九韶算法通过转化把乘法运算的次数减少到最多n次，加法最多n次【正解】由以上分析，共做了5次乘法，5次加法1辗转相除法与更相减损术都是求两数最大公约数的方法辗转相除法计算次数少，步骤简捷，更相减损术计算次数多，步骤复杂，但是更相减损术每一步的计算都是减法，比做除法运算要简单一些，一般当数较小时可以考虑用更相减损术，当数较大时可以考虑用辗转相除法2用秦九韶算法可大大降低乘法的运算次数，提高了运算速度用此方法求值，关键是正确地将所给多项式改写，然

11、后由内向外计算，由于后项计算需用到前项结果，故应认真、细心，确保结果的准确性(见学生用书第24页)1490和910的最大公约数为()A2B10C30D70【解析】910490×1420,490420×170,42070×6，故最大公约数为70.【答案】D2用更相减损术求294和84的最大公约数为()A21 B42 C32 D16【解析】294÷2147,84÷242,14742105,1054263,634221,422121,21×242，所以最大公约数为42.【答案】B3用秦九韶算法求f(x)2x3x3当x3时的值v2_.【解析】

12、f(x)(2x0)x1)x3，v02；v12×306；v26×3119.【答案】194用更相减损术求288与153的最大公约数【解】288153135,15313518,13518117,1171899,991881,811863,631845,451827,27189,1899.288与153的最大公约数为9.(见学生用书第93页)一、选择题1用“辗转相除法”求得360和504的最大公约数是()A72B36C24D2 520【解析】504360×1144,360144×272,14472×2，360和504的最大公约数是72，故选A.【答案】

13、A2设计程序框图，用秦九韶算法求多项式的值，主要用哪种结构实现()A顺序结构 B条件结构C循环结构 D条件、顺序结构【解析】该种算法主要是由内到外计算故在求值时用到循环结构【答案】C3(2013·德州高一检测)用秦九韶算法求多项式f(x)4x5x22当x3时的值时，需要进行的乘法运算和加法运算的次数分别为()A4,2 B5,3 C5,2 D6,2【解析】f(x)4x5x22(4x)x)x1)x)x2，需5次乘法运算和2次加法运算【答案】C4225与135的最大公约数是()A5 B9 C15 D45【解析】225135×190,13590×145,9045×

14、;2，45是225与135的最大公约数【答案】D5已知f(x)x52x33x2x1，应用秦九韶算法计算x3时的值时，v3的值为()A27 B11 C109 D36【解析】f(x)(x0)x2)x3)x1)x1当x3时，v01，v13，v23×3211，v311×3336.【答案】D二、填空题6464与272的最大公约数为_【解析】464÷1629,272÷1617,291712,17125,1257,752,523,321,211，最大公约数为1×1616.【答案】167用更相减损术求152与92的最大公约数时，需要做减法的次数是_【解析】15

15、2与92都是偶数，先两次用2约简得38与23，又382315，23158，1587，871，716，615，514，413，312，211，故要用10次减法【答案】108已知多项式函数f(x)2x55x44x33x26x7，当x5时由秦九韶算法v02，v12×555，则v3_.【解析】v2v1x45×5421，v3v2x321×53108.【答案】108三、解答题9用秦九韶算法求多项式f(x)x65x56x4x20.3x2，当x2时的值【解】f(x)x65x56x4x20.3x2(x5)x6)x0)x1)x0.3)x2.当x2时v01，v11×(2)57

16、，v27×(2)620，v320×(2)040，v440×(2)181，v581×(2)0.3161.7，v6161.7×(2)2325.4，f(2)325.4.10求三个数324,243,135的最大公约数【解】法一324243×181，24381×3.324与243的最大公约数为81.又13581×154，8154×127，5427×2.则81与135的最大公约数为27.三个数324,243,135的最大公约数为27.法二32424381,24381162,1628181.324与243的最大公约数为81.1358154,815427,542727.81与135的最大公约数为27.324,243,135的最大公约数是27.11求1 356和2 400的最小公倍数【解】2 4001×1 3561 044,1 3561×1 044312，1 0443×312108,3122×10896，1081×9612,9612×8，1 356和2 400的最大公约数为12.1 356和2 400的最小公倍