搜索
第一章算法初步1．3算法案例[学习目标]1.会用辗转相除法与更相减损术求两个数的最大公约数(易错点、易混点)．2.会用秦九韶算法求多项式的值(难点)．3.会进行不同进位制之间的数的转化(重点、难点)．[知识提炼·梳理]1．辗转相除法与更相减损术(1)辗转相除法：又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．(2)更相减损术：我国古代数学专著《九章算术》中介绍的一种求两个正整数的最大公约数的算法．2．秦九韶算法功能它是一种用于计算一元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.这样，求n次多项式f(x)的值就转化为求n个一次多项式的值3.进位制(1)进位制．进位制是人们为了计数和运算方便而约定的记数系统，“满几进一”就是几进制，几进制的基数就是几．(2)其他进位制与十进制间的转化．①其他进位制化成十进制．其他进位制的数化成十进制时，表示成不同位上数字与基数的幂的乘积之和的形式．②十进制化成k进制的方法——“除k取余法”．[思考尝试·夯基]1．思考判断(正确的打“√”，错误的打“×”)．(1)五进制的基数是5，用0，1，2，3，4，5六个数字表示．()(2)秦九韶算法的优点是减少了乘法运算的次数，提高了运算效率．()(3)用秦九韶算法可以求两个正整数的最大公约数．()(4)不同进位制中，十进制的数比二进制的数大．()答案：(1)×(2)√(3)×(4)×2．设计程序框图，用秦九韶算法求多项式的值，所选用的结构是()A．顺序结构B．条件结构C．循环结构D．以上都有解析：根据秦九韶算法的含义知选D.答案：D3．已知k进制数32501(k)，则k不可能是()A．5B．6C．7D．8解析：k进制数中各个数字均小于k，则k5.答案：A4．用辗转相除法求85与51的最大公约数时，需要做除法的次数为________．解析：85＝51×1＋34，51＝34×1＋17，34＝17×2＋0.答案：35．888与1147的最大公约数为________．解析：因为1147＝888×1＋259，888＝259×3＋111，259＝111×2＋37，111＝37×3，所以888和1147的最大公约数是37.答案：37类型1求最大公约数[典例1]用辗转相除法求840与1785的最大公约数．解：用辗转相除法求840和1785的最大公约数有：1785＝840×2＋105，840＝105×8.所以840和1785的最大公约数是105.归纳升华1．利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．2．利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数．若是，用2约简，也可以不除以2，直接求最大公约数，这样不影响最后结果．[变式训练]用更相减损术求612与468的最大公约数．解：首先612和468都是偶数，所以用2约简，得到306和234，还是偶数，需要再用2约简，得到153和117，最后用更相减损术计算得153－117＝36，117－36＝81，81－36＝45，45－36＝9，36－9＝27，27－9＝18，18－9＝9.所以612和468的最大公约数是9×2×2＝36.类型2用秦九韶算法求多项式的值[典例2]用秦九韶算法求多项式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.归纳升华当多项式中n次项不存在时，可将第n项看作0·xn.[变式训练]已知一个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不同进制的数之间的转化[典例3](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，而78＞77，所以210(6)＞85(9)．归纳升华1．把k进制数化为十进制数的方法是：先把这个k进制数写成用各位上的数字与k的幂的乘积之和的形式，再按照十进制数的运算法则计算出结果．2．将十进制数化为k进制数的方法是除k取余法，即用k连续地去除十进制数求商，直到商为0为止，然后将余数倒排写出，即得到所求的k进制数．3．把一个非十进制数转化为另一个非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，再把这个数转化为另一个非十进制数．[变式训练](1)已知一个k进制的数132(k)与十进制的数30相等，那么k的值为()A．－7或4B．－7C．4D．都不对(2)下列各数中最大的是()A．110(2)B．18C．16(8)D．20(5)解析：(1)132(k)＝1×k2＋3×k＋2＝k2＋3k＋2，所以k2＋3k＋2＝30，即k2＋3k－28＝0，解得k＝4或k＝－7(舍去)，所以k＝4.(2)110(2)＝1×22＋1×21＋0×20＝6；16(8)＝1×81＋6×80＝14；20(5)＝2×51＋0×50＝10.则最大数是18.答案：(1)C(2)B1．求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术．用辗转相除法，即根据a＝nb＋r这个式子，反复相除，直到r＝0为止；用更相减损术，即根据r＝|a－b|这个式子，反复相减，直到r＝0为止．2．秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行．3．不同进位制之间的转化．(1)k进制数转化为十进制数：写成k的方幂之和即可，即anan－1…a1a0(k)＝an×kn＋an－1×kn－1＋…＋a1×k＋a0.(2)十进制数转化为其他进制数：一般方法是除k取余法，即先用十进制数a除以k，商为a1，余数为r1，再用a1除以k，商为a2，余数为r2，…，反复进行这种除法，直到商为0为止，此时余数为rn，将所有余数按反向排列就得到k进制数rnrn－1…r1(k).