资源描述
第1课时辗转相除法与更相减损术、秦九韶算法1理解辗转相除法与更相减损术的含义，了解其执行过程2理解秦九韶算法的计算过程，并了解它提高计算效率的实质1辗转相除法与更相减损术(1)辗转相除法辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法辗转相除法的算法步骤第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，mn，nr.第四步，若r0，则m，n的最大公约数等于m；否则，返回第二步(2)更相减损术的算法步骤第一步，任意给定两个正整数，判断它们是否都是偶数若是，用2约简；若不是，执行第二步第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数(3)辗转相除法和更相减损术的区别与联系名称辗转相除法更相减损术区别(1)以除法为主；(2)两个整数的差值较大时，运算次数较少；(3)相除，余数为0时得结果(1)以减法为主；(2)两个整数的差值较大时，运算次数较多；(3)相减，减数与差相等时得结果；(4)相减前要进行是否都是偶数的判断联系(1)都是求两个正整数最大公约数的方法；(2)二者的实质都是递推的过程；(3)二者都要用循环结构来实现2.秦九韶算法(1)秦九韶算法简介秦九韶算法要解决的问题是求多项式的值秦九韶算法的特点通过一次式的反复计算，逐步得到高次多项式的值，即将一个n次多项式的求值问题归结为重复计算n个一次多项式的值的问题秦九韶算法的原理将f(x)anxnan1xn1a1xa0改写为：f(x)(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0先计算最内层括号内一次多项式的值，即v1anxan1，再由内向外逐层计算一次多项式vk的值(2)秦九韶算法的操作方法算法步骤如下第一步，输入多项式次数n、最高次项的系数an和x的值第二步，将v的值初始化为an，将i的值初始化为n1.第三步，输入i次项的系数ai.第四步，vvxai，ii1.第五步，判断i是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v.程序框图如图所示程序如下1实际应用更相减损术时要做的第一步工作是什么？提示先判断a，b是否为偶数，若是，都除以2再进行2判断正误(正确的打“”，错误的打“”)(1)辗转相除法的基本步骤是用较大的数除以较小的数()(2)求最大公约数的方法除辗转相除法之外，没有其他方法()(3)编写辗转相除法的程序时，要用到循环语句()提示(1)(2)(3)题型一辗转相除法和更相减损术的应用【典例1】用辗转相除法求612与468的最大公约数，并用更相减损术检验所得结果思路导引将612作为大数，468作为小数，执行辗转相除法和更相减损术的步骤即可. 解用辗转相除法：6124681144,468144336,144364，即612和468的最大公约数是36.用更相减损术检验：612和468为偶数，两次用2约简得153和117,15311736,1173681,813645,45369,36927,27918,1899，所以612和468的最大公约数为92236.求最大公约数的两种方法步骤(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数若是，用2约简，也可以不除以2，直接求最大公约数，这样不影响最后结果针对训练1用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果解803628，36844,8420，即80与36的最大公约数是4.验证：80240,36218；40220,1829；20911,1192；927,725；523,321；211,1224；所以80与36的最大公约数为4.题型二求三个正整数的最大公约数【典例2】求325,130,270三个数的最大公约数思路导引求三个数的最大公约数，可先求两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数解解法一(辗转相除法)：因为325130265,130652，所以325和130的最大公约数为65. 因为27065410,651065,1052, 所以65和270的最大公约数为5, 故325,130,270三个数的最大公约数为5. 解法二(更相减损术)：325130195,19513065,1306565. 所以325和130的最大公约数是65. 27065205,20565140,1406575,756510,651055,551045,451035,351025,251015,15105,1055. 所以65和270的最大公约数为5，故325,130,270三个数的最大公约数为5.理解辗转相除法的实质，从计算结果上看，辗转相除法是以相除余数为零而得到结果的. 针对训练2求三个数175,100,75的最大公约数. 解先求175与100的最大公约数：175100175,10075125,75253, 175与100的最大公约数是25. 再求25与75的最大公约数：752550,502525, 75和25的最大公约数是25. 175,100,75的最大公约数是25. 题型三秦九韶算法【典例3】已知一个5次多项式为f(x)4x52x43.5x32.6x21.7x0.8，用秦九韶算法求这个多项式当x5时的值. 思路导引可根据秦九韶算法的原理，将所给的多项式改写，然后由内到外逐次计算解将f(x)改写为f(x)(4x2)x3.5)x2.6)x1.7)x0.8，由内向外依次计算一次多项式，当x5时的值：v04；v145222；v22253.5113.5；v3113.552.6564.9；v4564.951.72826.2；v52826.250.814130.2.所以当x5时，多项式的值等于14130.2.(1)用秦九韶算法求多项式f(x)当xx0的值的思路为：改写计算结论f(x0)vn.(2)应用秦九韶算法计算多项式的值应注意的3个问题要正确将多项式的形式进行改写计算应由内向外依次计算当多项式函数中间出现空项时，要以系数为零的齐次项补充针对训练3用秦九韶算法计算多项式f(x)1235x8x26x45x53x6在x4时的值时，v3的值为()A144 B136 C57 D34解析根据秦九韶算法多项式可化为f(x)(3x5)x6)x0)x8)x35)x12.由内向外计算v03；v13(4)57；v27(4)634；v334(4)0136.答案B课堂归纳小结1.求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术用辗转相除法，即根据anbr这个式子，反复相除，直到r0为止；用更相减损术，即根据r|ab|这个式子，反复相减，直到r0为止2.秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行1辗转相除法可解决的问题是()A求两个正整数的最大公约数B多项式求值C求两个正整数的最小公倍数D排序问题解析辗转相除法可以求两个正整数的最大公约数. 答案A2用辗转相除法求72与120的最大公约数时，需要做除法次数为()A4 B3C5 D6解析12072148,7248124,48242.答案B3用更相减损术求36与134的最大公约数，第一步应为_解析36与134都是偶数，第一步应先除以2，得到18与67.答案先分别除以2，得到18与674用秦九韶算法求f(x)2x3x3当x3时的值v2_.解析f(x)(2x0)x1)x3，v02，v12306，v263119.答案195用秦九韶算法求多项式f(x)8x75x63x42x1，当x2时的值解根据秦九韶算法，把多项式改写成如下形式：f(x)8x75x60x53x40x30x22x1(8x5)x0)x3)x0)x0)x2)x1.而x2，所以有v08，v182521，v2212042，v3422387，v48720174，v517420348，v634822698，v7698211397.所以当x2时，多项式的值为1397.算法案例在实际生活中的应用通过算法案例的学习，知道算法的核心是一般意义上的解决问题的策略的具体化对于一个实际问题，我们在分析、思考后可将之转化为数学问题，从而获得解决它的基本思路. 【典例】现有长度为2.4 m和5.6 m两种规格的钢筋若干，要焊接一批棱上无接点的正方体模型，问怎样设计才能保证正方体的体积最大且不浪费材料？思路导引要焊接正方体，就是将两种规格的钢筋截成长度相等的钢筋条为了保证不浪费材料，应使得每种规格的钢筋截取后没有剩余，因此截取的长度应为2.4与5.6的公约数；为使得正方体的体积最大，因此截取的长度应为2.4与5.6的最大公约数. 解用更相减损术来求2.4与5.6的最大公约数：562.43.2, 322.40.8, 240.81.6, 160.80.8, 因此2.4与5.6的最大公约数为0.8. 所以使得正方体的棱长为0.8 m时，正方体的体积最大且不浪费材料. 针对训练甲，乙，丙三种溶液的质量分别为147 g，343 g，133 g，现要将它们分别全部装入小瓶中，每个小瓶中装入溶液的质量相同，问每瓶最多装多少？解由题意，每个小瓶中装入的溶液的质量应是三种溶液质量的最大公约数先求147与343的最大公约数：343147196,19614749,1474998,984949，所以147与343的最大公约数是49.再求49与133的最大公约数：1334984,844935,493514,351421,21147,1477，所以147,343,133的最大公约数为7，即每瓶最多装7 g.课后作业(八) (时间45分钟)学业水平合格练(时间25分钟)1秦九韶算法与直接计算相比较，下列说法错误的是()A秦九韶算法与直接计算相比，大大节省了做乘法的次数，使计算量减少，并且逻辑结构简单B秦九韶算法减少了做乘法的次数，在计算机上也就加快了计算的速度C秦九韶算法减少了做乘法的次数，在计算机上也就降低了计算的速度D秦九韶算法避免了对自变量x单独做幂的计算，而且与系数一起逐次增长幂次，从而提高计算的精度解析秦九韶算法减少了做乘法的次数，在计算机上也就加快了计算的速度，故选项C错误答案C2下列说法中正确的个数为()辗转相除法也叫欧几里得算法；辗转相除法的基本步骤是用较大的数除以较小的数；求最大公约数的方法，除辗转相除法之外，没有其他方法；编写辗转相除法的程序时，要用到循环语句A1 B2 C3 D4解析、正确，错误答案C3利用秦九韶算法求f(x)12x3x26x5当x2时的值时，下列说法正确的是()A先求122B先求625，第二步求2(625)4Cf(2)122322423524625直接运算求解D以上都不对解析利用秦九韶算法应先算anxan1，再算(anxan1)xan2，故选B.答案B4中国古代有计算多项式值的秦九韶算法，下图是实现该算法的程序框图执行该程序框图，若输入的x2，n2，依次输入的a为2,2,5，则输出的s()A7 B12 C17 D34解析该题考查程序框图的运行及考生的识图能力由程序框图知，第一次循环：x2，n2，a2，s0222，k1；第二次循环：a2，s2226，k2；第三次循环：a5，s62517，k3.结束循环，输出s的值为17，故选C.答案C5用更相减损术求117和182的最大公约数时，需做减法的次数是()A8 B7 C6 D5解析18211765,1176552,655213,521339,391326,261313，13是117和182的最大公约数，需做减法的次数是6.答案C6用秦九韶算法求n次多项式f(x)anxnan1xn1a1xa0当xx0时的值，求f(x0)需要乘方、乘法、加法的次数分别为()A.，n，nBn,2n，nC0,2n，nD0，n，n解析因为f(x)(anxan1)xan2)xa1)xa0，所以乘方、乘法、加法的次数分别为0，n，n.答案D7用秦九韶算法求多项式f(x)1235x8x279x36x45x53x6当x4的值时，其中v1的值为_解析f(x)1235x8x279x36x45x53x6，v0a63，v1v0xa53(4)57.答案78378和90的最大公约数为_解析37890418,901850，378与90的最大公约数是18.答案189求1356和2400的最小公倍数解2400135611044，135610441312，10443123108，312108296，10896112，96128.所以1356与2400的最大公约数为12.则1356与2400的最小公倍数为(13562400)12271200.10用秦九韶算法求多项式f(x)7x76x65x54x43x32x2x当x3时的值解f(x)(7x6)x5)x4)x3)x2)x1)x，所以v07，v173627，v2273586，v38634262，v426233789，v5789322369，v62369317108，v77108321324.故x3时，多项式f(x)7x76x65x54x43x32x2x的值为21324.应试能力等级练(时间20分钟)11下列哪组的最大公约数与1855,1120的最大公约数不同()A1120,735 B385,350C385,735 D1855,325解析(1855,1120)(735,1120)(735,385)(350,385)(350,35)，1855与1120的最大公约数是35，由以上计算过程可知选D.答案D12用秦九韶算法计算多项式f(x)3x64x55x46x37x28x1，当x0.4时的值时，需要做乘法和加法的次数分别是()A6,6B5,6C5,5D6,5解析根据秦九韶算法，把多项式改写为f(x)(3x4)x5)x6)x7)x8)x1，需要做6次加法运算，6次乘法运算，故选A.答案A13已知a333，b24，则使得abqr(q，r均为自然数，且0rb)成立的q和r的值分别为_解析用333除以24，商即为q，余数就是r.33324的商为13，余数是21.q13，r21.答案13,2114用秦九韶算法求多项式f(x)15x8x210x36x412x53x6当x4时的值时，v0，v1，v2，v3，v4中最大值与最小值的差是_解析多项式变形为f(x)3x612x56x410x38x25x1(3x12)x6)x10)x8)x5)x1，v03，v13(4)120，v20(4)66，v36(4)1014，v414(4)848，所以v4最大，v3最小，所以v4v3481462.答案6215用辗转相除法和更相减损术两种方法求三个数72,120,168的最大公约数解(辗转相除法)：先求120,168的最大公约数因为168120148，12048224,48242，所以120,168的最大公约数是24.再求72,24的最大公约数因为72243，所以72,24的最大公约数为24，即72,120,168的最大公约数为24.(更相减损术)：先求120,168的最大公约数16812048,1204872，724824,482424，所以120,168的最大公约数为24.再求72,24的最大公约数722448,482424，所以72,24的最大公约数为24，即72,120,168的最大公约数为24.13
展开阅读全文