算法案例.docx

算法案例.docx

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

算法案例

1.3　算法案例

1．会用辗转相除法与更相减损术求两个数的最大公约数．（易错易混点）

2．会用秦九韶算法求多项式的值．（难点）

3．会在不同进位制间进行相互转化．（重点）

[基础·初探]

教材整理1　辗转相除法与更相减损术

阅读教材P34～P36例1前的内容，完成下列问题．

1．辗转相除法

（1）辗转相除法是用于求两个正整数的最大公约数的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法．

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

2．更相减损术

更相减损术是我国古代数学专著《九章算术》中介绍的一种求两数最大公约数的方法．其基本过程是：

第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数或这个数与约简的数的乘积就是所求的最大公约数．

（1）228与1995的最大公约数是________．

（2）18与30的最大公约数是________．

【解析】　

（1）1995＝228×8＋171，

228＝171×1＋57，

171＝57×3，

∴57是228与1995的最大公约数．

（2）30－18＝12，

18－12＝6，

12－6＝6，

∴18与30的最大公约数是6.

【答案】　

（1）57　

（2）6

教材整理2　秦九韶算法

阅读教材P37～P38例2前的内容，完成下列问题．

求多项式f（x）＝anxn＋an－1xn－1＋…＋a1x＋a0的值时，常用秦九韶算法，这种算法的运算次数较少，是多项式求值比较先进的算法，其实质是转化为求n个一次多项式的值，共进行n次乘法运算和n次加法运算．其过程是：

改写多项式为：

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.

设计程序框图，用秦九韶算法求多项式的值，所选用的结构是（　　）

A．顺序结构　　　　　　B．条件结构

C．循环结构D．以上都有

【解析】　根据秦九韶算法的含义知选D.

【答案】　D

教材整理3　进位制

阅读教材P40的内容，完成下列问题．

1．进位制是人们为了计数和运算方便而约定的记数系统．“满k进一”就是k进制，k进制的基数是k.

2．将k进制数化为十进制数的方法是：

先把k进制数写成各位上的数字与k的幂的乘积之和的形式，再按照十进制数的运算规则计算出结果．

3．将十进制数化为k进制数方法是：

除k取余法．即用k连续去除十进制数所得的商，直到商为零为止，然后把各步得到的余数倒排写出就是相应的k进制数．

判断（正确的打“√”，错误的打“×”）

（1）五进制的基数是5，用0,1,2,3,4,5六个数字表示．（　　）

（2）秦九韶算法的优点是减少了乘法运算的次数，提高了运算效率．（　　）

（3）用秦九韶算法可以求两个正整数的最大公约数．（　　）

（4）不同进位制中，十进制的数比二进制的数大．（　　）

【答案】　

（1）×　

（2）√　（3）×　（4）×

[小组合作型]

求最大公约数

（1）98,280的最大公约数为（　　）

A．7　B．14

C．16D．8

（2）用更相减损术求得78与36的最大公约数为________．

【精彩点拨】　求两个数的最大公约数可用辗转相除法，也可用更相减损术．

【尝试解答】　

（1）由辗转相除法可得：

280＝98×2＋84,98＝84×1＋14,84＝14×6.故最大公约数为14.也可以使用更相减损术或短除法．

（2）78－36＝42,42－36＝6,36－6＝30，

30－6＝24,24－6＝18,18－6＝12，

12－6＝6.

【答案】　

（1）B　

（2）6

1．求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术．用辗转相除法，即根据a＝nb＋r这个式子，反复相除，直到r＝0为止；用更相减损术，即根据r＝|a－b|这个式子，反复相减，直到r＝0为止．

2．当两个整数的差较大时，用辗转相除法计算的次数较少．

[再练一题]

1．用辗转相除法求78与36的最大公约数．

【解】　由辗转相除法得，

78＝36×2＋6，

36＝6×6，

故78与36的最大公约数是6.

秦九韶算法

　已知一个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.

1．先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可．这样比直接将x＝2代入原式大大减少了计算量．若用计算机计算，则可提高运算效率．

2．注意：

当多项式中n次项不存在时，可将第n项看作0·xn.

[再练一题]

2．用秦九韶算法计算f（x）＝6x5－4x4＋x3－2x2－9x，需要加法（或减法）与乘法运算的次数分别为（　　）

A．5,4　　　　B．5,5　　　　

C．4,4　　　　D．4,5

【解析】　n次多项式需进行n次乘法；若各项均不为零，则需进行n次加法，缺一项就减少一次加法运算．f（x）中无常数项，故加法次数要减少一次，为5－1＝4.故选D.

【答案】　D

[探究共研型]

进位制及其转化

探究1　常见进位制有哪些？

【提示】　

（1）十进制使用0,1,2,3,4,5,6,7,8,9这十个数字，基数为10.

（2）二进制使用0和1这两个数字，基数为2.

