1、11.4算法案例1.理解辗转相除法与秦九韶算法的含义，了解其执行过程.2.掌握用算法解决实际问题.1.辗转相除法所谓辗转相除法，就是对于给定的两个正整数，用较大数除以较小数.若余数不为零，则将余数和较小数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小数就是原来两个数的最大公约数.伪代码如下：INPUTa，bDO ra MOD b ab brLOOP UNTILr0PRINTaEND2.秦九韶算法秦九韶算法其实质是通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，最多只需做n次乘法和n次加法即可.伪代码如下：INPUT“n”；nINPUT“an”；aINPUT“x
2、”；xvakn1WHILEk0 PRINT“k”；k INPUT“ak”；a vv*xa kk1WENDPRINTvEND1.判断正误.(对的打“”，错的打“”)(1)求两个正整数的最大公约数可以用辗转相除法.()(2)利用秦九韶算法计算时，乘法运算与加法运算次数相等.()答案：(1)(2)2.用秦九韶算法计算多项式f(x)3x64x55x46x37x28x1当x0.4时的值时，需要做乘法和加法的次数分别是()A.6，6B.5，6C.5，5D.6，5答案：A3.“辗转相除法”与“更相减损术”有何区别？解：辗转相除法的操作过程是先用两个数中较大的数除以较小的数，得商和余数；再用除数除以余数，重复
3、操作，直到出现余数为零，则这个最小除数就是两个数的最大公约数；而更相减损术是用较大数减去较小数，再把差与较小数作为一对相减直至差相等为止，则这个等数就是所求的最大公约数.辗转相除法学生用书P22利用辗转相除法求46，115和276的最大公约数.【解】求三个数的最大公约数，可以先求两个数的最大公约数，然后求第三个数与前两个数的最大公约数.276211546，11524623，46232，所以276与115的最大公约数为23.又46与23的最大公约数为23，所以46、115和276的最大公约数为23.利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为
4、零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数. 1.378与90的最大公约数为.解析：辗转相除法：37890418，901850，所以378与90的最大公约数是18.答案：18二分法学生用书P22写出用二分法求方程x32x30在区间1，2内的一个近似解(误差不超过0.001)的一个算法.【解】算法如下：S1：令f(x)x32x3，a1，b2，c0.001；S2：取x0；S3：若|ab|c，则进入S4；否则输出x0结束算法；S4：若f(x0)0，则进入S5；否则xx0就是方程的根，输出x0，结束算法；S5：若f(x0)f(a)0
5、，则解在x0，b中，用x0替换a；若f(x0)f(a)0，则解在a，x0中，用x0替换b，返回S2.用二分法求方程的近似解的步骤(1)画草图探索解所在的区间； (2)用二分法求符合限制条件的解；(3)编制伪代码用计算机完成.2.写出用二分法求方程x220的一个正的近似解(误差不超过0.005)的算法.解：算法如下：S1：令f(x)x22，因为f(1)0，所以令a1，b2，c0.005；S2：取x0；S3：若|ab|c，则进入S4；否则输出x0结束算法；S4：若f(x0)0，则进入S5；否则xx0就是方程的根，输出x0，结束算法；S5：若f(a)f(x0)0，则解在x0，b，用x0替换a；若f(
6、x0)f(a)0，则解在a，x0，用x0替换b；返回S2.秦九韶算法学生用书P23用秦九韶算法计算多项式f(x)x612x560x4160x3240x2192x64当x2时的值.【解】将f(x)改写为f(x)(x12)x60)x160)x240)x192)x64.由内向外依次计算一次多项式当x2时的值，v01，v1121210，v21026040，v340216080，v480224080，v580219232，v6322640，所以f(2)0，即x2时，原多项式的值为0.秦九韶算法的步骤 3.已知f(x)x52x33x2x1，应用秦九韶算法计算当x3时，v3的值为()A.27B11C.109
7、D36解析：选D.将多项式改写成如下形式：f(x)(x0)x2)x3)x1)x1，由内向外依次计算：v01，v11303，v233211，v3113336.选D.1.辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数.2.用秦九韶算法可大大降低乘法的运算次数，提高了运算速度.用此方法求值，关键是正确地将所给多项式改写，然后由内向外计算，由于后项计算需用到前项结果，故应认真、细心，确保结果的准确性.(1)求两个正数的公约数，当两数差别较大时，用辗转相除法，当两数差别不大时，用更相减损术较快.(2)利用秦九韶算法计算多项式值的关键是能准确地将多项式改写，然后由内向外逐次计算.由于
8、后项计算用到前项的结果，故应认真、细心，确保每项计算结果的准确性.1.用辗转相除法求36与134的最大公约数，第一步是()A.1343698B13433626C.先除以2，得到18与67 D134363(余26)解析：选B.用辗转相除法求36与134的最大公约数的第一步是计算较大数134除以较小数36的余数.2.用秦九韶算法求多项式f(x)4x5x22当x3时的值时，需要进行的乘法运算和加减运算的次数分别为()A.4，2 B5，3C.5，2 D6，2解析：选C.f(x)4x5x22(4x)x)x1)x)x2，所以需要5次乘法运算和2次加减运算.3.已知多项式p(x)3x59x4x3kx24x1
9、1，当x3时值为1 616，则k.解析：由秦九韶算法，得p(x)(3x9)x1)xk)x4)x11.则当x3时，p(3)(541)3k)34)311(4953k4)3119k1 5081 616，所以k12.答案：124.运行下面的伪代码：INPUTm，nDOrm MOD nmnnrLOOP UNTILr0PRINTmEND当输入168，72时，输出的结果是.解析：这个伪代码的作用是求m，n的最大公约数.故16872224，72243.所以，168与72的最大公约数是24.答案：245.已知一个一元五次多项式为f(x)5x52x43.5x32.6x21.7x0.8，用秦九韶算法求这个多项式当x
10、5时的值.解：f(x)5x52x43.5x32.6x21.7x0.8(5x2)x3.5)x2.6)x1.7)x0.8，v155227，v22753.5138.5，v3138.552.6689.9，v4689.951.73 451.2，v53 451.250.817 255.2.所以，当x5时，多项式的值等于17 255.2.A基础达标1.4 830与3 289的最大公约数为()A.23B35C.11 D13解析：选A.4 83013 2891 541；3 28921 541207；1 541720792；20729223；92423；所以23是4 830与3 289的最大公约数.2.有关辗转相
11、除法下列说法正确的是()A.它和更相减损之术一样是求多项式值的一种方法B.基本步骤是用较大的数m除以较小的数n得到除式mnqr，直至rn为止C.基本步骤是用较大的数m除以较小的数n得到除式mqnr(0rn)，反复进行，直到r0为止D.以上说法皆错答案：C3.用秦九韶算法求多项式f(x)7x66x53x22，当x4时，先算的是()A.4416 B7428C.44464 D74634解析：选D.因为f(x)anxnan1xn1a1xa0(anxan1)xan2)xa1)xa0，所以用秦九韶算法求多项式f(x)7x66x53x22当x4的值时，先算的是74634.4.45和150的最大公约数和最小公
12、倍数分别是()A.5，150 B15，450C.450，15 D15，150解析：选B.利用辗转相除法求45和150的最大公约数：15045315，45153，所以45和150的最大公约数为15.所以45和150的最小公倍数为15(4515)(15015)450，故选B.5.用秦九韶算法计算f(x)6x54x4x32x29x时，需要做加法(或减法)与乘法运算的次数分别为()A.5，4 B5，5C.4，4 D4，5解析：选D.n次多项式需进行n次乘法运算；若各项的系数均不为零，则需进行n次加法(或减法)运算，缺一项就减少一次加法(或减法)运算.f(x)中无常数项，故加法(或减法)运算要减少一次，
13、为514(次)，乘法运算的次数为5.故选D.6.用辗转相除法求得375和85的最大公约数为.解析：37585435，8535215，351525，15530.所以375与85的最大公约数为5.答案：57.按秦九韶算法，多项式f(x)4x62x53.5x43x32.5x22x750，当x3时的值为.解析：v04，v143214，v21433.545.5，v345.533139.5，v4139.532.5416，v5416321 250，v61 25037503 000.答案：3 0008.已知函数f(x)x32x25x6，用秦九韶算法，则f(10).解析：f(x)x32x25x6(x22x5)x
14、6(x2)x5)x6.当x10时，f(10)(102)105)106(8105)10675106756.答案：7569.现有长度为2.4米和5.6米两种规格的钢筋若干，要焊接一批正方体模型，问怎样设计才能保证正方体的体积最大且不浪费材料？解：用辗转相除法步骤如下：5.62.420.8，2.40.83，所以5.6与2.4的最大公约数为0.8，因此将正方体的棱长设为0.8米时，正方体的体积最大且不浪费材料.10.古时候，当边境有敌人来犯时，守边的官兵通过在烽火台上点火向境内报告来犯敌人数，如图所示，烽火台上点火表示数字1，未点火表示数字0，约定二进制数对应的十进制数的单位是1 000，请你计算一下
15、，这组烽火台表示有多少敌人入侵？解：由题图可知这组烽火台表示的二进制数为11011(2)，它表示的十进制数为11011(2)12412302212112027，由于约定二进制数对应的十进制数的单位是1 000，所以入侵的敌人的数目为271 00027 000(人).B能力提升11.下面一段伪代码的功能是()INPUTm，nWHILEmn IFmnTHENmmn ELSE nnm ENDIFWENDPRINTmENDA.求m，n的最小公倍数B.求m，n的最大公约数C.求m被n除的商D.求n除以m的余数解析：选B.本伪代码当m，n不相等时，总是用较大的数减去较小的数，直到相等时跳出循环，显然是“更
16、相减损术”.故选B.12.用秦九韶算法计算多项式f(x)1235x8x279x36x45x53x6在x4时的值时，v3的值为.解析：首先，将多项式按降幂排列得f(x)3x65x56x479x38x235x12，所以v03，v1v0x5，v2v1x6，v3v2x79，逐层代入可得v357.答案：5713.用辗转相除法求459和357的最大公约数.解：4593571102，357102351，102512，所以最大公约数为51.14.（选做题）利用秦九韶算法分别计算f(x)8x75x63x42x1在x2与x1时的值，并判断多项式f(x)在区间1，2有没有零点.解：因为f(x)8x75x63x42x1(8x5)x0)x3)x0)x0)x2)x1，且x2，所以v08，v182521，v2212042，v3422387，v48720174，v517420348，v634822698，v7698211 397.所以当x2时，f(x)1 397.同理可求当x1时，f(x)1，又因为f(1)f(2)1 3970，则多项式f(x)在区间1，2上有零点.