高中数学人教A必修三配套课件13算法案例精讲优练课型

1、1.3 算法案例,【知识提炼】 1.辗转相除法与更相减损术 (1)辗转相除法： 辗转相除法：又叫_算法，是一种求两个正整数的 _的古老有效的算法.,欧几里得,最大公约数,程序 INPUTm，n DO r=_ m=n n=r LOOP UNTILr=0 PRINTm END,m MOD n,(2)更相减损术： 我国古代数学专著九章算术中介绍的一种求两个正整数的 _的算法. 运算过程 第一步，任意给定两个正整数，判断它们是否都是偶数，若是， _；若不是，执行第二步.,最大公约数,用2约简,第二步，以较大的数减去较小的数，接着把所得的差与_比 较，并以大数减小数.继续这个操作，直到所得的数_为止，则

2、 这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.,较小的数,相等,2.秦九韶算法,n个一次多项式,3.进位制及进位制之间的互化 (1)进位制： 概念：进位制是为了_而约定的记数系统， “满几进一”就是几进制. 基数：几进制的基数就是_.,计数和运算方便,几,(2)不同进位制之间的互化： k进制化为十进制的方法： anan-1a1a0(k)=_(an，an-1，a1，a0N，0ank，0an-1，a1，a0k). 十进制化为k进制的方法_.,ankn+an-1kn-1+a1k+a0,除k取余法,【即时小测】 1.思考下列问题： (1)实际应用更相减损术时要做的第一步工作是什么? 提

3、示：先判断a，b是否为偶数，若是，都除以2再进行. (2)任何进位制中都要用到的数字是什么? 提示：0和1.,2.将101111011(2)转化为十进制的数为() A.376(10)B.377(10)C.378(10)D.379(10) 【解析】选D.101111011(2)=128+027+126+125+124+123+ 022+121+120=379(10).,3.用更相减损术可求得78与36的最大公约数是() A.3B.4C.6D.12 【解析】选C. 78=392，36=182， 39-18=21，21-18=3， 18-3=15，15-3=12， 12-3=9，9-3=6， 6-3

4、=3，因此最大公约数为23=6.,4.利用辗转相除法求3869与6497的最大公约数时，第二步是. 【解析】第一步：6497=38691+2628 第二步：3869=26281+1241. 答案：3869=26281+1241,5.已知多项式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； v

5、1=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：用更

6、相减损术求最大公约数应按照怎样的步骤进行?,【总结提升】 1.辗转相除法的原理 设m，n是两个正整数(不妨设mn)， (1)用m除以n，若商为q1，余数为r1(0r1n)，则m=nq1+r1，显然若x是m和n的公约数，即x能整除m和n，则x也必然能整除r1，这样x也是n和r1的公约数，故求m和n的公约数就是求n和r1的公约数.,(2)用n除以r1，得n=r1q2+r2(0r2nr1r2，所以到某一步必然有ri=ri+1qi+2，即ri恰能被ri+1整除，这时ri+1是ri和ri+1的公约数，它也必然是ri-1和ri，ri-2和ri-1，r1与r2，n和r1，m和n的最大公约数.,2.更相减损术

7、求最大公约数的程序设计,【知识拓展】更相减损术与辗转相除法的区别与联系,知识点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：常见的进位制有哪些?,【总结提升

8、】 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).,【题型探究】 类型一 求最大公

9、约数 【典例】1.(2015大同高一检测)用辗转相除法求378与90的最大公约数为. 2.(2015衡水高一检测)用更相减损术求294与84的最大公约数时，需做减法的次数是. 3.求104与65的最大公约数.,【解题探究】1.典例1中应将两数怎样进行相除? 提示：应将294除以84，用较大的数除以较小的数依次进行. 2.典例2中应用更相减损术时要做的第一步工作是什么? 提示：由于294与84都是偶数，因此应先将两数都除以2再进行. 3.典例3中如何探求两数的最大公约数? 提示：可采用辗转相除法或更相减损术求两数的最大公约数.,【解析】1.378=904+18，90=185+0， 所以378与9

10、0的最大公约数是18. 答案：18 2.因为294与84是偶数，首先除以2得到147，42，再求147与42的最大公约数147-42=105，105-42=63，63-42=21，42-21=21，共做了4次减法. 答案：4,3.方法一(辗转相除法) 第一步：10465=165+39 第二步：65=139+26 第三步：39=126+13 第四步：26=213+0 所以104和65的最大公约数为13.,方法二(更相减损术) 由于65不是偶数，把104和65以大数减小数，并辗转相减，即 104-65=39， 65-39=26， 39-26=13， 26-13=13， 所以104和65的最大公约数

11、为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)从三个数中任取两个数，用辗转相除法或更相减损术求它们的最大公约

12、数. (2)根据辗转相除法或更相减损术求所求得的最大公约数和第三个数的最大公约数. (3)求得的最大公约数即为这三个数的最大公约数.,【变式训练】1.用辗转相除法求225和135的最大公约数. 2.用更相减损术求1734，816的最大公约数. 【解析】1.225=1351+90， 135=901+45，90=452， 所以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=

