2019-2020学年高中数学 第1章 算法初步 1-3-1 辗转相除法与更相减损术、秦九韶算法课件

算法初步第一章1．3算法案例第1课时辗转相除法与更相减损术、秦九韶算法课前自主预习1．理解辗转相除法与更相减损术的含义，了解其执行过程．2．理解秦九韶算法的计算过程，并了解它提高计算效率的实质．1．辗转相除法与更相减损术(1)辗转相除法①辗转相除法，又叫欧几里得算法，是一种求两个正整数的的古老而有效的算法．最大公约数②辗转相除法的算法步骤第一步，给定.第二步，计算.第三步，.第四步，若r＝0，则m，n的最大公约数等于；否则，返回两个正整数m，nm除以n所得的余数rm＝n，n＝rm第二步．(2)更相减损术的算法步骤第一步，任意给定两个正整数，判断它们是否都是若是，用约简；若不是，执行第二步，以的数减去的数，接着把所得的差与的数比较，并以大数减小数．继续这个操作，直到所得的数为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．偶数．2第二步．较大较小较小相等(3)辗转相除法和更相减损术的区别与联系名称辗转相除法更相减损术区别(1)以除法为主；(2)两个整数的差值较大时，运算次数较少；(3)相除，余数为0时得结果(1)以减法为主；(2)两个整数的差值较大时，运算次数较多；(3)相减，减数与差相等时得结果；(4)相减前要进行是否都是偶数的判断联系(1)都是求两个正整数最大公约数的方法；(2)二者的实质都是递推的过程；(3)二者都要用循环结构来实现2.秦九韶算法(1)秦九韶算法简介①秦九韶算法要解决的问题是②秦九韶算法的特点通过的反复计算，逐步得到高次多项式的值，即将一个n次多项式的求值问题归结为重复计算n个的问题．求多项式的值．一次式一次多项式的值③秦九韶算法的原理将f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写为：f(x)＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0＝…先计算最内层括号内一次多项式的值，即v1＝anx＋an－1，再由内向外逐层计算一次多项式vk的值．(2)秦九韶算法的操作方法①算法步骤如下第一步，输入多项式次数n、最高次项的系数an和x的值．第二步，将v的值初始化为an，将i的值初始化为n－1.第三步，输入i次项的系数ai.第四步，v＝，i＝.第五步，判断i是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v.vx＋aii－1②程序框图如图所示③程序如下INPUT“n＝”；nINPUT“an＝”；aINPUT“x＝”；xv＝ai＝n－1WHILEi＞＝0INPUT“ai＝”；av＝v*x＋ai＝i－1WENDPRINTvEND1．实际应用更相减损术时要做的第一步工作是什么？[提示]先判断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；v1＝4×5＋2＝22；v2＝22×5＋3.5＝113.5；v3＝113.5×5－2.6＝564.9；v4＝564.9×5＋1.7＝2826.2；v5＝2826.2×5－0.8＝14130.2.所以当x＝5时，多项式的值等于14130.2.(1)用秦九韶算法求多项式f(x)当x＝x0的值的思路为：①改写．②计算v0＝an，vk＝vk－1x0＋an－kk＝1，2，…，n.③结论f(x0)＝vn.(2)应用秦九韶算法计算多项式的值应注意的3个问题①要正确将多项式的形式进行改写．②计算应由内向外依次计算．③当多项式函数中间出现空项时，要以系数为零的齐次项补充．[针对训练3]用秦九韶算法计算多项式f(x)＝12＋35x－8x2＋6x4＋5x5＋3x6在x＝－4时的值时，v3的值为()A．－144B．－136C．－57D．34[解析]根据秦九韶算法多项式可化为f(x)＝(((((3x＋5)x＋6)x＋0)x－8)x＋35)x＋12.由内向外计算v0＝3；v1＝3×(－4)＋5＝－7；v2＝－7×(－4)＋6＝34；v3＝34×(－4)＋0＝－136.[答案]B课堂归纳小结1.求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术．用辗转相除法，即根据a＝nb＋r这个式子，反复相除，直到r＝0为止；用更相减损术，即根据r＝|a－b|这个式子，反复相减，直到r＝0为止．2.秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行．