第一章13算法案例一Word文件下载.docx

1、vnvn1xa0，这样，求n次多项式f（x）的值就转化为求n个一次多项式的值类型一辗转相除法例1试用辗转相除法求325、130、270的最大公约数解325130265,130652，325与130的最大公约数是65.27065410,651065,1052，65与270的最大公约数是5，故325、130、270这三个数的最大公约数为5.反思与感悟辗转相除法的实质：对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到大数被小数除尽，则这时的小数就是原来两个正整数的最大公约数跟踪训练1用辗转相除法求204与85的最大公约数时，需要做除法的

2、次数是_答案3解析用辗转相除法可得20485234,8534217,34172，此时可以判断204与85的最大公约数是17，做了3次除法得出结果类型二更相减损术例2试用更相减损术求612、396的最大公约数解方法一6122306,3962198,3062153,198299，1539954,995445,54459,45936,36927,27918,1899.所以612、396的最大公约数为92236.方法二612396216,396216180,21618036,18036144,14436108,1083672,723636.故36为612、396的最大公约数反思与感悟用更相减损术的算法

3、步骤第一步，给定两个正整数m，n，不妨设mn.第二步，若m，n都是偶数，则不断用2约简，使它们不同时是偶数，约简后的两个数仍记为m，n.第三步，dmn.第四步，判断“dn”是否成立，若是，则将n，d中的较大者记为m，较小者记为n，返回第三步；否则，2kd（k是约简整数2的个数）为所求的最大公约数跟踪训练2用更相减损术求261和319的最大公约数解31926158，26158203，20358145，1455887，875829，582929，319与261的最大公约数为29.类型三秦九韶算法的基本思想例3已知一个5次多项式为f（x）4x52x43.5x32.6x21.7x0.8，用秦九韶算法求

4、这个多项式当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.72 826.2；v52 826.250.814 130.2.当x5时，多项式的值等于14 130.2.反思与感悟秦九韶算法之所以优秀，一是其对所有多项式求值都适用，二是充分利用已有计算成果，效率更高跟踪训练3用秦九韶算法求多项式f（x）7x76x65x54x43x32x2x当x3时的值解f（x）（7x6）x5）x4）x3）x2）x1）x，所以有v07，

5、v173627，v2273586，v38634262，v426233789，v5789322 369，v62 369317 108，v77 108321 324.故当x3时，多项式f（x）7x76x65x54x43x32x2x的值为21 324.1下列说法中正确的个数为（）辗转相除法也叫欧几里得算法；辗转相除法的基本步骤是用较大的数除以较小的数；求最大公约数的方法除辗转相除法之外，没有其他方法；编写辗转相除法的程序时，要用到循环语句A1 B2 C3 D4答案C解析依据辗转相除法可知，正确，错误，故选C.2用秦九韶算法计算多项式f（x）6x65x54x43x32x2x7在x0.4时的值时，需做加

6、法和乘法的次数的和为（）A10 B9 C12 D8解析f（x）（6x5）x4）x3）x2）x1）x7，做加法6次，乘法6次，6612（次），故选C.3已知a333，b24，则使得abqr（q，r均为自然数，且0rb）成立的q和r的值分别为_答案13,21解析用333除以24，商即为q，余数就是r.333241321.4187和253的最大公约数是_答案11解析253187166,18766255,6655111,55115，253和187的最大公约数为11.5分别用辗转相除法和更相减损术求1 734和816的最大公约数解辗转相除法：1 7348162102,8161028.所以1 734与81

7、6的最大公约数是102.更相减损术：因为1 734和816都是偶数，所以分别除以2得867和408.867408459,45940851,40851357，35751306,30651255,25551204，20451153,15351102,1025151.所以867和408的最大公约数是51，故1 734和816的最大公约数是512102.1辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数2更相减损术，就是对于给定的两个正整数，用较大的数减去较小的