13、153，153-51=102， 102-51=51， 所以1734与816的最大公约数是512=102.,类型二 秦九韶算法的应用 【典例】1.用秦九韶算法计算多项式f(x)=3x6+4x5-5x4+6x3-7x2+8x+1当x=2时的值时，需要做乘法和加法的次数分别是() A.6，6B.5，6C.5，5D.6，5 2.用秦九韶算法求多项式f(x)=8x7+5x6+3x4+2x+1，当x=2时的值.,【解题探究】1.典例1中多项式的最高次数是几，多少项相加? 2.典例2中不含x5，x3及x2项怎么办? 【探究提示】1.典例1中多项式的最高次数是6，共7项相加. 2.先把多项式f(x)=8x7+

14、5x6+3x4+2x+1变形为f(x)=8x7+5x6+0 x5+3x4+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=32+4=10. v2=102-5=15， v3=152+6=36， v4=362-7=65，,v5=652+8=138， v6=1382+1=277. 这样求多项式的值时，是通过求6个一次多项式的值得到的，故进行了6次乘法和6次加法.,2.根据秦九韶算法，把多项式改写成如下形式： f(x)=8x7+5x6+0 x5

15、+3x4+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=82+5=21， v2=212+0=42， v3=422+3=87，,v4=872+0=174， v5=1742+0=348， v6=3482+2=698， v7=6982+1=1397. 所以当x=2时，多项式的值为1397.,【延伸探究】典例2中需要做乘法和加法的次数是多少? 【解析】根据秦九韶算法，把多项式改写成如下形式： f(x)=8x7+5x6+0 x5+3x4+0 x3+0 x2+2x+1=(8x+5)x+0)x+3)x+0)x+2)x+1.

16、而x=2，所以有v0=8， v1=82+5=21， v2=212+0=42， v3=422+3=87，,v4=872+0=174， v5=1742+0=348， v6=3482+2=698， v7=6982+1=1397. 所以当x=2时，多项式的值为1397. 这样求多项式的值时，是通过求7个一次多项式的值得到的，故进行了7次乘法和7次加法.,【方法技巧】应用秦九韶算法计算多项式的值应注意的问题 (1)要正确将多项式的形式进行改写. (2)计算应由内向外依次计算. (3)当多项式函数中间出现空项时，要以系数为零的齐次项补充.,【变式训练】1.已知f(x)=x5+2x3+3x2+x+1，应用秦

17、九韶算法计算当x=3时，v2的值为() A.27B.11C.109D.36 2.(2015福州高一检测)用秦九韶算法写出当x=3时f(x)=2x5-4x3+3x2-5x+1的值.,【解析】1.选B.将多项式改写成如下形式： f(x)=(x+0)x+2)x+3)x+1)x+1， 由内向外依次计算： v0=1， v1=13+0=3， v2=33+2=11.,2.因为f(x)=(2x-0)x-4)x+3)x-5)x+1， v0=2， v1=23+0=6， v2=63-4=14， v3=143+3=45， v4=453-5=130， v5=1303+1=391， 所以f(3)=391.,类型三 进位制

18、及其转化 【典例】1.(2015抚顺高一检测)把二进制数101101(2)化为十进制数为. 2.将十进制数458转化为四进制数为. 3.比较85(9)和210(6)的大小.,【解题探究】1.典例1中二进制数右数第i位数字ai化为十进制数是什么数? 提示：ai2i-1. 2.典例2中应按照怎样的方法将458转化为四进制的数? 提示：用4连续去除该十进制数得到商，直到商为零为止，然后把每次所得的余数倒着排成一个数，就是相应的四进制数.,3.典例3中比较85(9)和210(6)的大小的关键是什么? 提示：比较这两个数的关键是统一进位制，可将两个数转化为十进制数进行比较.,【解析】1.101101(2

19、)=125+024+123+122+021+120 =32+8+4+1=45， 所以二进制数101101(2)转化为十进制的数为45. 答案：45,2. 458=13022(4). 答案：13022(4) 3.因为85(9)=5+89=77， 210(6)=0+16+262=78，而7877， 所以210(6)85(9).,【延伸探究】 1.(改变问法)把典例2中的数转化成六进制的数，结果如何? 【解析】 458=2042(6).,2.(改变问法)把典例2中的数转化成八进制的数，结果如何? 【解析】 所以458=712(8).,【方法技巧】十进制数转化为其他进制数的方法步骤,【补偿训练】将235(7)转化为八进制数. 【解题指南】先将非十进制数转化为十进制数，再向其他k进制数转化，注意十进制数的中间作用. 【解析】235(7)=272+37+570=124(10)， 所以124(10)=174(8)，即235(7)=174(8).,【延伸探究】 1.(变换条件)若将“235(7)”变为“235(6)”，如