搜索
1.3算法案例(1)如何求a，b，c的最大公约数？(2)如何求两个数的最小公倍数？[新知初探]1．辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．(2)辗转相除法的算法步骤：第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，m＝n，n＝r.第四步，若r＝0，则m，n的最大公约数等于m；否则，返回第二步．2．更相减损术(1)更相减损术是我国古代数学专著《九章算术》中介绍的一种求两个正整数的最大公约数的算法．(2)其基本过程是：第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．[点睛]辗转相除法与更相减损术的区别与联系预习课本P34～45，思考并完成以下问题两种方法辗转相除法更相减损术计算法则除法减法终止条件余数为0减数与差相等最大公约数的选取最后一步中的除数最后一步中的减数计算特点步骤较少，运算复杂步骤较多，运算简单相同点同为求两个正整数最大公约数的方法，都是递归过程3．秦九韶算法把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：f(x)＝(…((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)的值的方法叫秦九韶算法．[小试身手]1．用更相减损术求98与63的最大公约数时，需做减法的次数为()A．4B．5C．6D．7解析：选C(98,63)→(35,63)→(35,28)→(7,28)→(7,21)→(7,14)→(7,7)，∴共进行6次减法．2．用“辗转相除法”求得168与486的最大公约数是()A．3B．4C．6D．16解析：选C486＝168×2＋150,168＝150×1＋18,150＝18×8＋6,18＝3×6，故168与486的最大公约数为6.3．有关辗转相除法下列说法正确的是()A．它和更相减损之术一样是求多项式值的一种方法B．基本步骤是用较大的数m除以较小的数n得到除式m＝nq＋r，直至rn为止C．基本步骤是用较大的数m除以较小的数n得到除式m＝nq＋r(0≤rn)，反复进行，直到r＝0为止D．以上说法皆错解析：选C辗转相除法和更相减损之术都是求最大公约数的方法，故A错，而C中0≤rn且除到r＝0为止，C对．B错，故选C.4．已知多项式f(x)＝4x5＋3x4＋2x3－x2－x－12，用秦九韶算法求f(－2)等于()A．－1972B.1972C.1832D．－1832解析：选A∵f(x)＝((((4x＋3)x＋2)x－1)x－1)x－12，∴f(－2)＝－1972.求最大公约数[典例]求228与1995的最大公约数．[解]法一：(辗转相除法)1995＝8×228＋171,228＝1×171＋57,171＝3×57，所以228与1995的最大公约数为57.法二：(更相减损术)1995－228＝1767,1767－228＝1539，1539－228＝1311,1311－228＝1083，1083－228＝855,855－228＝627，627－228＝399,399－228＝171，228－171＝57,171－57＝114，114－57＝57.所以228与1995的最大公约数为57.辗转相除法计算次数少，步骤简捷，更相减损术计算次数多，步骤复杂，但是更相减损术每一步的计算都是减法，比做除法运算要简单一些，一般当数较小时可以考虑用更相减损术，当数较大时可以考虑用辗转相除法．[活学活用]用辗转相除法和更相减损术求1515与600的最大公约数，需要运算的次数分别为()A．4,15B．5,14C．5,13D．4,12解析：选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,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.故最大公约数为15，且需计算14次.秦九韶算法的应用[典例]用秦九韶算法求多项式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.应用秦九韶算法计算多项式的值应注意的3个问题(1)要正确将多项式的形式进行改写．(2)计算应由内向外依次计算．(3)当多项式函数中间出现空项时，要以系数为零的齐次项补充．[活学活用]用秦九韶算法写出当x＝3时，f(x)＝2x5－4x3＋3x2－5x＋1的值．解：因为f(x)＝((((2x＋0)x－4)x＋3)x－5)x＋1，v0＝2，v1＝2×3＋0＝6，v2＝6×3－4＝14，v3＝14×3＋3＝45，v4＝45×3－5＝130，v5＝130×3＋1＝391，所以f(3)＝391.进位制[典例](1)把二进制数101101(2)化为十进制数为________．(2)将十进制数458转化为四进制数为________．(3)比较85(9)和210(6)的大小．[解析](1)101101(2)＝1×25＋0×24＋1×23＋1×22＋0×21＋1×20＝32＋8＋4＋1＝45，所以二进制数101101(2)转化为十进制的数为45.(2)所以458＝13022(4)．答案：(1)45(2)13022(4)(3)解：因为85(9)＝5＋8×9＝77，210(6)＝0＋1×6＋2×62＝78，而7877，所以210(6)85(9)．十进制数转化为其他进制数的方法步骤[活学活用](1)将101111011(2)转化为十进制的数；(2)将235(7)转化为十进制的数；(3)将137(10)转化为六进制的数；(4)将53(8)转化为二进制的数．解：(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)．[层级一学业水平达标]1．用辗转相除法求294和84的最大公约数时，需要做除法运算的次数是()A．1B．2C．3D．4解析：选B294＝84×3＋42,84＝42×2，故需要做2次除法运算．2．三位四进制数中的最大数等于十进制数的()A．63B．83C．189D．252解析：选A三位四进制数中的最大数为333(4)，则333(4)＝3×42＋3×41＋3＝63.3．把389化为四进制数，则该数的末位是()A．1B．2C．3D．4解析：选A由389＝4×97＋1,97＝4×24＋1,24＝4×6＋0,6＝4×1＋2,1＝4×0＋1,389化为四进制数的末位是第一个除法代数式中的余数1.4．在对16和12求最大公约数时，整个操作如下：16－12＝4,12－4＝8,8－4＝4.由此可以看出12和16的最大公约数是()A．4B．12C．16D．8解析：选A根据更相减损术的方法判断．[层级二应试能力达标]1．4830与3289的最大公约数为()A．23B．35C．11D．13解析：选A4830＝1×3289＋1541；3289＝2×1541＋207；1541＝7×207＋92；207＝2×92＋23；92＝4×23；∴23是4830与3289的最大公约数．2．用辗转相除法求72与120的最大公约数时，需要做除法次数为()A．4B．3C．5D．6解析：选B120＝72×1＋48，72＝48×1＋24，48＝24×2.3．用更相减损术求459与357的最大公约数，需要做减法的次数为()A．4B．5C．6D．7解析：选B459－357＝102,357－102＝255,255－102＝153,153－102＝51,102－51＝51，所以459与357的最大公约数为51，共做减法5次．4．下列各数，化为十进制后，最大的为()A．101010(2)B．111(5)C．32(8)D．54(6)解析：选A101010(2)＝1×25＋0×24＋1×23＋0×22＋1×21＋0×20＝42,111(5)＝1×52＋1×51＋1×50＝31,32(8)＝3×81＋2×80＝26,54(6)＝5×61＋4×60＝34.故转化为十进制后，最大的是101010(2)．5.阅读程序框图，利用秦九韶算法计算多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0，当x＝x0时，框图中A处应填入________．解析：f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0，先用秦九韶算法改为一次多项式，f(x)＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0.f1＝an；k＝1，f2＝f1x0＋an－1；k＝2，f3＝f2x0＋an－2；…；归纳得第k次fk＋1＝fkx0＋an－k.故A处应填an－k.答案：an－k6．三进制数2012(3)化为六进制数为abc(6)，则a＋b＋c＝________.解析：2012(3)＝2×33＋0×32＋1×31＋2×30＝59.三进制数2012(3)化为六进制数为135(6)，∴a＋b＋c＝9.答案：97．三位七进制数表示的最大的十进制数是________．解析：最大的三位七进制数表示的十进制数最大，最大的三位七进制数为666(7)，则666(7)＝6×72＋6×71＋6×70＝342.答案：3428．10x1(2)＝y02(3)，求数字x，y的值．解：∵10x1(2)＝1×20＋x×21＋0×22＋1×23＝9＋2x，y02(3)＝2×30＋y×32＝9y＋2，∴9＋2x＝9y＋2且x∈{}0，1，y∈{}0，1，2，所以x＝1，y＝1.9．用秦九韶算法计算多项式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，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.(时间120分钟，满分150分)[对应配套卷P73]一、选择题(本大题共12小题，每小题5分，共60分．在每小题给出的四个选项中，只有一项是符合题目要求的)1．下列关于赋值语句的说法错误的是()A．赋值语句先计算出赋值号右边的表达式的值B．赋值语句是把左边变量的值赋给赋值号右边的表达式C．赋值语句是把右边表达式的值赋给赋值号左边的变量D．在算法语句中，赋值语句是最基本的语句解析：选B赋值语句的一般格式是：变量名＝表达式，其作用