8、数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数3用秦九韶算法求多项式f（x）当xx0的值的思路为（1）改写；（2）计算（3）结论f（x0）vn.40分钟课时作业一、选择题1关于辗转相除法，下列说法正确的是（）A它和更相减损术一样是求多项式的值的一种方法B基本步骤是用较大的数m除以较小的数n得到除式mnqr，直到rn为止C基本步骤是用较大的数m除以较小的数n得到除式mnqr（0rn），反复进行，直到r0为止D以上说法皆不正确21 037和425的最大公约数是（）A51 B17 C9 D3答案B解析1 0374252187，42

9、5187251，18751334，5134117，34172，即1 037和425的最大公约数是17.3利用秦九韶算法求当x2时，f（x）12x3x24x35x46x5的值，下列说法正确的是（）A先求122B先求625，第二步求2（625）4C用f（2）122322423524625直接运算求解D以上都不正确445和150的最大公约数和最小公倍数分别是（）A5,150 B15,450C450,15 D15,150解析利用辗转相除法求45和150的最大公约数：15045315,45153，所以45和150的最大公约数为15.所以45和150的最小公倍数为15（4515）（15015）450，故选

10、B.5下边程序框图的算法思路源于我国古代数学名著九章算术中的“更相减损术”执行该程序框图，若输入的a，b分别为14,18，则输出的a等于（）A0 B2 C4 D14解析开始：a14，b18，第一次循环：a14，b4；第二次循环：a10，b4；第三次循环：a6，b4；第四次循环：a2，b4；第五次循环：a2，b2.此时，ab，退出循环，输出a2.6用秦九韶算法求多项式f（x）12xx23x32x4当x1时的值时，v2的结果是（）A4 B1C5 D6答案D解析此题的n4，a42，a33，a21，a12，a01，由秦九韶算法的递推关系式得v1v0xa32（1）35，v2v1xa25（1）16，故选D

11、.7三个数4 557、1 953、5 115的最大公约数是（）A31 B93 C217 D6518已知f（x）x52x33x2x1，应用秦九韶算法计算当x3时的值时，v3的值为（）A27 B11 C109 D36解析将函数式化成如下形式，f（x）（x0）x2）x3）x1）x1.由内向外依次计算：v01，v11303，v233211，v3113336，v43631109，v510931328.二、填空题9辗转相除法程序中有一空请填上INPUT“a，b”；a，bDOrabbrLOOP UNTILr0PRINTaEND答案a MOD b解析MOD用来表示a除以b的余数10用秦九韶算法求多项式6x35

12、x24x3的值时，应先将此多项式变形为_答案x（x（6x5）4）3解析6x35x24x3（6x25x4）x3（6x5）x4）x3.11用秦九韶算法求多项式f（x）20.35x1.8x23.66x36x45.2x5x6在x1.3时的值时，令v0a6，v1v0xa5，v6v5xa0时，v3的值为_答案22.44512用辗转相除法求85与51的最大公约数时，需要做除法的次数为_解析8551134，20.三、解答题13用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果解803628，36844,8420，即80与36的最大公约数是4.验证：80240,36218；40220,1829；2

13、0911,1192；927,725；523,321；211,1224；所以80与36的最大公约数为4.14用秦九韶算法求多项式f（x）4x53x45x3x2x当x2时的值解因为f（x）（4x3）x5）x1）x1）x，所以v04，2311，v2112527，v3272155，v45521111，v51112222.所以当x2时，多项式f（x）4x53x45x3x2x的值为222.15有甲、乙、丙三种溶液分别重147 g,343 g,133 g，现要将它们分别全部装入小瓶中，每个小瓶装入液体的质量相同，每瓶最多装多少克溶液？解每个小瓶装的溶液的质量应是三种溶液质量的最大公约数，先求147和343的最大公约数.343147196,19614749,1474998,984949.所以147和343的最大公约数为49.同理可求得49与133的最大公约数为7.所以每瓶最多装7克