搜索
1.3算法案例【知识提炼】1.辗转相除法与更相减损术(1)辗转相除法：①辗转相除法：又叫_________算法，是一种求两个正整数的___________的古老有效的算法.欧几里得最大公约数②程序INPUTm，nDOr=________m=nn=rLOOPUNTILr=0PRINTmENDmMODn(2)更相减损术：①我国古代数学专著《九章算术》中介绍的一种求两个正整数的___________的算法.②运算过程第一步，任意给定两个正整数，判断它们是否都是偶数，若是，________；若不是，执行第二步.最大公约数用2约简第二步，以较大的数减去较小的数，接着把所得的差与_________比较，并以大数减小数.继续这个操作，直到所得的数_____为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.较小的数相等2.秦九韶算法功能计算n次多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值改写后的形式f(x)=anxn+an-1xn-1+…+a1x+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进制化为十进制的方法：anan-1…a1a0(k)=__________________________(an，an-1，…，a1，a0∈N，0ank，0≤an-1，…，a1，a0k).②十进制化为k进制的方法——__________.an×kn+an-1×kn-1+…+a1×k+a0除k取余法【即时小测】1.思考下列问题：(1)实际应用更相减损术时要做的第一步工作是什么?提示：先判断a，b是否为偶数，若是，都除以2再进行.(2)任何进位制中都要用到的数字是什么?提示：0和1.2.将101111011(2)转化为十进制的数为()A.376(10)B.377(10)C.378(10)D.379(10)【解析】选D.101111011(2)=1×28+0×27+1×26+1×25+1×24+1×23+0×22+1×21+1×20=379(10).3.用更相减损术可求得78与36的最大公约数是()A.3B.4C.6D.12【解析】选C.78=39×2，36=18×2，39-18=21，21-18=3，18-3=15，15-3=12，12-3=9，9-3=6，6-3=3，因此最大公约数为2×3=6.4.利用辗转相除法求3869与6497的最大公约数时，第二步是.【解析】第一步：6497=3869×1+2628第二步：3869=2628×1+1241.答案：3869=2628×1+12415.已知多项式f(x)=1+x+0.5x2+0.16667x3+0.04167x4+0.00833x5，用秦九韶算法求得f(-0.2)=.【解析】根据秦九韶算法，把多项式改写成如下形式：f(x)=((((0.00833x+0.04167)x+0.16667)x+0.5)x+1)x+1.按照从内到外的顺序依次计算一次多项式当x=-0.2时的值：v0=0.00833；v1=0.00833×(-0.2)+0.04167=0.040004；v2=0.040004×(-0.2)+0.16667=0.1586692；v3=0.1586692×(-0.2)+0.5=0.46826616；v4=0.46826616×(-0.2)+1=0.906346768；v5=0.906346768×(-0.2)+1=0.8187306464.所以当x=-0.2时，多项式的值为0.8187306464.答案：0.8187306464【知识探究】知识点1辗转相除法与更相减损术观察如图所示的内容，回答下列问题：问题1：用辗转相除法求两数的最大公约数的原理是什么?问题2：用更相减损术求最大公约数应按照怎样的步骤进行?【总结提升】1.辗转相除法的原理设m，n是两个正整数(不妨设mn)，(1)用m除以n，若商为q1，余数为r1(0≤r1n)，则m=n·q1+r1，显然若x是m和n的公约数，即x能整除m和n，则x也必然能整除r1，这样x也是n和r1的公约数，故求m和n的公约数就是求n和r1的公约数.(2)用n除以r1，得n=r1·q2+r2(0≤r2r1)，所以n和r1的公约数就是r1和r2的公约数，…，依次下去，由于mnr1r2…，所以到某一步必然有ri=ri+1·qi+2，即ri恰能被ri+1整除，这时ri+1是ri和ri+1的公约数，它也必然是ri-1和ri，ri-2和ri-1，…，r1与r2，n和r1，m和n的最大公约数.2.更相减损术求最大公约数的程序设计【知识拓展】更相减损术与辗转相除法的区别与联系辗转相除法更相减损术区别①以除法为主②两个整数差值较大时运算次数较少③相除余数为零时得结果①以减法为主②两个整数的差值较大时，运算次数较多③相减，差与减数相等得结果④相减前要做是否都是偶数的判断联系①都是求最大公约数的方法②二者的实质都是递归的过程③二者都要用循环结构来实现知识点2秦九韶算法观察如图所示内容，回答下列问题：问题1：秦九韶算法的计数原理是怎样的?问题2：应按照怎样的步骤进行秦九韶算法?【总结提升】1.秦九韶算法的计数原理秦九韶算法是按照从内到外的顺序依次计算求值的.设f(x)=anxn+an-1xn-1+…+a1x+a0，则该算法先计算v1=anx+an-1，再计算v2=v1x+an-2，…，最后计算vn=vn-1x+a0.2.秦九韶算法的步骤知识点3进位制观察如图所示内容，回答下列问题：问题1：进位制应如何表示?问题2：常见的进位制有哪些?【总结提升】1.进位制的表示若一个数为十进制数，则其基数可以省略不写，若是其他进位制的数，在没有特别说明的前提下，其基数必须写出，常在数的右下角标明基数.2.常见的进位制(1)二进制：①只使用0和1两个数字；②满二进一，如1+1=10(2).(2)八进制：①使用0，1，2，3，4，5，6，7八个不同的数字；②满八进一，如7+1=10(8).(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(16).【题型探究】类型一求最大公约数【典例】1.(2015·大同高一检测)用辗转相除法求378与90的最大公约数为.2.(2015·衡水高一检测)用更相减损术求294与84的最大公约数时，需做减法的次数是.3.求104与65的最大公约数.【解题探究】1.典例1中应将两数怎样进行相除?提示：应将294除以84，用较大的数除以较小的数依次进行.2.典例2中应用更相减损术时要做的第一步工作是什么?提示：由于294与84都是偶数，因此应先将两数都除以2再进行.3.典例3中如何探求两数的最大公约数?提示：可采用辗转相除法或更相减损术求两数的最大公约数.【解析】1.378=90×4+18，90=18×5+0，所以378与90的最大公约数是18.答案：182.因为294与84是偶数，首先除以2得到147，42，再求147与42的最大公约数147-42=105，105-42=63，63-42=21，42-21=21，共做了4次减法.答案：43.方法一(辗转相除法)第一步：104÷65=1×65+39第二步：65=1×39+26第三步：39=1×26+13第四步：26=2×13+0所以104和65的最大公约数为13.方法二(更相减损术)由于65不是偶数，把104和65以大数减小数，并辗转相减，即104-65=39，65-39=26，39-26=13，26-13=13，所以104和65的最大公约数为13.【方法技巧】1.辗转相除法的算法步骤第一步，输入两个正整数m，n(mn).第二步，计算m除以n所得的余数r.第三步，m=n，n=r.第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步.第五步，输出最大公约数m.2.更相减损术的求解步骤第一步，给定两个正整数m，n(mn且m，n不全是偶数).第二步，计算m-n所得的差k.第三步，比较n与k的大小，其中大者用m表示，小者用n表示.第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步.【拓展延伸】三个数的最大公约数的求解方法(1)从三个数中任取两个数，用辗转相除法或更相减损术求它们的最大公约数.(2)根据辗转相除法或更相减损术求所求得的最大公约数和第三个数的最大公约数.(3)求得的最大公约数即为这三个数的最大公约数.【变式训练】1.用辗转相除法求225和135的最大公约数.2.用更相减损术求1734，816的最大公约数.【解析】1.225=135×1+90，135=90×1+45，90=45×2，所以45是225和135的最大公约数.2.因为两数皆为偶数，首先除以2得到867，408，再求867与408的最大公约数.867-408=459，459-408=51，408-51=357，357-51=306，306-51=255，255-51=204，204-51=153，153-51=102，102-51=51，所以1734与816的最大公约数是51×2=102.类型二秦九韶算法的应用【典例】1.用秦九韶算法计算多项式f(x)=3x6+4x5-5x4+6x3-7x2+8x+1当x=2时的值时，需要做乘法和加法的次数分别是()A.6，6B.5，6C.5，5D.6，52.用秦九韶算法求多项式f(x)=8x7+5x6+3x4+2x+1，当x=2时的值.【解题探究】1.典例1中多项式的最高次数是几，多少项相加?2.典例2中不含x5，x3及x2项怎么办?【探究提示】1.典例1中多项式的最高次数是6，共7项相加.2.先把多项式f(x)=8x7+5x6+3x4+2x+1变形为f(x)=8x7+5x6+0·x5+3·x4+0·x3+0·x2+2x+1.【解析】1.选A.由秦九韶算法将多项式改成如下形式：f(x)=(((((3x+4)x-5)x+6)x-7)x+8)x+1，按由内到外的顺序，依次计算x=2时的值.v0=3，v1=3×2+4=10.v2=10×2-5=15，v3=15×2+6=36，v4=36×2-7=65，v5=65×2+8=138，v6=138×2+1=277.这样求多项式的值时，是通过求6个一次多项式的值得到的，故进行了6次乘法和6次加法.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.【延伸探究】典例2中需要做乘法和加法的次数是多少?【解析】根据秦九韶算法，把多项式改写成如下形式：f(x)=8x7+5x6+0·x5+3·x4+0·x3+0·x2+2x+1=((((((8x+5)x+0)x+3)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.所