（3）八进制使用0,1,2,3,4,5,6,7这八个数字，基数为8.

（4）十六进制使用0,1,2,3,4,5,6,7,8,9，A，B，C，D，E，F这十六个符号，基数为16.其中A，B，C，D，E，F分别相当于十进制中的10,11,12,13,14,15.

探究2　两个非十进制的数之间怎样转化？

【提示】　两个非十进制的数之间的转化，可以先化成十进制数，再化成另一进制的数，即将十进制作为“桥梁”．

探究3　不同进位制的数能比较大小吗？

【提示】　进位制是人们为了计数和运算方便而约定的记数系统，不同进位制的数可以比较大小，一般转化成十进制数比较大小更方便．

探究4　进位制的原理是什么？

不同的进位制如何区分？

【提示】　

（1）十进制的原理是满十进一．一个十进制正整数N可以写成an·10n＋an－1·10n－1＋…＋a1·101＋a0·100的形式，其中an，an－1，…，a1，a0都是0至9中的数字，且an≠0.例如365＝3×102＋6×10＋5.

（2）一般地，k进制数的原理是满k进一，k进制数一般在右下角处标注（k），以示区别．例如270（8）表示270是一个8进制数．但十进制一般省略不写．

　把“五进制”数1234（5）转化为“十进制”数，再把它转化为“八进制”数.

【精彩点拨】　k进制化十进制时，利用求各位上的数与k的幂的乘积后再相加的方法，十进制化其他进制可采用除k取余法．

【尝试解答】　∵1234（5）＝1×53＋2×52＋3×51＋4×50＝194，而

∴1234（5）＝194（10）＝302（8）．

把一个非十进制转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数.而在使用除k取余法时要注意以下几点：

（1）必须除到所得的商是0为止；

（2）各步所得的余数必须从下到上排列；

（3）切记在所求数的右下角标明基数.

[再练一题]

3．210（6）化成十进制数为________，85化成七进制数为________.

【解析】　210（6）＝2×62＋1×6＝78，

所以85＝151（7）．

【答案】　78　151（7）

秦九韶算法中的运算次数

直接法乘法运算的次数最多可达

，加法最多n次，秦九韶算法通过转化把乘法运算的次数减少到最多n次，加法最多n次．

　已知f（x）＝x5＋2x4＋3x3＋4x2＋5x＋6，用秦九韶算法求这个多项式当x＝2时的值时，做了几次乘法？

几次加法？

【尝试解答】　在v1中虽然“v1＝2＋2＝4”，而计算机还是做了1次乘法“v1＝2×1＋2＝4”．因为用秦九韶算法计算多项式f（x）＝anxn＋an－1xn－1＋…＋a1x＋a0当x＝x0时的值时，首先将多项式改写成f（x）＝（…（anx＋an－1）x＋…＋a1）x＋a0，然后再计算v1＝anx＋an－1，v2＝v1x＋an－2，v3＝v2x＋an－3，…，vn＝vn－1x＋a0.无论an是不是1，这次的乘法都是要进行的．由以上分析，共做了5次乘法，5次加法．

[再练一题]

4．用秦九韶算法求多项式f（x）＝4x5－x2＋2当x＝3时的值时，需要进行的乘法运算和加法运算的次数分别为（　　）

A．4,2　　　　B．5,3　　　　

C．5,2　　　　D．6,2

【解析】　f（x）＝4x5－x2＋2＝（（（（4x）x）x－1）x）x＋2，需5次乘法运算和2次加法运算．

【答案】　C

1．490和910的最大公约数为（　　）

A．2　　　B．10　　　

C．30　　　D．70

【解析】　910＝490×1＋420,490＝420×1＋70,420＝70×6，故最大公约数为70.

【答案】　D

2．用更相减损术求294和84的最大公约数时，需做减法的次数是（　　）

A．2B．3

C．4D．5

【解析】　294－84＝210,210－84＝126,126－84＝42,84－42＝42.

【答案】　C

3．下列有可能是4进制数的是（　　）

A．5123B．6542

C．3103D．4312

【解析】　4进制数每位上的数字一定小于4，

故选C.

【答案】　C

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

【解析】　

【答案】　110011

（2）

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

【解】　原多项式可化为：

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

学业分层测评（八）　算法案例

（建议用时：

45分钟）

[学业达标]

一、选择题

1．关于进位制说法错误的是（　　）

A．进位制是人们为了计数和运算方便而约定的记数系统

B．二进制就是满二进一，十进制就是满十进一

C．满几进一，就是几进制，几进制的基数就是几

D．为了区分不同的进位制，必须在数的右下角标注基数

【解析】　一般情况下，不同的进位制须在数的右下角标注基数，但十进制可以不用标注，所以不是必须在数的右下角标注基数，所以D错误．

【答案】　D

2．下列四个数中，数值最小的是（　　）

A．25（10）　　　B．54（4）　　

