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

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

《第一章13算法案例一Word文件下载.docx》由会员分享，可在线阅读，更多相关《第一章13算法案例一Word文件下载.docx（12页珍藏版）》请在冰点文库上搜索。

…

vn＝vn－1x＋a0，

这样，求n次多项式f（x）的值就转化为求n个一次多项式的值．

类型一　辗转相除法

例1　试用辗转相除法求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.

反思与感悟　辗转相除法的实质：

对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到大数被小数除尽，则这时的小数就是原来两个正整数的最大公约数．

跟踪训练1　用辗转相除法求204与85的最大公约数时，需要做除法的次数是________．

答案　3

解析　用辗转相除法可得204÷

85＝2……34,85÷

34＝2……17,34÷

17＝2，此时可以判断204与85的最大公约数是17，做了3次除法得出结果．

类型二　更相减损术

例2　试用更相减损术求612、396的最大公约数．

解　方法一　612÷

2＝306,396÷

2＝198,306÷

2＝153,198÷

2＝99，∴153－99＝54,99－54＝45,54－45＝9,45－9＝36,36－9＝27,27－9＝18,18－9＝9.所以612、396的最大公约数为9×

22＝36.

方法二　612－396＝216,396－216＝180,216－180＝36,180－36＝144,144－36＝108,108－36＝72,72－36＝36.故36为612、396的最大公约数．

反思与感悟　用更相减损术的算法步骤

第一步，给定两个正整数m，n，不妨设m＞n.

第二步，若m，n都是偶数，则不断用2约简，使它们不同时是偶数，约简后的两个数仍记为m，n.

第三步，d＝m－n.

第四步，判断“d≠n”是否成立，若是，则将n，d中的较大者记为m，较小者记为n，返回第三步；

否则，2kd（k是约简整数2的个数）为所求的最大公约数．

跟踪训练2　用更相减损术求261和319的最大公约数．

解　∵319－261＝58，

261－58＝203，

203－58＝145，

145－58＝87，

87－58＝29，

58－29＝29，

∴319与261的最大公约数为29.

类型三　秦九韶算法的基本思想

例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.

反思与感悟　秦九韶算法之所以优秀，一是其对所有多项式求值都适用，二是充分利用已有计算成果，效率更高．

跟踪训练3　用秦九韶算法求多项式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.

1．下列说法中正确的个数为（　　）

①辗转相除法也叫欧几里得算法；

②辗转相除法的基本步骤是用较大的数除以较小的数；

③求最大公约数的方法除辗转相除法之外，没有其他方法；

④编写辗转相除法的程序时，要用到循环语句．

A．1B．2C．3D．4

答案　C

解析　依据辗转相除法可知，①②④正确，③错误，故选C.

2．用秦九韶算法计算多项式f（x）＝6x6＋5x5＋4x4＋3x3＋2x2＋x＋7在x＝0.4时的值时，需做加法和乘法的次数的和为（　　）

A．10B．9C．12D．8

解析　f（x）＝（（（（（6x＋5）x＋4）x＋3）x＋2）x＋1）x＋7，

∴做加法6次，乘法6次，∴6＋6＝12（次），故选C.

3．已知a＝333，b＝24，则使得a＝bq＋r（q，r均为自然数，且0≤r＜b）成立的q和r的值分别为________．

答案　13,21

解析　用333除以24，商即为q，余数就是r.333÷

24＝13……21.

4．187和253的最大公约数是________．

答案　11

解析　∵253＝187×

1＋66,187＝66×

2＋55,66＝55×

1＋11,55＝11×

5，

∴253和187的最大公约数为11.

5．分别用辗转相除法和更相减损术求1734和816的最大公约数．

解　辗转相除法：

1734＝816×

2＋102,816＝102×

8.

所以1734与816的最大公约数是102.

更相减损术：

因为1734和816都是偶数，所以分别除以2得867和408.

867－408＝459,459－408＝51,408－51＝357，

357－51＝306,306－51＝255,255－51＝204，

204－51＝153,153－51＝102,102－51＝51.

所以867和408的最大公约数是51，故1734和816的最大公约数是51×

2＝102.

1．辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数．

2．更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数．

3．用秦九韶算法求多项式f（x）当x＝x0的值的思路为

（1）改写；

（2）计算

（3）结论f（x0）＝vn.

40分钟课时作业

一、选择题

1．关于辗转相除法，下列说法正确的是（　　）

A．它和更相减损术一样是求多项式的值的一种方法

B．基本步骤是用较大的数m除以较小的数n得到除式m＝nq＋r，直到r<

n为止

C．基本步骤是用较大的数m除以较小的数n得到除式m＝nq＋r（0≤r<

n），反复进行，直到r＝0为止

D．以上说法皆不正确

2．1037和425的最大公约数是（　　）

A．51B．17C．9D．3

