学案513 算法案例.docx

学案513 算法案例.docx

《学案513 算法案例.docx》由会员分享，可在线阅读，更多相关《学案513 算法案例.docx（14页珍藏版）》请在冰点文库上搜索。

学案513算法案例

1.3算法案例

知识一

辗转相除法与更相减损术

[提出问题]

问题1：

如何求18与54的最大公约数？

问题2：

要求6750与3492的最大公约数，上述法还好用吗？

问题3：

还有没有其他方法，可用来解决问题2中的问题？

[导入新知]

1．辗转相除法

（1）辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．

（2）辗转相除法的算法步骤：

第一步，给定两个正整数m，n.

第二步，计算m除以n所得的余数r.

第三步，m＝n，n＝r.

第四步，若r＝0，则m，n的最大公约数等于m；否则返回第二步．

2．更相减损术

（1）更相减损术是我国古代数学专著《九章算术》中介绍的一种求两个正整数的最大公

约数的算法．

（2）其基本过程是：

第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执

行第二步．

第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，

继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所

求的最大公约数．

[化解疑难]

辗转相除法与更相减损术的比较

两种方法

辗转相除法

更相减损术

计算法则

除法

减法

终止条件

余数为0

减数与差相等

最大公约数的选取

最后一步中的除数

最后一步中的减数

计算次数

步骤较少，运算复杂

步骤较多，运算简单

相同点

同为求两个正整数最大公约数的方法，都是递归过程

知识点二

秦九韶算法

[提出问题]

已知多项式f（x）＝x5＋3x4－3x3＋4x2－x－1.

问题1：

提示：

f

（1）＝1＋3－3＋4－1－1＝3.

问题2：

若求f（39），再代入运算出现什么情况？

问题3：

当x的值较大时，有没有更好的方法求函数值呢？

[导入新知]

秦九韶算法的算法原理

把一个n次多项式f（x）＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：

f（x）＝anxn＋an－1xn－1＋…＋a1x＋a0

＝（anxn－1＋an－1xn－2＋…＋a1）x＋a0

＝（（anxn－2＋an－1xn－3＋…＋a2）x＋a1）x＋a0

＝…

＝（…（（anx＋an－1）x＋an－2）x＋…＋a1）x＋a0.

求多项式的值时，首先计算最内层括号内一次多项式的值，即v1＝anx＋an－1，

然后由内向外逐层计算一次多项式的值，即

v2＝v1x＋an－2，

v3＝v2x＋an－3，

…

vn＝vn－1x＋a0，

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

[化解疑难]

秦九韶算法的步骤

知识点三

进位制

[提出问题]

问题1：

今天是星期二，那么20天后是星期几？

问题2：

每周七天，逢七便又是一循环，这与我们所学过的十进制，逢十进一是否有相似之处？

[导入新知]

1．进位制

（1）概念：

进位制是为了计数和运算方便而约定的记数系统，“满几进一”就是几进制．

（2）基数：

几进制的基数就是几．

2．不同进位制之间的互化

（1）k进制化为十进制的方法：

anan－1…a1a0（k）＝an×kn＋an－1×kn－1＋…＋a1×k＋a0（an，an－1，…，a1，a0∈N,0＜an＜k,

0≤an－1，…，a1，a0＜k）．

（2）十进制化为k进制的方法——除k取余数．

[化解疑难]

常见的进位制

（1）二进制：

①只使用0和1两个数字；②满二进一，如1＋1＝10.

（2）八进制：

①使用0,1,2,3,4,5,6,7八个不同的数字；②满八进一，如7＋1＝10.

（3）十六进制：

①使用0,1,2,3,4,5,6,7,8,9，A，B，C，D，E，F这十六个不同的数码，其中A，B，C，D，E，F分别代表十进制中的10,11,12,13,14,15；②满十六进一，如F＋1＝2＋E＝10.

题型一

求最大公约数

[例1]　分别用辗转相除法和更相减损术求779与209的最大公约数．

[类题通法]

1．用辗转相除法求最大公约数的步骤

2．用更相减损术求最大公约数的步骤

第一步，给定两个正整数m，n（m＞n且m，n不全是偶数）．

第二步，计算m－n所得的差k.

第三步，比较n与k的大小，其中大者用m表示，小者用n表示．

第四步，若m＝n，则m，n的最大公约数等于m；否则，返回第二步．

[活学活用]

用辗转相除法和更相减损术求1515与600的最大公约数，需要运算的次数分别为（　　）

A．4,15B．5,14

C．5,13D．4,12

题型二

秦九韶算法及其应用

[例2]　

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

A．27B．11

C．109D．36

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

[类题通法]

秦九韶算法原理及注意事项

（1）秦九韶算法的原理是

（k＝1,2，…，n）．

（2）在运用秦九韶算法进行计算时，应注意每一步的运算结果，像这种一环扣一环的运算，如果错一步，那么下一步，一直到最后一步就会全部算错，同学们在计算这种题时应格外小心．

[活学活用]

用秦九韶算法计算多项式f（x）＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1当x＝0.4时的值时，需要做乘法和加法的次数分别是（　　）

A．6,6B．5,6

C．5,5D．6,5

题型三

进位制

[例3]　

（1）将101111011

（2）转化为十进制的数；

（2）将235（7）转化为十进制的数；

（3）将137（10）转化为六进制的数；

（4）将53（8）转化为二进制的数．

[类题通法]

1．k进制数化为十进制数的步骤

（1）把k进制数写成不同数位上的数字与k的幂的乘积之和的形式．

（2）按十进制数的运算规则运算出结果．

2．十进制数化为k进制数（除k取余法）的步骤

[活学活用]

