必修三-第一章-1.3-算法案例导学案

[学习目标]理解辗转相除法与更相减损术的含义，了解其执行过程.理解秦九韶算法的计算过程，并了解它提高计算效率的实质.理解进位制的概念，能进行不同进位制间的转化.4.了解进位制的程序框图和程序．知识点一辗转相除法与更相减损术1．辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．(2)辗转相除法的算法步骤第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，m＝n，n＝r.第四步，若r＝0，则m，n的最大公约数等于m；否则，返回第二步．2．更相减损术第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．3．辗转相除法和更相减损术的区别与联系：名称辗转相除法更相减损术区别(1)以除法为主；(2)两个整数的差值较大时，运算次数较少；(3)相除，余数为0时得结果(1)以减法为主；(2)两个整数的差值较大时，运算次数较多；(3)相减，减数与差相等时得结果；(4)相减前要进行是否都是偶数的判断联系(1)都是求两个正整数最大公约数的方法；(2)二者的实质都是递归的过程；(3)二者都要用循环结构来实现思考实际应用更相减损术时要做的第一步工作是什么？答先判断a，b是否为偶数，若是，都除以2再进行．知识点二秦九韶算法1．秦九韶算法简介(1)秦九韶算法要解决的问题是求多项式的值．(2)秦九韶算法的特点：通过一次式的反复计算，逐步得到高次多项式的值，即将一个n次多项式的求值问题归结为重复计算n个一次多项式的值的问题．(3)秦九韶算法的原理：将f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写为：f(x)＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0＝…先计算最内层括号内一次多项式的值，即v1＝anx＋an－1，再由内向外逐层计算一次多项式vk的值．2．秦九韶算法的操作方法(1)算法步骤如下：第一步，输入多项式次数n、最高次项的系数an和x的值．第二步，将v的值初始化为an，将i的值初始化为n－1.第三步，输入i次项的系数ai.第四步，v＝vx＋ai，i＝i－1.第五步，判断i是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v.(2)程序框图如图所示．(3)程序如下：INPUT“n＝”；nINPUT“an＝”；aINPUT“x＝”；xv＝ai＝n－1WHILEi＞＝0PRINT“i＝”；iINPUT“ai＝”；av＝v*x＋ai＝i－1WENDPRINTvEND知识点三进位制1．进位制的概念进位制是为了计数和运算方便而约定的记数系统，约定“满几进一”就是几进制，几进制的基数(大于1的整数)就是几．2．常见的进位制(1)二进制：①只使用0和1两个数学；②满二进一，即1＋1＝10(2)．(2)八进制；①使用0,1,2,3,4,5,6,7这八个不同数学；②满八进一，即7＋1＝10(8)．思考任何进位制中都要用到的数字是什么？答0和1.题型一求两个正整数的最大公约数例1分别用辗转相除法和更相减损术求261和319的最大公约数．解方法一(辗转相除法)319÷261＝1(余58)，261÷58＝4(余29)，58÷29＝2(余0)，所以319与261的最大公约数为29.方法二(更相减损术)319－261＝58，261－58＝203，203－58＝145，145－58＝87，87－58＝29，58－29＝29，29－29＝0，所以319与261的最大公约数是29.反思与感悟(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数．若是，用2约简．也可以不除以2，直接求最大公约数，这样不影响最后结果．跟踪训练1用辗转相除法求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.题型二秦九韶算法的应用例2用秦九韶算法求多项式f(x)＝x5＋5x4＋10x3＋10x2＋5x＋1当x＝－2时的值．解f(x)＝x5＋5x4＋10x3＋10x2＋5x＋1＝((((x＋5)x＋10)x＋10)x＋5)x＋1.当x＝－2时，有v0＝1；v1＝v0x＋a4＝1×(－2)＋5＝3；v2＝v1x＋a3＝3×(－2)＋10＝4；v3＝v2x＋a2＝4×(－2)＋10＝2；v4＝v3x＋a1＝2×(－2)＋5＝1；v5＝v4x＋a0＝1×(－2)＋1＝－1.故f(－2)＝－1.反思与感悟(1)先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可．这样比直接将x＝－2代入原式大大减少了计算量．若用计算机计算，则可提高运算效率．(2)注意：当多项式中n次项不存在时，可将第n次项看作0·xn.跟踪训练2用秦九韶算法计算多项式f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64当x＝2时的值．解根据秦九韶算法，把多项式改写成如下形式：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.所以当x＝2时，多项式的值为0.题型三进位制之间的互化例3(1)把二进制数1110011(2)化为十进制数．(2)将8进制数314706(8)化为十进制数．解(1)1110011(2)＝1×26＋1×25＋1×24＋0×23＋0×22＋1×21＋1＝115.(2)314706(8)＝3×85＋1×84＋4×83＋7×82＋0×81＋6×80＝104902.所以，化为十进制数是104902.反思与感悟(1)将k进制转化为十进制的方法是：先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式，再按照十进制的运算规则计算出结果．(2)十进制转化为k进制，采用除k取余法，也就是除基数，倒取余．跟踪训练3将53(8)转化为二进制数．解先将八进制数53(8)转化为十进制数：53(8)＝5×81＋3×80＝43；再将十进制数43转化为二进制数：所以53(8)＝101011(2)．转化与化归思想例4下列各数中，最小的数是()A．85(9) B．210(6)C．1000(4) D．111111(2)分析先将它们转化为十进制数，再进行比较．解析85(9)＝8×9＋5＝77,210(6)＝2×62＋1×6＋0＝78,1000(4)＝1×43＝64,111111(2)＝1×25＋1×24＋1×23＋1×22＋1×2＋1＝63.故最小的是63.答案D解后反思合理的转化是解题的关键．对于进位制之间的转化问题，一般要先把k进制数转化为十进制数，再转化为其他进制数．数制转化方法掌握不牢致错例5把十字进制数49化为二进制数．分析对进位制间的换算，要弄清解题的办法，将十进制数转化为k进制数用“除k取余法”．解所以49＝110001(2)．解后反思本例常出现的错误是把上式中各步所得的余数从上到下排列，这是基本方法掌握不牢造成的，应加以注意．1．1337与382的最大公约数是()A．3B．382C．191D．201答案C解析利用辗转相除法，1337＝382×3＋191,382＝191×2，故两数的最大公约数为191.2．把189化为三进制数，则末位数字是()A．0B．1C．2D．3答案A解析采用“除k取余法”，得即189＝21000(3)3．用秦九韶算法求n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0当x＝x0时的值，求f(x0)需要乘方、乘法、加法的次数分别为()A.eq\f(nn＋1,2)，n，nB．n,2n，nC．0,2n，n D．0，n，n答案D解析因为f(x)＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，所以乘方、乘法、加法的次数分别为0，n，n.4．用秦九韶算法求多项式f(x)＝7x6＋6x5＋3x2＋2，当x＝4时的值时，先算的是()A．4×4＝16 B．7×4＝28C．4×4×4＝64 D．7×4＋6＝34答案D解析因为f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，所以用秦九韶算法求多项式f(x)＝7x6＋6x5＋3x2＋2当x＝4时的值时，先算的是7×4＋6＝34.5．用更相减损术求36与134的最大公约数，第一步应为________．答案先除以2，得到18与67解析∵36与134都是偶数，∴第一步应为：先除以2，得到18与67.1.求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术．用辗转相除法，即根据a＝nb＋r这个式子，反复相除，直到r＝0为止；用更相减损术，即根据r＝|a－b|这个式子，反复相减，直到r＝0为止．2．秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行．3．把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数．而在使用除k取余法时要注意以下几点：(1)必须除到所得的商是0为止；(2)各步所得的余数必须从下到上排列；(3)切记在所求数的右下角标明基数．一、选择题1．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.2．用秦九韶算法计算多项式f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1当x＝0.4时的值时，需要做乘法和加法的次数分别是()A．6,6B．5,6C．5,5D．6,5答案A解析秦九韶算法中最多需用加法和乘法的次数是由多项式的次数n可知，故选A.3．两个二进制数101(2)与110(2)的和用十进制数表示为()A．12B．11C．10D．9答案B解析101(2)＝1×22＋0×21＋1×20＝5,110(2)＝1×22＋1×21＋0×20＝6.4．三位七进制数中的最大数表示的十进制的数是()A．322B．402C．342D．365答案C解析三位七进制数中的最大数为666(7)，则转化为十进制为666(7)＝6×72＋6×71＋6×70＝294＋42＋6＝342.5．下列四个数最大的是()A．322(7)B．402(6)C．342(7) D．355(6)答案C解析342(7)＝3×72＋4×7＋2＝177，402(6)＝4×62＋0×6＋2＝146.所以342(7)＞402(6)．而342(7)＞322(7)，402(6)＞355(6)，所以最大的数是342(7)6．用秦九韶算法计算f(x)＝6x5－4x4＋x3－2x2－9x，需要加法(或减法)与乘法运算的次数分别为()A．5,4B．5,5C．4,4 D．4,5答案D解析n次多项式，当最高次项的系数不为1时，需进行n次乘法；若各项均不为0，则需进行n次加法(或减法)，缺一项就减少一次加法(或减法)运算，而这个5次多项式的5次项系数不为1，缺常数项，因而乘法次数为5，加法(或减法)次数为5－1＝4.故选D.二、填空题8．用辗转相除法计算60和48的最大公约数，需要做的除法次数是________．答案2解析60＝48×1＋12,48＝12×4，故需做2次除法．9．用更相减损术求459和357的最大公约数，需进行减法的次数为________．答案5解析利用更相减损术，有459－357＝102,357－102＝255,255－102＝153,153－102＝51,102－51＝51，共进行了5次减法．10．378和90的最大公约数为________．答案18解析辗转相除法：378＝90×4＋18,90＝18×5＋0，∴378与90的最大公约数是18.11．用秦九韶算法求多项式f(x)＝2＋0.35x＋1.8x2－3x3＋6x4－5x5＋x6当x＝－1时的值时，令v0＝a6，v1＝v0x＋a5，…，v6＝v5x＋a0，则v3的值是________．答案－15解析f(x)＝x