答案　B

解析　∵1037＝425×

2＋187，

425＝187×

2＋51，

187＝51×

3＋34，

51＝34×

1＋17，

34＝17×

2，

即1037和425的最大公约数是17.

3．利用秦九韶算法求当x＝2时，f（x）＝1＋2x＋3x2＋4x3＋5x4＋6x5的值，下列说法正确的是（　　）

A．先求1＋2×

2

B．先求6×

2＋5，第二步求2×

（6×

2＋5）＋4

C．用f

（2）＝1＋2×

2＋3×

22＋4×

23＋5×

24＋6×

25直接运算求解

D．以上都不正确

4．45和150的最大公约数和最小公倍数分别是（　　）

A．5,150B．15,450

C．450,15D．15,150

解析　利用辗转相除法求45和150的最大公约数：

150＝45×

3＋15,45＝15×

3，所以45和150的最大公约数为15.所以45和150的最小公倍数为15×

（45÷

15）×

（150÷

15）＝450，故选B.

5．下边程序框图的算法思路源于我国古代数学名著《九章算术》中的“更相减损术”．执行该程序框图，若输入的a，b分别为14,18，则输出的a等于（　　）

A．0B．2C．4D．14

解析　开始：

a＝14，b＝18，

第一次循环：

a＝14，b＝4；

第二次循环：

a＝10，b＝4；

第三次循环：

a＝6，b＝4；

第四次循环：

a＝2，b＝4；

第五次循环：

a＝2，b＝2.

此时，a＝b，退出循环，输出a＝2.

6．用秦九韶算法求多项式f（x）＝1＋2x＋x2－3x3＋2x4当x＝－1时的值时，v2的结果是（　　）

A．－4B．－1

C．5D．6

答案　D

解析　此题的n＝4，a4＝2，a3＝－3，a2＝1，a1＝2，a0＝1，由秦九韶算法的递推关系式

得v1＝v0x＋a3＝2×

（－1）－3＝－5，v2＝v1x＋a2＝－5×

（－1）＋1＝6，故选D.

7．三个数4557、1953、5115的最大公约数是（　　）

A．31B．93C．217D．651

8．已知f（x）＝x5＋2x3＋3x2＋x＋1，应用秦九韶算法计算当x＝3时的值时，v3的值为（　　）

A．27B．11C．109D．36

解析　将函数式化成如下形式，

f（x）＝（（（（x＋0）x＋2）x＋3）x＋1）x＋1.

由内向外依次计算：

v0＝1，

v1＝1×

3＋0＝3，

v2＝3×

3＋2＝11，

v3＝11×

3＋3＝36，

v4＝36×

3＋1＝109，

v5＝109×

3＋1＝328.

二、填空题

9．辗转相除法程序中有一空请填上．

INPUT　“a，b＝”；

a，b

DO

r＝　　　　　　

a＝b

b＝r

LOOPUNTIL　r＝0

PRINT　a

END

答案　aMODb

解析　MOD用来表示a除以b的余数．

10．用秦九韶算法求多项式6x3＋5x2＋4x＋3的值时，应先将此多项式变形为________．

答案　x（x（6x＋5）＋4）＋3

解析　6x3＋5x2＋4x＋3＝（6x2＋5x＋4）x＋3＝（（6x＋5）x＋4）x＋3.

11．用秦九韶算法求多项式f（x）＝2＋0.35x＋1.8x2－3.66x3＋6x4－5.2x5＋x6在x＝－1.3时的值时，令v0＝a6，v1＝v0x＋a5，…，v6＝v5x＋a0时，v3的值为________．

答案　－22.445

12．用辗转相除法求85与51的最大公约数时，需要做除法的次数为________．

解析　85＝51×

1＋34，

2＋0.

三、解答题

13．用辗转相除法求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.

14．用秦九韶算法求多项式f（x）＝4x5＋3x4＋5x3＋x2＋x当x＝2时的值．

解　因为f（x）＝（（（（4x＋3）x＋5）x＋1）x＋1）x，

所以v0＝4，

2＋3＝11，

v2＝11×

2＋5＝27，

v3＝27×

2＋1＝55，

v4＝55×

2＋1＝111，

v5＝111×

2＝222.

所以当x＝2时，多项式f（x）＝4x5＋3x4＋5x3＋x2＋x的值为222.

15．有甲、乙、丙三种溶液分别重147g,343g,133g，现要将它们分别全部装入小瓶中，每个小瓶装入液体的质量相同，每瓶最多装多少克溶液？

解　每个小瓶装的溶液的质量应是三种溶液质量的最大公约数，先求147和343的最大公约数.343－147＝196,196－147＝49,147－49＝98,98－49＝49.

所以147和343的最大公约数为49.

同理可求得49与133的最大公约数为7.

所以每瓶最多装7克．