C．10110

（2）　　D．10111

（2）

【解析】　统一成十进制，B中，54（4）＝5×41＋4＝24.C中，10110

（2）＝1×24＋1×22＋2＝22.D中，10111

（2）＝23.

【答案】　C

3．用更相减损术求1515和600的最大公约数时，需要做减法次数是（　　）

A．15　B．14

C．13D．12

【解析】　1515－600＝915,915－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.

∴1515与600的最大公约数是15，则共做14次减法．

【答案】　B

4．计算机中常用的十六进制是逢16进1的计数制，采用数字0～9和字母A～F共16个计数符号，这些符号与十进制数的对应关系如下表：

十六进制

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

十进制

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

例如，用十六进制表示：

E＋D＝1B，则A×B等于（　　）

A．6EB．72

C．5FD．B0

【解析】　A×B用十进制表示10×11＝110，而110＝6×16＋14，所以用16进制表示6E.

【答案】　A

5．以下各数有可能是五进制数的是（　　）

A．15B．106

C．731D．21340

【解析】　五进制数中各个数字均是小于5的自然数，故选D.

【答案】　D

二、填空题

6．用更相减损术求36与134的最大公约数，第一步应为________．　

【解析】　∵36与134都是偶数，∴第一步应为：

先除以2，得到18与67.

【答案】　先除以2，得到18与67

7．用秦九韶算法求f（x）＝2x3＋x－3当x＝3时的值v2＝________.

【解析】　f（x）＝（（2x＋0）x＋1）x－3，

v0＝2；

v1＝2×3＋0＝6；

v2＝6×3＋1＝19.

【答案】　19

8．将八进制数127（8）化成二进制数为________．

【解析】　先将八进制数127（8）化为十进制数：

127（8）＝1×82＋2×81＋7×80＝64＋16＋7＝87，

再将十进制数87化成二进制数：

∴87＝1010111

（2），

∴127（8）＝1010111

（2）．

【答案】　1010111

（2）

三、解答题

9．用更相减损术求288与153的最大公约数．

【解】　288－153＝135,153－135＝18,135－18＝117,117－18＝99,99－18＝81,81－18＝63,63－18＝45,45－18＝27,27－18＝9,18－9＝9.

因此288与153的最大公约数为9.

10．用秦九韶算法计算多项式f（x）＝x6－12x5＋60x4－160x3＋240x2－192x＋64，当x＝2时的值．

【解】　将f（x）改写为

f（x）＝（（（（（x－12）x＋60）x－160）x＋240）x－192）x＋64，

由内向外依次计算一次多项式当x＝2时的值，

v0＝1，

v1＝1×2－12＝－10，

v2＝－10×2＋60＝40，

v3＝40×2－160＝－80，

v4＝－80×2＋240＝80，

v5＝80×2－192＝－32，

v6＝－32×2＋64＝0.

所以f

（2）＝0，即x＝2时，原多项式的值为0.

[能力提升]

1．下面一段程序的目的是（　　）

A．求m，n的最小公倍数

B．求m，n的最大公约数

C．求m被n除的商

D．求n除以m的余数

【解析】　本程序当m，n不相等时，总是用较大的数减去较小的数，直到相等时跳出循环，显然是“更相减损术”．故选B.

【答案】　B

2．若k进制数123（k）与十进制数38相等，则k＝________.

【解析】　由k进制数123可知k≥4.下面可用验证法：

若k＝4，则38（10）＝212（4），不合题意；若k＝5，则38（10）＝123（5）成立，所以k＝5.

或者123（k）＝1×k2＋2×k＋3＝k2＋2k＋3，∴k2＋2k＋3＝38，k2＋2k－35＝0，k＝5（k＝－7＜0舍去）．

【答案】　5

3．若二进制数10b1

（2）和三进制数a02（3）相等，求正整数a，b.

【解】　∵10b1

（2）＝1×23＋b×2＋1＝2b＋9，

a02（3）＝a×32＋2＝9a＋2，

∴2b＋9＝9a＋2，即9a－2b＝7.

∵a∈{1,2}，b∈{0,1}，

∴当a＝1时，b＝1，符合题意；

当a＝2时，b＝

，不符合题意．

∴a＝1，b＝1.

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

【解】　根据秦九韶算法，把多项式改写成如下形式：

f（x）＝8x7＋5x6＋0·x5＋3·x4＋0·x3＋0·x2＋2x＋1

＝（（（（（（8x＋5）x＋0）x＋3）x＋0）x＋0）x＋2）x＋1.

而x＝2，所以有

v0＝8，

v1＝8×2＋5＝21，

v2＝21×2＋0＝42，

v3＝42×2＋3＝87，

v4＝87×2＋0＝174，

v5＝174×2＋0＝348，

v6＝348×2＋2＝698，

v7＝698×2＋1＝1397.

所以当x＝2时，多项式的值为1397.