新课标A版必修3导学案 1.3.1 辗转相除法、更相减损术及秦九昭算法

第1课时辗转相除法与更相减损术、秦九韶算法1．理解辗转相除法与更相减损术的含义，了解其执行过程．2．理解秦九韶算法的计算过程，并了解它提高计算效率的实质．1．辗转相除法与更相减损术(1)辗转相除法①辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．②辗转相除法的算法步骤第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，m＝n，n＝r.第四步，若r＝0，则m，n的最大公约数等于m；否则，返回第二步．(2)更相减损术的算法步骤第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．(3)辗转相除法和更相减损术的区别与联系(1)秦九韶算法简介①秦九韶算法要解决的问题是求多项式的值．②秦九韶算法的特点通过一次式的反复计算，逐步得到高次多项式的值，即将一个n次多项式的求值问题归结为重复计算n个一次多项式的值的问题．③秦九韶算法的原理将f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0改写为：f(x)＝(a n x n－1＋a n－1x n－2＋…＋a1)x＋a0＝((a n x n－2＋a n－1x n－3＋…＋a2)x＋a1)x＋a0＝…先计算最内层括号内一次多项式的值，即v1＝a n x＋a n－1，再由内向外逐层计算一次多项式v k的值．(2)秦九韶算法的操作方法①算法步骤如下第一步，输入多项式次数n、最高次项的系数a n和x的值．第二步，将v的值初始化为a n，将i的值初始化为n－1.第三步，输入i次项的系数a i.第四步，v＝vx＋a i，i＝i－1.第五步，判断i是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v.②程序框图如图所示③程序如下INPUT “n＝”；nINPUT “an＝”；aINPUT “x＝”；xv＝ai＝n－1WHILE i＞＝0INPUT “ai＝”；av＝v*x＋ai＝i－1WENDPRINT vEND1．实际应用更相减损术时要做的第一步工作是什么？[提示] 先判断a，b是否为偶数，若是，都除以2再进行．2．判断正误．(正确的打“√”，错误的打“×”)(1)辗转相除法的基本步骤是用较大的数除以较小的数．( )(2)求最大公约数的方法除辗转相除法之外，没有其他方法．( )(3)编写辗转相除法的程序时，要用到循环语句．( )[提示] (1)√(2)×(3)√题型一辗转相除法和更相减损术的应用【典例1】用辗转相除法求612与468的最大公约数，并用更相减损术检验所得结果．[思路导引] 将612作为大数，468作为小数，执行辗转相除法和更相减损术的步骤即可.[解] 用辗转相除法：612＝468×1＋144,468＝144×3＋36,144＝36×4，即612和468的最大公约数是36.用更相减损术检验：612和468为偶数，两次用2约简得153和117,153－117＝36,117－36＝81,81－36＝45,45－36＝9,36－9＝27,27－9＝18,18－9＝9，所以612和468的最大公约数为9×2×2＝36.求最大公约数的两种方法步骤(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数．若是，用2约简，也可以不除以2，直接求最大公约数，这样不影响最后结果．[针对训练1] 用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果．[解] 80＝36×2＋8，36＝8×4＋4,8＝4×2＋0，即80与36的最大公约数是4.验证：80÷2＝40,36÷2＝18；40÷2＝20,18÷2＝9；20－9＝11,11－9＝2；9－2＝7,7－2＝5；5－2＝3,3－2＝1；2－1＝1,1×2×2＝4；所以80与36的最大公约数为4.题型二求三个正整数的最大公约数【典例2】求325,130,270三个数的最大公约数[思路导引] 求三个数的最大公约数，可先求两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数．[解] 解法一(辗转相除法)：因为325＝130×2＋65,130＝65×2，所以325和130的最大公约数为65.因为270＝65×4＋10,65＝10×6＋5,10＝5×2,所以65和270的最大公约数为5,故325,130,270三个数的最大公约数为5.解法二(更相减损术)：325－130＝195,195－130＝65,130－65＝65.所以325和130的最大公约数是65.270－65＝205,205－65＝140,140－65＝75,75－65＝10,65－10＝55,55－10＝45,45－10＝35,35－10＝25,25－10＝15,15－10＝5,10－5＝5.所以65和270的最大公约数为5，故325,130,270三个数的最大公约数为5.理解辗转相除法的实质，从计算结果上看，辗转相除法是以相除余数为零而得到结果的.[针对训练2] 求三个数175,100,75的最大公约数.[解] 先求175与100的最大公约数：175＝100×1＋75,100＝75×1＋25,75＝25×3,∴175与100的最大公约数是25.再求25与75的最大公约数：75－25＝50,50－25＝25,∴75和25的最大公约数是25.∴175,100,75的最大公约数是25.题型三秦九韶算法【典例3】已知一个5次多项式为f(x)＝4x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8，用秦九韶算法求这个多项式当x＝5时的值.[思路导引] 可根据秦九韶算法的原理，将所给的多项式改写，然后由内到外逐次计算．[解] 将f(x)改写为f(x)＝((((4x＋2)x＋3.5)x－2.6)x＋1.7)x－0.8，由内向外依次计算一次多项式，当x＝5时的值：v0＝4；v 1＝4×5＋2＝22； v 2＝22×5＋3.5＝113.5； v 3＝113.5×5－2.6＝564.9； v 4＝564.9×5＋1.7＝2826.2； v 5＝2826.2×5－0.8＝14130.2.所以当x ＝5时，多项式的值等于14130.2.(1)用秦九韶算法求多项式f (x )当x ＝x 0的值的思路为： ①改写．②计算⎩⎪⎨⎪⎧v 0＝a n ，v k ＝v k －1x 0＋a n －k (k ＝1，2，…，n ).③结论f (x 0)＝v n .(2)应用秦九韶算法计算多项式的值应注意的3个问题 ①要正确将多项式的形式进行改写． ②计算应由内向外依次计算．③当多项式函数中间出现空项时，要以系数为零的齐次项补充．[针对训练3] 用秦九韶算法计算多项式f (x )＝12＋35x －8x 2＋6x 4＋5x 5＋3x 6在x ＝－4时的值时，v 3的值为( )A ．－144B ．－136C ．－57D ．34[解析] 根据秦九韶算法多项式可化为f (x )＝(((((3x ＋5)x ＋6)x ＋0)x －8)x ＋35)x ＋12.由内向外计算v 0＝3；v 1＝3×(－4)＋5＝－7； v 2＝－7×(－4)＋6＝34； v 3＝34×(－4)＋0＝－136.[答案] B课堂归纳小结1.求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术．用辗转相除法，即根据a＝nb＋r这个式子，反复相除，直到r＝0为止；用更相减损术，即根据r＝|a－b|这个式子，反复相减，直到r＝0为止．2.秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行．1．辗转相除法可解决的问题是( )A．求两个正整数的最大公约数B．多项式求值C．求两个正整数的最小公倍数D．排序问题[解析] 辗转相除法可以求两个正整数的最大公约数.[答案] A2．用辗转相除法求72与120的最大公约数时，需要做除法次数为( )A．4 B．3C．5 D．6[解析] 120＝72×1＋48,72＝48×1＋24,48＝24×2.[答案] B3．用更相减损术求36与134的最大公约数，第一步应为________．[解析] ∵36与134都是偶数，∴第一步应先除以2，得到18与67.[答案] 先分别除以2，得到18与674．用秦九韶算法求f(x)＝2x3＋x－3当x＝3时的值v2＝________.[解析] f(x)＝((2x＋0)x＋1)x－3，v0＝2，v1＝2×3＋0＝6，v2＝6×3＋1＝19.[答案] 195．用秦九韶算法求多项式f(x)＝8x7＋5x6＋3x4＋2x＋1，当x＝2时的值．[解] 根据秦九韶算法，把多项式改写成如下形式：f(x)＝8x7＋5x6＋0·x5＋3·x4＋0·x3＋0·x2＋2x＋1＝((((((8x＋5)x＋0)x＋3)x＋0)x＋0)x＋2)x＋1.而x＝2，所以有v0＝8，v1＝8×2＋5＝21，v2＝21×2＋0＝42，v3＝42×2＋3＝87，v4＝87×2＋0＝174，v5＝174×2＋0＝348，v6＝348×2＋2＝698，v7＝698×2＋1＝1397.所以当x＝2时，多项式的值为1397.算法案例在实际生活中的应用通过算法案例的学习，知道算法的核心是一般意义上的解决问题的策略的具体化．对于一个实际问题，我们在分析、思考后可将之转化为数学问题，从而获得解决它的基本思路.【典例】现有长度为2.4 m和5.6 m两种规格的钢筋若干，要焊接一批棱上无接点的正方体模型，问怎样设计才能保证正方体的体积最大且不浪费材料？[思路导引] 要焊接正方体，就是将两种规格的钢筋截成长度相等的钢筋条．为了保证不浪费材料，应使得每种规格的钢筋截取后没有剩余，因此截取的长度应为2.4与5.6的公约数；为使得正方体的体积最大，因此截取的长度应为2.4与5.6的最大公约数.[解] 用更相减损术来求2.4与5.6的最大公约数：5．6－2.4＝3.2,3．2－2.4＝0.8,2．4－0.8＝1.6,1．6－0.8＝0.8,因此2.4与5.6的最大公约数为0.8.所以使得正方体的棱长为0.8 m时，正方体的体积最大且不浪费材料.[针对训练] 甲，乙，丙三种溶液的质量分别为147 g，343 g，133 g，现要将它们分别全部装入小瓶中，每个小瓶中装入溶液的质量相同，问每瓶最多装多少？[解] 由题意，每个小瓶中装入的溶液的质量应是三种溶液质量的最大公约数．先求147与343的最大公约数：343－147＝196,196－147＝49,147－49＝98,98－49＝49，所以147与343的最大公约数是49.再求49与133的最大公约数：133－49＝84,84－49＝35,49－35＝14,35－14＝21,21－14＝7,14－7＝7，所以147,343,133的最大公约数为7，即每瓶最多装7 g.课后作业(八)(时间45分钟)学业水平合格练(时间25分钟)1．秦九韶算法与直接计算相比较，下列说法错误的是( )A．秦九韶算法与直接计算相比，大大节省了做乘法的次数，使计算量减少，并且逻辑结构简单B．秦九韶算法减少了做乘法的次数，在计算机上也就加快了计算的速度C．秦九韶算法减少了做乘法的次数，在计算机上也就降低了计算的速度D．秦九韶算法避免了对自变量x单独做幂的计算，而且与系数一起逐次增长幂次，从而提高计算的精度[解析] 秦九韶算法减少了做乘法的次数，在计算机上也就加快了计算的速度，故选项C错误．[答案] C2．下列说法中正确的个数为( )①辗转相除法也叫欧几里得算法；②辗转相除法的基本步骤是用较大的数除以较小的数；③求最大公约数的方法，除辗转相除法之外，没有其他方法；④编写辗转相除法的程序时，要用到循环语句．A．1 B．2C．3 D．4[解析] ①、②、④正确，③错误．[答案] C3．利用秦九韶算法求f(x)＝1＋2x＋3x2＋…＋6x5当x＝2时的值时，下列说法正确的是( )A．先求1＋2×2B．先求6×2＋5，第二步求2×(6×2＋5)＋4C．f(2)＝1＋2×2＋3×22＋4×23＋5×24＋6×25直接运算求解D．以上都不对[解析] 利用秦九韶算法应先算a n x＋a n－1，再算(a n x＋a n－1)x＋a n－2，故选B.[答案] B4．中国古代有计算多项式值的秦九韶算法，下图是实现该算法的程序框图．执行该程序框图，若输入的x＝2，n＝2，依次输入的a为2,2,5，则输出的s＝( )A．7 B．12C．17 D．34[解析] 该题考查程序框图的运行及考生的识图能力．由程序框图知，第一次循环：x＝2，n＝2，a＝2，s＝0×2＋2＝2，k＝1；第二次循环：a＝2，s＝2×2＋2＝6，k＝2；第三次循环：a＝5，s＝6×2＋5＝17，k＝3.结束循环，输出s的值为17，故选C.[答案] C5．用更相减损术求117和182的最大公约数时，需做减法的次数是( )A．8 B．7C．6 D．5[解析] ∵182－117＝65,117－65＝52,65－52＝13,52－13＝39,39－13＝26,26－13＝13，∴13是117和182的最大公约数，需做减法的次数是6.[答案] C6．用秦九韶算法求n次多项式f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0当x＝x0时的值，求f(x0)需要乘方、乘法、加法的次数分别为( )A.n(n＋1)2，n，n B．n,2n，nC．0,2n，n D．0，n，n[解析] 因为f(x)＝(…((a n x＋a n－1)x＋a n－2)x＋…＋a1)x＋a0，所以乘方、乘法、加法的次数分别为0，n，n.[答案] D7．用秦九韶算法求多项式f(x)＝12＋35x－8x2＋79x3＋6x4＋5x5＋3x6当x＝－4的值时，其中v1的值为________．[解析] ∵f(x)＝12＋35x－8x2＋79x3＋6x4＋5x5＋3x6，∴v0＝a6＝3，v1＝v0x＋a5＝3×(－4)＋5＝－7.[答案] －78．378和90的最大公约数为________．[解析] 378＝90×4＋18,90＝18×5＋0，∴378与90的最大公约数是18.[答案] 189．求1356和2400的最小公倍数．[解] 2400＝1356×1＋1044，1356＝1044×1＋312，1044＝312×3＋108，312＝108×2＋96，108＝96×1＋12，96＝12×8.所以1356与2400的最大公约数为12.则1356与2400的最小公倍数为(1356×2400)÷12＝271200.10．用秦九韶算法求多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x当x＝3时的值．[解] f(x)＝((((((7x＋6)x＋5)x＋4)x＋3)x＋2)x＋1)·x，所以v0＝7，v1＝7×3＋6＝27，v2＝27×3＋5＝86，v3＝86×3＋4＝262，v4＝262×3＋3＝789，v5＝789×3＋2＝2369，v6＝2369×3＋1＝7108，v7＝7108×3＝21324.故x＝3时，多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x的值为21324.应试能力等级练(时间20分钟)11．下列哪组的最大公约数与1855,1120的最大公约数不同( )A．1120,735 B．385,350C．385,735 D．1855,325[解析] ∵(1855,1120)→(735,1120)→(735,385)→(350,385)→(350,35)，∴1855与1120的最大公约数是35，由以上计算过程可知选D.[答案] D12．用秦九韶算法计算多项式f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1，当x＝0.4时的值时，需要做乘法和加法的次数分别是( )A．6,6 B．5,6C．5,5 D．6,5[解析] 根据秦九韶算法，把多项式改写为f(x)＝(((((3x＋4)x＋5)x＋6)x＋7)x＋8)x＋1，∴需要做6次加法运算，6次乘法运算，故选A.[答案] A13．已知a＝333，b＝24，则使得a＝bq＋r(q，r均为自然数，且0≤r≤b)成立的q 和r的值分别为________．[解析] 用333除以24，商即为q，余数就是r.333÷24的商为13，余数是21.∴q＝13，r＝21.[答案] 13,2114．用秦九韶算法求多项式f(x)＝1－5x－8x2＋10x3＋6x4＋12x5＋3x6当x＝－4时的值时，v0，v1，v2，v3，v4中最大值与最小值的差是________．[解析] 多项式变形为f(x)＝3x6＋12x5＋6x4＋10x3－8x2－5x＋1＝(((((3x＋12)x＋6)x＋10)x－8)x－5)x＋1，v0＝3，v1＝3×(－4)＋12＝0，v2＝0×(－4)＋6＝6，v3＝6×(－4)＋10＝－14，v4＝－14×(－4)－8＝48，所以v4最大，v3最小，所以v4－v3＝48＋14＝62.[答案] 6215．用辗转相除法和更相减损术两种方法求三个数72,120,168的最大公约数．[解] (辗转相除法)：先求120,168的最大公约数．因为168＝120×1＋48，120＝48×2＋24,48＝24×2，所以120,168的最大公约数是24.再求72,24的最大公约数．因为72＝24×3，所以72,24的最大公约数为24，即72,120,168的最大公约数为24.(更相减损术)：先求120,168的最大公约数．168－120＝48,120－48＝72，72－48＝24,48－24＝24，所以120,168的最大公约数为24.再求72,24的最大公约数．72－24＝48,48－24＝24，所以72,24的最大公约数为24，即72,120,168的最大公约数为24.。

5.用更相减损术求294和84的最大公约数时,第一步是 【解析】由于294和84都是偶数,先用2约简. 答案:用2约简
.
一、辗转相除法与更相减损术 根据辗转相除法与更相减损术求两个正整数最大公约数的步骤,探究下列问题: 探究1:(1)用辗转相除法可以求两个正整数m,n的最大公约数,那么用什么逻辑 结构来设计算法?其算法步骤如何设计?
1.辗转相除法可解决下列问题中的 ( ) A.求两个正整数的最大公约数 B.多项式求值 C.求两个正整数的最小公倍数 D.排序问题 【解析】选A.辗转相除法可以求两个正整数的最大公约数.
2.用更相减损术可求得78与36的最大公约数是 ( ) A.24 B.18 C.12 D.6 【解析】选D.先用2约简得39,18;然后辗转相减得39-18=21, 21-18=3,18-3=15,15-3=12,12-3=9,9-3=6,6-3=3.所以所求的最大公约数为 3×2=6.
种算法由欧几里得在公元前300年左右首先提出,因而又叫
_____________. (2)算法步骤: 第一步,给定两个正整数m,n. 第二步,计算m除以n所得的余数r. 第三步,m=n,n=r. r=0 则m,n的最大公约数等于m;否则,返回第二步. 第四步,若____,
欧几里得算法
2.更相减损术
莫忘记求得的相等两数乘以约简的数才是所求最大公约数.
二、秦九韶算法 根据秦九韶算法的含义和步骤探究下列各题: 探究1:秦九韶算法的实质是什么? 提示:秦九韶算法的实质是:求多项式f(x)=anxn+an-1xn-1 +…+a1x+a0的值时,转化为求n个一次多项式的值,共进行n次乘法运算和n次加 法运算.这种算法的运算次数较少,是多项式求值比较先进的算法.

第一课时辗转相除法与更相减损术、秦九韶算法1．理解辗转相除法与更相减损术的含义，了解其执行过程，并会求最大公约数．2．掌握秦九韶算法的计算过程，了解它提高计算效率的实质，并会求多项式的值．3．进一步体会算法的基本思想．1．辗转相除法与更相减损术(1)辗转相除法．①算法步骤：第一步，给定两个正整数，n第二步，计算除以n所得的余数r第三步，＝n，n＝r第四步，若r＝，则，n的最大公约数等于；否则返回第步．②程序框图如图所示．③程序：INPUT ，nDOr＝ MOD n＝nn＝rLOOP UNTILPRINTEND(2)更相减损术．[。

]算法分析：第一步，任意给定两个正整数，判断它们是否都是．若是，用约简；若不是，执行第二步．第二步，以较大的数去较小的数，接着把所得的差与较小的数比较，并以数减数．继续这个操作，直到所得的差与减数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．【做一做1】用更相减损术求294和84的最大公约数时，第一步是．2．秦九韶算法(1)概念：求多项式f()＝a n n＋a n－1n－1＋…＋a1＋a0的值时，常用秦九韶算法，这种算法的运算次数较少，是多项式求值比较先进的算法，其实质是转化为求n个多项式的值，共进行次乘法运算和次加法运算．其过程是：改写多项式为：f()＝a n n＋a n－1n－1＋…＋a1＋a0＝(a n n－1＋a n－1n－2＋…＋a1)＋a0＝((a n n－2＋a n－1n－3＋…＋a2)＋a1)＋a0＝…＝(…((a n＋a n－1)＋a n－2)＋…＋a1)＋a0设v1＝，v2＝v1＋a n－2，v3＝v2＋a n－3，…，v n＝(2)算法步骤：第一步，输入多项式的次数n、最高次项的系数a n和的值．第二步，将v的值初始化为a n，将i的值初始化为n－1第三步，输入i次项的系数a i第四步，v＝v＋a i，i＝第五步，判断i是否大于或等于．若是，则返回第三步；否则，输出多项式的值．(3)程序框图如图所示．(4)程序：INPUT “n＝”；nINPUT “an＝”；aINPUT “＝”；v＝ai＝n－1[]WHILEPRINT “i＝”；iINPUT “ai＝”；av＝i＝i－1WENDPRINT END【做一做2】 设计程序框图，用秦九韶算法求多项式的值，所选用的结构是( )A ．顺序结构B ．条件结构 ．循环结构 D ．以上都有答案：1．(1)①0 二 ③r ＝0 (2)偶数 2 减 大 小 【做一做1】 用2约简 由于294和84都是偶数，先用2约简． 2．(1)一次 n n a n ＋a n －1 v n －1＋a 0 (2)i －1 0 v (4)i ＞＝0 v ＋a v【做一做2】D1．更相减损术与辗转相除法的区别与联系 剖析：如表所示．②二者的实质都是递归的过程．2．秦九韶算法是比较先进的算法剖析：计算机的最重要特点就是运算速度快2003年2月26日，以色列家宣布研制出一台依靠DNA 运行、速度达每秒运算330万亿次的生物计算机．这种计算机的运算速度比现在普通计算机的运算速度要快10万倍，但是即便如此，计算机也不是万能的．同一个问题有多种算法，如果某个算法比其他算法的步骤少，运算的次数少，那么这个算法就是比较先进的算法．算法好坏的一个重要标志就是运算的次数越少越好．求多项式f ()＝a n n ＋a n －1n －1＋…＋a 1＋a 0的值时，通常是先计算a n n ，进行n 次乘法运算；再计算a n －1n －1，进行n －1次乘法运算；这样继续下去共进行n ＋n －1＋…＋2＋1＝n n ＋12(其计算方法以后习)次乘法运算，还需要进行n 次加法运算，总共进行n n ＋12＋n次运算．但是用秦九韶算法时，改写多项式为f ()＝a n n ＋a n －1n －1＋…＋a 1＋a 0＝(a n n －1＋a n －1n －2＋…＋a 1)＋a 0[] ＝((a n n －2＋a n －1n －3＋…＋a 2)＋a 1)＋a 0 …＝(…((a n＋a n－1)＋…＋a2)＋a1)＋a0先计算v1＝a n＋a n－1，需1次乘法运算，1次加法运算；v2＝v1＋a n－2，需1次乘法运算，1次加法运算；…v n＝v n－1＋a0，需1次乘法运算，1次加法运算．所以需进行n次乘法运算，n次加法运算，共进行2n次运算．由于错误!－2n＝错误!≥0，则错误!＋n≥2n因此说秦九韶算法与其他算法相比运算次数少，秦九韶算法是比较先进的算法．题型一求最大公约数【例题1】 (1)用辗转相除法求840与1 785的最大公约数；(2)用更相减损术求612与468的最大公约数．分析：本题是关于辗转相除法和更相减损术的直接应用．辗转相除法的操作是较大的数除以较小的数；更相减损术的操作是以大数减小数．反思：(1)利用辗转相除法求最大公约数时经常会取错最后一个余数．因为辗转相除法有有限个除法式子，而最后一个余数在倒数第二个式子的最后．(2)利用更相减损术求解最大公约数时，最大公约数是直到差等于减数时的那个差，或是该差与约简的数的乘积．[]题型二求多项式的值【例题2】用秦九韶算法求多项式f()＝77＋66＋55＋44＋33＋22＋当＝3时的值．分析：解决本题首先需要将原多项式化成f()＝((((((7＋6)＋5)＋4)＋3)＋2)＋1)的形式，其次再弄清v0，v1，v2，…，v7分别是多少，再针对这些式子进行计算．反思：本题中比较容易出现的问题主要集中在计算上，多步计算必须保证每一步的正确性，否则最后不但将题目算错，而且浪费了宝贵的时间．题型三易错辨析【例题3】已知f()＝34＋22＋4＋2，利用秦九韶算法求f(－2)的值．错解：f()＝((32＋2)＋4)＋2，v1＝3×(－2)2＋2＝14；v2＝14×(－2)＋4＝－24；v3＝－24×(－2)＋2＝50故f(－2)＝50错因分析：所求f(－2)的值是正确的，但是错解中没有抓住秦九韶算法原理的关键，正确改写多项式，并使每一次计算只含有的一次项．答案：【例题1】解：(1)用辗转相除法求840和1 785的最大公约数．1 785＝840×2＋105，840＝105×8所以840和1 785的最大公约数是105(2)首先612和468都是偶数，所以用2约简，得到306和234，但它们还都是偶数，需要再用2约简，得到153和117，最后用更相减损术计算得153－117＝36，117－36＝81，81－36＝45，45－36＝9，36－9＝27，27－9＝18，18－9＝9所以612和468的最大公约数是9×2×2＝36【例题2】解：f()＝((((((7＋6)＋5)＋4)＋3)＋2)＋1)，所以有v0＝7；v1＝7×3＋6＝27；v2＝27×3＋5＝86；v3＝86×3＋4＝262；v4＝262×3＋3＝789；v5＝789×3＋2＝2 369；v6＝2 369×3＋1＝7 108；v7＝7 108×3＝21 324故当＝3时，多项式f()＝77＋66＋55＋44＋33＋22＋的值为21 324 【例题3】正解：f()＝34＋0·3＋22＋4＋2＝(((3＋0)＋2)＋4)＋2，v1＝3×(－2)＋0＝－6；v2＝－6×(－2)＋2＝14；v3＝14×(－2)＋4＝－24；v4＝－24×(－2)＋2＝50故f(－2)＝501．用更相减损术可求得78与36的最大公约数是( )A．24 B．18 ．12D．62．用秦九韶算法计算f()＝36＋45＋54＋63＋72＋8＋1当＝04时的值，需要进行乘法运算和加法运算的次数分别为( ) A．6,6 B．5,6 ．6,5D．6,123．利用辗转相除法求3 869与6 497的最大公约数时，第二步是．4．用秦九韶算法求多项式f()＝5＋54＋103＋102＋5＋1在＝－2时的值为．5．用辗转相除法求242与154的最大公约数．答案：1．D 先用2约简得39,18；然后辗转相减得39－18＝21，21－18＝3，18－3＝15,15－3＝12,12－3＝9,9－3＝6，6－3＝3所以所求的最大公约数为3×2＝62．A 改写多项式f()＝(((((3＋4)＋5)＋6)＋7)＋8)＋1，则需进行6次乘法和6次加法运算．3．3 869＝2 628×1＋1 241 第一步：6 497＝3 869×1＋2 628，第二步：3 869＝2 628×1＋1 2414．－1 改写多项式为f()＝((((＋5)＋10)＋10)＋5)＋1，当＝－2时，v0＝1；v1＝1×(－2)＋5＝3；v2＝3×(－2)＋10＝4；v3＝4×(－2)＋10＝2；v4＝2×(－2)＋5＝1；v5＝1×(－2)＋1＝－1；故f(－2)＝－15．解：242＝154×1＋88，154＝88×1＋66，88＝66×1＋22，66＝22×3所以242与154的最大公约数是22。

1．3算法案例第1课时辗转相除法、更相减损术与秦九韶算法[目标] 1.会用辗转相除法与更相减损术求两个数的最大公约数；2.会用秦九韶算法求多项式的值．[重点] 两种算法的原理及应用．[难点] 两种算法思想的理解．知识点一辗转相除法与更相减损术[填一填]1．辗转相除法(1)辗转相除法是用于求两个正整数的最大公约数的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法．(2)所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数．若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数．2．更相减损术更相减损术是我国古代数学专著《九章算术》中介绍的一种求两数最大公约数的方法．其基本过程是：第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数或这个数与约简的数的乘积就是所求的最大公约数．1．任意给定两个正整数，是否用辗转相除法和更相减损术都可以求它们的最大公约数？提示：是．辗转相除法和更相减损术都能在有限步内结束，故均可以用来求两个正整数的最大公约数．2．求最大公约数时，如何选择辗转相除法和更相减损术？提示：当两个数大小差别不大时，两种方法的计算次数区别不大，只是辗转相除法以除法为主，更相减损术以减法为主；当两个数大小差别较大时，辗转相除法的计算次数明显较少，可选择辗转相除法．3．用“辗转相除法”求得459和357的最大公约数是51.解析：用辗转相除法：459＝357×1＋102,357＝102×3＋51,102＝51×2.∴459与357的最大公约数为51.知识点二秦九韶算法[填一填]把一个n次多项式f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0改写成如下形式：f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0＝(…((a n x＋a n－1)x＋a n－2)x＋…＋a1)x＋a0.求多项式的值时，首先计算最内层括号内一次多项式的值，即v1＝a n x＋a n－1，然后由内向外逐层计算一次多项式的值，即v2＝v1x＋a n－2，v3＝v2x＋a n－3，…v n＝v n－1x＋a0，这样，求n次多项式f(x)的值就转化为求n个一次多项式的值．4．利用秦九韶算法求多项式f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0的值时，如何改写多项式，用这种方法，最多可进行多少次乘法，多少次加法？提示：可将多项式改写为f(x)＝(…(((a n x＋a n－1)x＋a n－2)x＋a n－3)x ＋…＋a1)x＋a0，这样最多只需n次乘法和n次加法即可求出多项式的值．5．用秦九韶算法计算多项式f(x)＝12＋5x－8x2＋7x3＋6x4＋5x5＋3x6当x＝－4时，v3的值为－129.解析：v1＝3×(－4)＋5＝－7，v2＝(－7)×(－4)＋6＝34，v3＝34×(－4)＋7＝－129.类型一辗转相除法与更相减损术[例1]求228与1 995的最大公约数．[解]法一：(辗转相除法)1 995＝8×228＋171,228＝1×171＋57,171＝3×57，所以228与1 995的最大公约数为57.法二：(更相减损术)1 995－228＝1 767,1 767－228＝1 539，1 539－228＝1 311,1 311－228＝1 083，1 083－228＝855,855－228＝627，627－228＝399,399－228＝171，228－171＝57,171－57＝114,114－57＝57.所以228与1 995的最大公约数为57.辗转相除法计算次数少，步骤简捷，更相减损术计算次数多，步骤复杂，但是更相减损术每一步的计算都是减法，比做除法运算要简单一些，一般当数较小时可以考虑用更相减损术，当数较大时可以考虑用辗转相除法.[变式训练1] 用辗转相除法和更相减损术求1 515与600的最大公约数，需要运算的次数分别为( B )A ．4,15B ．5,14C ．5,13D ．4,12解析：辗转相除法：1 515＝600×2＋315,600＝315×1＋285,315＝285×1＋30,285＝30×9＋15,30＝15×2，故最大公约数为15，且需计算5次．用更相减损术：1 515－600＝915,915－600＝315,600－315＝285,315－285＝30,285－30＝255,255－30＝225,225－30＝195,195－30＝165,165－30＝135,135－30＝105,105－30＝75,75－30＝45,45－30＝15,30－15＝15.故最大公约数为15，且需计算14次．类型二 秦九韶算法的应用[例2] 利用秦九韶算法分别计算f (x )＝8x 7＋5x 6＋3x 4＋2x ＋1在x ＝2与x ＝－1时的值，并判断多项式f (x )在区间[－1,2]有没有零点．[分析] ①分别求多项式f (x )在x ＝2与x ＝－1时的值；②秦九韶算法是⎩⎪⎨⎪⎧v 0＝a n v k ＝v k －1x ＋a n －k (k ＝1，2，…，n )，因此多项式f (x )中缺失的几项：x 5，x 3，x 2应该补充完整f (x )＝8x 7＋5x 6＋3x 4＋2x ＋1＝((((((8x ＋5)x ＋0)x ＋3)x ＋0)x ＋0)x ＋2)x ＋1.[解] ∵f (x )＝8x 7＋5x 6＋3x 4＋2x ＋1＝((((((8x ＋5)x ＋0)x ＋3)x ＋0)x ＋0)x ＋2)x ＋1，且x ＝2，∴v 0＝8，v 1＝8×2＋5＝21，v 2＝21×2＋0＝42，v 3＝42×2＋3＝87，v 4＝87×2＋0＝174，v 5＝174×2＋0＝348，v 6＝348×2＋2＝698，v 7＝698×2＋1＝1 397.∴当x ＝2时，f (x )＝1 397.同理可求当x ＝－1时，f (x )＝－1.又∵f (－1)f (2)＝－1 397<0，则多项式f (x )在区间[－1，2]上有零点．秦九韶算法的算法步骤第一步，输入多项式次数n 、最高次项的系数a n 和x 的值．第二步，将v 的值初始化为a n ，将i 的值初始化为n －1.第三步，输入i 次项的系数a i .第四步，v ＝v x ＋a i ，i ＝i －1.第五步，判断i 是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v .[变式训练2] 用秦九韶算法求多项式f (x )＝2＋0.35x ＋1.8x 2－3x 3＋6x 4－5x 5＋x 6在x ＝－1时的值时，令v 0＝a 6，v 1＝v 0x ＋a 5，…，v 6＝v 5x ＋a 0，则v 3的值是－15.解析： f (x )＝(((((x －5)x ＋6)x －3)x ＋1.8)x ＋0.35)x ＋2，v 0＝1，v 1＝v 0x －5＝－6，v 2＝v 1x ＋6＝－6×(－1)＋6＝12，v 3＝v 2x －3＝－15. 类型三 算法思想的应用[例3] 运用秦九韶算法求7次多项式f (x )＝a 7x 7＋a 6x 6＋a 5x 5＋a 4x 4＋a 3x 3＋a 2x 2＋a 1x ＋a 0当x ＝x 0时的值，x 0，a 1～a 7都由键盘输入，画出算法的程序框图．[分析] 用秦九韶算法对一个n 次多项式变形，可以得到下面的表达式：⎩⎪⎨⎪⎧v 0＝a n ，v k ＝v k －1·x ＋a n －k (k ＝1，2，3，…，n )，这是一个反复执行的步骤，因此可用循环结构来实现．[解]程序框图如下图所示：秦九韶算法思想就是先将多项式函数从外到内依次提取x，然后通过一次式的反复计算，逐步得出n次多项式的值，对于一个n次多项式，最多只需做n次乘法和n次加法即可.[变式训练3]阅读程序：INPUT “m，n＝”；m，nIF n>m THENt＝mm＝nn＝tEND IFDOr＝m MOD nm＝nn＝rLOOP UNTIL r＝0PRINT mEND若INPUT语句中输入m，n的数据分别是72,168，则程序运行的结果为24.解析：该程序是用辗转相除法求两个数的最大公约数的算法程序，输入72,168，即求它们的最大公约数，可求出它们的最大公约数为24.1．如图所示的程序表示的算法是(B)A．交换m，n的值B．辗转相除法C．更相减损术D．秦九韶算法2．两个整数490和910的最大公约数是(D)A．2 B．10C．30 D．70解析：(910,490)→(490,420)→(420,70)→(350,70)→(280,70)→(210,70)→(140,7 0)→(70,70)．3．用秦九韶算法计算多项式f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1当x＝0.4时的值时，需要做乘法和加法的次数分别是(A) A．6,6 B．5,6C．5,5 D．6,5解析：f(x)＝(((((3x＋4)x＋5)x＋6)x＋7)x＋8)x＋1.4．78和36的最大公约数为6.解析：78－36＝42,42－36＝6,36－6＝30,30－6＝24,24－6＝18,18－6＝12,12－6＝6.5．已知函数f (x )＝x 3－2x 2－5x ＋6，用秦九韶算法求f (10)的值． 解：由秦九韶算法，得f (x )＝x 3－2x 2－5x ＋6＝(x 2－2x －5)x ＋6＝((x －2)x －5)x ＋6.当x ＝10时，f (10)＝((10－2)×10－5)×10＋6＝(8×10－5)×10＋6＝75×10＋6＝756.——本课须掌握的三大问题1．辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数．2．更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数．3．用秦九韶算法求多项式f (x )当x ＝x 0的值的思路为：①改写；②计算⎩⎪⎨⎪⎧v 0＝a n v k ＝v k －1x 0＋a n －k (k ＝1，2，…，n )； ③结论f (x 0)＝v n .莘莘学子，最重要的就是不要去看远方模糊的，而要做手边清楚的事。