若六进制数13m502（6）化为十进制数等于12710，求数字m的值．

典例利用秦九韶算法求f（x）＝x5＋x3＋x2＋x＋1当x＝3时的值（　　）

A．121　　　　　　　　B．283

C．321D．239

[成功破障]

用秦九韶算法求多项式f（x）＝x5＋0.11x3－0.15x－0.04当x＝0.3时的值．

[随堂即时演练]

1．在对16和12求最大公约数时，整个操作如下：

16－12＝4,12－4＝8,8－4＝4.由此可以看出12和16的最大公约数是（　　）

A．4B．12

C．16D．8

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

A．－4B．－1

C．5D．6

3．将51化为二进制数得________．

4．用辗转相除法求294和84的最大公约数时，需要做除法的次数是________．

5．将1234（5）转化为八进制数．

参考答案

知识一

问题1：

提示：

短除法．

问题2：

提示：

数值太大，短除法不方便用．

问题3：

提示：

有．

知识二

问题1：

求f

（1）．

问题2：

提示：

运算量太大，不易运算．

问题3：

提示：

有．可将f（x）转化为求一次多项式的值．

知识三

问题1：

提示：

20天后是星期一．

问题2：

提示：

其实一周七天，与十进制一样，相当于逢七进一，是七进制论法．

[例1]解：

（1）辗转相除法：

779＝209×3＋152，

209＝152×1＋57，

152＝57×2＋38，

57＝38×1＋19，

38＝19×2.

所以，779与209的最大公约数为19.

（2）更相减损术：

779－209＝570，　　　　152－57＝95，

570－209＝361,95－57＝38，

361－209＝152,57－38＝19，

209－152＝57,38－19＝19.

所以779和209的最大公约数为19.

[活学活用]

【解析】选B　辗转相除法：

1515＝600×2＋315；600＝315×1＋285,315＝285×1＋30,285＝30×9＋15,30＝15×2故最大公约数为15，且需计算5次．用更相减损术法：

1515－600＝915,9－15－600＝315,600－315＝285，315－285＝30,285－30＝255,255－30＝225，225－30＝195,195－30＝165,165－30＝135,135－30＝105，105－30＝75,75－30＝45,45－30＝15,30－15＝15.故最大公约数为15，且需计算14次.

【答案】B

[例2]

（1）【解析】将多项式改写成如下形式：

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.

【答案】D

（2）解：

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

当x＝2时，有

v0＝6，

v1＝6×2＋5＝17，

v2＝17×2＋4＝38，

v3＝38×2＋3＝79，

v4＝79×2＋2＝160，

v5＝160×2＋1＝321，

v6＝321×2＝642，

故当x＝2时，多项式f（x）＝6x6＋5x5＋4x4＋3x3＋2x2＋x的值为642.

[活学活用]

【解析】选A　f（x）＝（（（（（3x＋4）x＋5）x＋6）x＋7）x＋8）x＋1，所以需要进行6次乘法和6次加法.

【答案】A

[例3]解：

（1）101111011

（2）＝1×28＋0×27＋1×26＋1×25＋1×24＋1×23＋0×22＋1×21＋1×20＝

379（10）．

（2）235（7）＝2×72＋3×71＋5×70＝124（10）．

（3）

∴137（10）＝345（6）．

（4）53（8）＝5×81＋3×80＝43（10）．

∴53（8）＝101011

（2）．

[活学活用]

解：

因为13m502（6）

＝1×65＋3×64＋m×63＋5×62＋0×61＋2×60

＝216m＋11846，

令216m＋11846＝12710，

所以m＝4.

典例【解析】原多项式可化为：

∵f（x）＝（（（（x＋0）x＋1）x＋1）x＋1）x＋1

当x＝3时

v0＝1，v1＝1×3＋0＝3，v2＝3×3＋1＝10，

v3＝10×3＋1＝31，v4＝31×3＋1＝94，

v5＝94×3＋1＝283.

所以，当x＝3时f（3）＝283.

【答案】B

[易错防范]

当多项式中间出现空项时，用秦九韶算法求函数值要补上系数为0的相应项，否则，本题极易出现如下所示的错误算法，从而误选A.

∵f（x）＝（（（x＋1）x＋1）x＋1）x＋1，

∴当x＝3时，

v0＝1，v1＝3＋1＝4，

v2＝4×3＋1＝13，

v3＝13×3＋1＝40，

v4＝40×3＋1＝120＋1＝121，

所以当x＝3时，f（3）＝121.

[成功破障]

解：

根据秦九韶算法，将f（x）写为：

f（x）＝（（（（x＋0）x＋0.11）x＋0）x－0.15）x－0.04.

按照从内到外的顺序，依次计算一次多项式当x＝0.3时的值；

v0＝1

v1＝v0×0.3＋0＝0.3；

v2＝v1×0.3＋0.11＝0.2；

v3＝v2×0.3＋0＝0.06；

v4＝v3×0.3－0.15＝－0.132；

v5＝v4×0.3－0.04＝－0.0796.

所以，当x＝0.3时，多项式的值为－0.0796.

1.【解析】选A　根据更相减损术的方法判断．

【答案】A

2.【解析】选D　n＝4，a4＝2，a3＝－3，a2＝1，a1＝2，a0＝1，由秦九韶算法的递推关系式得v0＝2，v1＝v0x＋a3＝－5，v2＝v1x＋a2＝6.

【答案】D

3.【解析】

【答案】110011

（2）

4.【解析】294＝84×3＋42，84＝42×2.

【答案】2

5.解：

将1234（5）转化为十进制数：

1234（5）＝1×53＋2×52＋3×51＋4×50＝194.

再将十进制数194转化为八进制数：

所以1234（5）＝302（8）．