高中数学13算法案例课件.ppt

1、1.3算法案例【知识提炼知识提炼】1.1.辗转相除法与更相减损术辗转相除法与更相减损术(1)(1)辗转相除法辗转相除法：辗转相除法：又叫辗转相除法：又叫_算法，是一种求两个正整数的算法，是一种求两个正整数的_的古老有效的算法的古老有效的算法.欧几里得欧几里得最大公约数最大公约数程序程序INPUTINPUTm m，n nDODOr r=_=_m=nm=nn=rn=rLOOP UNTILLOOP UNTILr=0r=0PRINTPRINTm mENDENDm MOD nm MOD n(2)(2)更相减损术：更相减损术：我国古代数学专著我国古代数学专著九章算术九章算术中介绍的一种求两个正整数的中介绍

2、的一种求两个正整数的_的算法的算法.运算过程运算过程第一步，任意给定两个正整数，判断它们是否都是偶数，若是，第一步，任意给定两个正整数，判断它们是否都是偶数，若是，_；若不是，执行第二步；若不是，执行第二步.最大公约数最大公约数用用2 2约简约简第二步，以较大的数减去较小的数，接着把所得的差与第二步，以较大的数减去较小的数，接着把所得的差与_比比较，并以大数减小数较，并以大数减小数.继续这个操作，直到所得的数继续这个操作，直到所得的数_为止，则为止，则这个数这个数(等数等数)或这个数与约简的数的乘积就是所求的最大公约数或这个数与约简的数的乘积就是所求的最大公约数.较小的数较小的数相等相等2.2

3、.秦九韶算法秦九韶算法n n个一次多项式个一次多项式3.3.进位制及进位制之间的互化进位制及进位制之间的互化(1)(1)进位制：进位制：概念：进位制是为了概念：进位制是为了_而约定的记数系统，而约定的记数系统，“满几进一满几进一”就是几进制就是几进制.基数：几进制的基数就是基数：几进制的基数就是_._.计数和运算方便计数和运算方便几几(2)(2)不同进位制之间的互化：不同进位制之间的互化：k k进制进制化为十进制的方法：化为十进制的方法：a an na an-1n-1a a1 1a a0(k)0(k)=_(a=_(an n，a an-1n-1，a a1 1，a a0 0NN，0a0an nkk

4、，0a0an-1n-1，a a1 1，a a0 0k).n)mn)，(1)(1)用用m m除以除以n n，若商为，若商为q q1 1，余数为，余数为r r1 1(0r(0r1 1n)n)，则，则m=nm=nq q1 1+r+r1 1，显然若，显然若x x是是m m和和n n的公约数，即的公约数，即x x能整除能整除m m和和n n，则，则x x也必然能整除也必然能整除r r1 1，这样，这样x x也是也是n n和和r r1 1的公约数，故求的公约数，故求m m和和n n的公约数就是求的公约数就是求n n和和r r1 1的公约数的公约数.(2)(2)用用n n除以除以r r1 1，得，得n=rn

5、=r1 1q q2 2+r+r2 2(0r(0r2 2rnrmnr1 1rr2 2，所以到某一步必然，所以到某一步必然有有r ri i=r=ri+1i+1q qi+2i+2，即，即r ri i恰能被恰能被r ri+1i+1整除，这时整除，这时r ri+1i+1是是r ri i和和r ri+1i+1的公约数，它的公约数，它也必然是也必然是r ri-1i-1和和r ri i，r ri-2i-2和和r ri-1i-1，r r1 1与与r r2 2，n n和和r r1 1，m m和和n n的最大公约的最大公约数数.2.2.更相减损术求最大公约数的程序设计更相减损术求最大公约数的程序设计【知识拓展知识拓

6、展】更相减损术与辗转相除法的区别与联系更相减损术与辗转相除法的区别与联系知识点知识点2 2 秦九韶算法秦九韶算法观察如图所示内容，回答下列问题：观察如图所示内容，回答下列问题：问题问题1 1：秦九韶算法的计数原理是怎样的：秦九韶算法的计数原理是怎样的?问题问题2 2：应按照怎样的步骤进行秦九韶算法：应按照怎样的步骤进行秦九韶算法?【总结提升总结提升】1.1.秦九韶算法的计数原理秦九韶算法的计数原理秦九韶算法是按照从内到外的顺序依次计算求值的秦九韶算法是按照从内到外的顺序依次计算求值的.设设f(x)=af(x)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a

7、0 0，则该算法先计算则该算法先计算v v1 1=a=an nx+ax+an-1n-1，再计算，再计算v v2 2=v=v1 1x+ax+an-2n-2，最后计算最后计算v vn n=v=vn-1n-1x+ax+a0 0.2.2.秦九韶算法的步骤秦九韶算法的步骤知识点知识点3 3 进位制进位制观察如图所示内容，回答下列问题：观察如图所示内容，回答下列问题：问题问题1 1：进位制应如何表示：进位制应如何表示?问题问题2 2：常见的进位制有哪些：常见的进位制有哪些?【总结提升总结提升】1.1.进位制的表示进位制的表示若一个数为十进制数，则其基数可以省略不写，若是其他进位制的数，若一个数为十进制数，

8、则其基数可以省略不写，若是其他进位制的数，在没有特别说明的前提下，其基数必须写出，常在数的右下角标明基在没有特别说明的前提下，其基数必须写出，常在数的右下角标明基数数.2.2.常见的进位制常见的进位制(1)(1)二进制：二进制：只使用只使用0 0和和1 1两个数字；满二进一，如两个数字；满二进一，如1+1=101+1=10(2)(2).(2)(2)八进制：八进制：使用使用0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7八个不同的数字；满八进一，如八个不同的数字；满八进一，如7+1=107+1=10(8)(8).(3)(3)十六进制：十六进制：使用使用0 0，1 1，2 2，3 3

9、，4 4，5 5，6 6，7 7，8 8，9 9，A A，B B，C C，D D，E E，F F这十六个这十六个不同的数码，其中不同的数码，其中A A，B B，C C，D D，E E，F F分别代表十进制中的分别代表十进制中的1010，1111，1212，1313，1414，1515；满十六进一，如；满十六进一，如F+1=2+E=10F+1=2+E=10(16)(16).【题型探究题型探究】类型一类型一 求最大公约数求最大公约数【典例典例】1.(20151.(2015大同高一检测大同高一检测)用辗转相除法求用辗转相除法求378378与与9090的最大公约的最大公约数为数为.2.(20152.(

10、2015衡水高一检测衡水高一检测)用更相减损术求用更相减损术求294294与与8484的最大公约数时，需的最大公约数时，需做减法的次数是做减法的次数是.3.3.求求104104与与6565的最大公约数的最大公约数.【解题探究解题探究】1.1.典例典例1 1中应将两数怎样进行相除中应将两数怎样进行相除?提示：提示：应将应将294294除以除以8484，用较大的数除以较小的数依次进行，用较大的数除以较小的数依次进行.2.2.典例典例2 2中应用更相减损术时要做的第一步工作是什么中应用更相减损术时要做的第一步工作是什么?提示：提示：由于由于294294与与8484都是偶数，因此应先将两数都除以都是偶

11、数，因此应先将两数都除以2 2再进行再进行.3.3.典例典例3 3中如何探求两数的最大公约数中如何探求两数的最大公约数?提示：提示：可采用辗转相除法或更相减损术求两数的最大公约数可采用辗转相除法或更相减损术求两数的最大公约数.【解析解析】1.378=901.378=904+184+18，90=1890=185+05+0，所以所以378378与与9090的最大公约数是的最大公约数是18.18.答案：答案：18182.2.因为因为294294与与8484是偶数，首先除以是偶数，首先除以2 2得到得到147147，4242，再求，再求147147与与4242的最大的最大公约数公约数147-42=10

12、5147-42=105，105-42=63105-42=63，63-42=2163-42=21，42-21=2142-21=21，共做了，共做了4 4次减次减法法.答案：答案：4 43.3.方法一方法一(辗转相除法辗转相除法)第一步：第一步：10410465=165=165+3965+39第二步：第二步：65=165=139+2639+26第三步：第三步：39=139=126+1326+13第四步：第四步：26=226=213+013+0所以所以104104和和6565的最大公约数为的最大公约数为13.13.方法二方法二(更相减损术更相减损术)由于由于6565不是偶数，把不是偶数，把10410

13、4和和6565以大数减小数，并辗转相减，即以大数减小数，并辗转相减，即104-65=39104-65=39，65-39=2665-39=26，39-26=1339-26=13，26-13=1326-13=13，所以所以104104和和6565的最大公约数为的最大公约数为13.13.【方法技巧方法技巧】1.1.辗转相除法的算法步骤辗转相除法的算法步骤第一步，输入两个正整数第一步，输入两个正整数m m，n(mn).n(mn).第二步，计算第二步，计算m m除以除以n n所得的余数所得的余数r.r.第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，则，则m m，n n的

14、最大公约数等于的最大公约数等于m m；否则，返回第二步否则，返回第二步.第五步，输出最大公约数第五步，输出最大公约数m.m.2.2.更相减损术的求解步骤更相减损术的求解步骤第一步，给定两个正整数第一步，给定两个正整数m m，n(mnn(mn且且m m，n n不全是偶数不全是偶数).).第二步，计算第二步，计算m-nm-n所得的差所得的差k.k.第三步，比较第三步，比较n n与与k k的大小，其中大者用的大小，其中大者用m m表示，小者用表示，小者用n n表示表示.第四步，若第四步，若m=nm=n，则，则m m，n n的最大公约数等于的最大公约数等于m m；否则，返回第二步；否则，返回第二步.【

15、拓展延伸拓展延伸】三个数的最大公约数的求解方法三个数的最大公约数的求解方法(1)(1)从三个数中任取两个数，用辗转相除法或更相减损术求它们的最从三个数中任取两个数，用辗转相除法或更相减损术求它们的最大公约数大公约数.(2)(2)根据辗转相除法或更相减损术求所求得的最大公约数和第三个数根据辗转相除法或更相减损术求所求得的最大公约数和第三个数的最大公约数的最大公约数.(3)(3)求得的最大公约数即为这三个数的最大公约数求得的最大公约数即为这三个数的最大公约数.【变式训练变式训练】1.1.用辗转相除法求用辗转相除法求225225和和135135的最大公约数的最大公约数.2.2.用更相减损术求用更相减

16、损术求17341734，816816的最大公约数的最大公约数.【解析解析】1.225=1351.225=1351+901+90，135=90135=901+451+45，90=4590=452 2，所以所以4545是是225225和和135135的最大公约数的最大公约数.2.2.因为两数皆为偶数，首先除以因为两数皆为偶数，首先除以2 2得到得到867867，408408，再求，再求867867与与408408的最的最大公约数大公约数.867-408=459867-408=459，459-408=51459-408=51，408-51=357408-51=357，357-51=306357-51

17、=306，306-51=255306-51=255，255-51=204255-51=204，204-51=153204-51=153，153-51=102153-51=102，102-51=51102-51=51，所以所以17341734与与816816的最大公约数是的最大公约数是51512=102.2=102.类型二类型二 秦九韶算法的应用秦九韶算法的应用【典例典例】1.1.用秦九韶算法计算多项式用秦九韶算法计算多项式f(x)=3xf(x)=3x6 6+4x+4x5 5-5x-5x4 4+6x+6x3 3-7x-7x2 2+8x+1+8x+1当当x=2x=2时的值时，需要做乘法和加法的次数

18、分别是时的值时，需要做乘法和加法的次数分别是()A.6A.6，6 6B.5B.5，6 6C.5C.5，5 5D.6D.6，5 52.2.用秦九韶算法求多项式用秦九韶算法求多项式f(x)=8xf(x)=8x7 7+5x+5x6 6+3x+3x4 4+2x+1+2x+1，当，当x=2x=2时的值时的值.【解题探究解题探究】1.1.典例典例1 1中多项式的最高次数是几，多少项相加中多项式的最高次数是几，多少项相加?2.2.典例典例2 2中不含中不含x x5 5，x x3 3及及x x2 2项怎么办项怎么办?【探究提示探究提示】1.1.典例典例1 1中多项式的最高次数是中多项式的最高次数是6 6，共，

19、共7 7项相加项相加.2.2.先把多项式先把多项式f(x)=8xf(x)=8x7 7+5x+5x6 6+3x+3x4 4+2x+1+2x+1变形为变形为f(x)=8xf(x)=8x7 7+5x+5x6 6+0+0 x x5 5+3+3x x4 4+0+0 x x3 3+0+0 x x2 2+2x+1.+2x+1.【解析解析】1.1.选选A.A.由秦九韶算法将多项式改成如下形式：由秦九韶算法将多项式改成如下形式：f(x)=(3x+4)x-5)x+6)x-7)x+8)x+1f(x)=(3x+4)x-5)x+6)x-7)x+8)x+1，按由内到外的顺序，依次计算按由内到外的顺序，依次计算x=2x=2

20、时的值时的值.v v0 0=3=3，v v1 1=3=32+4=10.2+4=10.v v2 2=10=102-5=152-5=15，v v3 3=15=152+6=362+6=36，v v4 4=36=362-7=652-7=65，v v5 5=65=652+8=1382+8=138，v v6 6=138=1382+1=277.2+1=277.这样求多项式的值时，是通过求这样求多项式的值时，是通过求6 6个一次多项式的值得到的，故进行个一次多项式的值得到的，故进行了了6 6次乘法和次乘法和6 6次加法次加法.2.2.根据秦九韶算法，把多项式改写成如下形式：根据秦九韶算法，把多项式改写成如下形

21、式：f(x)=8xf(x)=8x7 7+5x+5x6 6+0+0 x x5 5+3+3x x4 4+0+0 x x3 3+0+0 x x2 2+2x+1+2x+1=(8x+5)x+0)x+3)x+0)x+0)x+2)x+1.=(8x+5)x+0)x+3)x+0)x+0)x+2)x+1.而而x=2x=2，所以有，所以有v v0 0=8=8，v v1 1=8=82+5=212+5=21，v v2 2=21=212+0=422+0=42，v v3 3=42=422+3=872+3=87，v v4 4=87=872+0=1742+0=174，v v5 5=174=1742+0=3482+0=348，v

22、 v6 6=348=3482+2=6982+2=698，v v7 7=698=6982+1=1397.2+1=1397.所以当所以当x=2x=2时，多项式的值为时，多项式的值为1397.1397.【延伸探究延伸探究】典例典例2 2中需要做乘法和加法的次数是多少中需要做乘法和加法的次数是多少?【解析解析】根据秦九韶算法，把多项式改写成如下形式：根据秦九韶算法，把多项式改写成如下形式：f(x)=8xf(x)=8x7 7+5x+5x6 6+0+0 x x5 5+3+3x x4 4+0+0 x x3 3+0+0 x x2 2+2x+1=(8x+5)x+0)x+3)x+0)x+2x+1=(8x+5)x+

23、0)x+3)x+0)x+2)x+1.2)x+1.而而x=2x=2，所以有，所以有v v0 0=8=8，v v1 1=8=82+5=212+5=21，v v2 2=21=212+0=422+0=42，v v3 3=42=422+3=872+3=87，v v4 4=87=872+0=1742+0=174，v v5 5=174=1742+0=3482+0=348，v v6 6=348=3482+2=6982+2=698，v v7 7=698=6982+1=1397.2+1=1397.所以当所以当x=2x=2时，多项式的值为时，多项式的值为1397.1397.这样求多项式的值时，是通过求这样求多项式的

24、值时，是通过求7 7个一次多项式的值得到的，故进行个一次多项式的值得到的，故进行了了7 7次乘法和次乘法和7 7次加法次加法.【方法技巧方法技巧】应用秦九韶算法计算多项式的值应注意的问题应用秦九韶算法计算多项式的值应注意的问题(1)(1)要正确将多项式的形式进行改写要正确将多项式的形式进行改写.(2)(2)计算应由内向外依次计算计算应由内向外依次计算.(3)(3)当多项式函数中间出现空项时，要以系数为零的齐次项补充当多项式函数中间出现空项时，要以系数为零的齐次项补充.【变式训练变式训练】1.1.已知已知f(x)=xf(x)=x5 5+2x+2x3 3+3x+3x2 2+x+1+x+1，应用秦九

25、韶算法计算当，应用秦九韶算法计算当x=3x=3时，时，v v2 2的值为的值为()A.27A.27B.11B.11C.109C.109D.36D.362.(20152.(2015福州高一检测福州高一检测)用秦九韶算法写出当用秦九韶算法写出当x=3x=3时时f(x)=2xf(x)=2x5 5-4x-4x3 3+3x+3x2 2-5x+15x+1的值的值.【解析解析】1.1.选选B.B.将多项式改写成如下形式：将多项式改写成如下形式：f(x)=(x+0)x+2)x+3)x+1)x+1f(x)=(x+0)x+2)x+3)x+1)x+1，由内向外依次计算：由内向外依次计算：v v0 0=1=1，v v

26、1 1=1=13+0=33+0=3，v v2 2=3=33+2=11.3+2=11.2.2.因为因为f(x)=(2x-0)x-4)x+3)x-5)x+1f(x)=(2x-0)x-4)x+3)x-5)x+1，v v0 0=2=2，v v1 1=2=23+0=63+0=6，v v2 2=6=63-4=143-4=14，v v3 3=14=143+3=453+3=45，v v4 4=45=453-5=1303-5=130，v v5 5=130=1303+1=3913+1=391，所以所以f(3)=391.f(3)=391.类型三类型三 进位制及其转化进位制及其转化【典例典例】1.(20151.(20

27、15抚顺高一检测抚顺高一检测)把二进制数把二进制数101101101101(2)(2)化为十进制数化为十进制数为为.2.2.将十进制数将十进制数458458转化为四进制数为转化为四进制数为.3.3.比较比较8585(9)(9)和和210210(6)(6)的大小的大小.【解题探究解题探究】1.1.典例典例1 1中二进制数右数第中二进制数右数第i i位数字位数字a ai i化为十进制数是什化为十进制数是什么数么数?提示：提示：a ai i2 2i-1i-1.2.2.典例典例2 2中应按照怎样的方法将中应按照怎样的方法将458458转化为四进制的数转化为四进制的数?提示：提示：用用4 4连续去除该十

28、进制数得到商，直到商为零为止，然后把每连续去除该十进制数得到商，直到商为零为止，然后把每次所得的余数倒着排成一个数，就是相应的四进制数次所得的余数倒着排成一个数，就是相应的四进制数.3.3.典例典例3 3中比较中比较8585(9)(9)和和210210(6)(6)的大小的关键是什么的大小的关键是什么?提示：提示：比较这两个数的关键是统一进位制，可将两个数转化为十进制比较这两个数的关键是统一进位制，可将两个数转化为十进制数进行比较数进行比较.【解析解析】1.1011011.101101(2)(2)=1=12 25 5+0+02 24 4+1+12 23 3+1+12 22 2+0+02 21 1

29、+1+12 20 0=32+8+4+1=45=32+8+4+1=45，所以二进制数所以二进制数101101101101(2)(2)转化为十进制的数为转化为十进制的数为45.45.答案：答案：45452.2.458=13022458=13022(4)(4).答案：答案：1302213022(4)(4)3.3.因为因为8585(9)(9)=5+8=5+89=779=77，210210(6)(6)=0+1=0+16+26+26 62 2=78=78，而，而78777877，所以所以210210(6)(6)8585(9)(9).【延伸探究延伸探究】1.(1.(改变问法改变问法)把典例把典例2 2中的数

30、转化成六进制的数，结果如何中的数转化成六进制的数，结果如何?【解析解析】458=2042458=2042(6)(6).2.(2.(改变问法改变问法)把典例把典例2 2中的数转化成八进制的数，结果如何中的数转化成八进制的数，结果如何?【解析解析】所以所以458=712458=712(8)(8).【方法技巧方法技巧】十进制数转化为其他进制数的方法步骤十进制数转化为其他进制数的方法步骤【补偿训练补偿训练】将将235235(7)(7)转化为八进制数转化为八进制数.【解题指南解题指南】先将非十进制数转化为十进制数，再向其他先将非十进制数转化为十进制数，再向其他k k进制数转进制数转化，注意十进制数的中间

31、作用化，注意十进制数的中间作用.【解析解析】235235(7)(7)=2=27 72 2+3+37+57+57 70 0=124=124(10)(10)，所以所以124124(10)(10)=174=174(8)(8)，即，即235235(7)(7)=174=174(8).(8).【延伸探究延伸探究】1.(1.(变换条件变换条件)若将若将“235235(7)(7)”变为变为“235235(6)(6)”，如何转化为八进制数，如何转化为八进制数?【解析解析】因为因为235235(6)(6)=2=26 62 2+3+36 61 1+5+56 60 0=95=95(10)(10)所以所以9595(10

32、)(10)=137=137(8)(8)故故235235(6)(6)=137=137(8)(8)2.(2.(改变问法改变问法)如何将如何将235235(7)(7)转变成四进制数转变成四进制数?【解析解析】因为因为235235(7)(7)=2=27 72 2+3+37+57+57 70 0=124=124(10)(10)所以所以237237(7)(7)=1330=1330(4)(4).易错案例易错案例 利用秦九韶算法求多项式的值利用秦九韶算法求多项式的值【典例典例】(2015(2015哈尔滨高一检测哈尔滨高一检测)已知已知f(x)=xf(x)=x5 5+x+x3 3+x+x2 2+x+1+x+1，

33、用秦九韶，用秦九韶算法求算法求f(3)f(3)的值的值.【失误案例失误案例】【错解分析错解分析】分析解题过程，你知道错在哪里吗分析解题过程，你知道错在哪里吗?提示：提示：错误的根本原因在于当多项式中间出现空项时，用秦九韶算法错误的根本原因在于当多项式中间出现空项时，用秦九韶算法求函数值时没有补上系数为求函数值时没有补上系数为0 0的相应相项的相应相项.【自我矫正自我矫正】原多项式可化为：原多项式可化为：f(x)=(x+0)x+1)x+1)+1)x+1f(x)=(x+0)x+1)x+1)+1)x+1，当当x=3x=3时，时，v v0 0=1=1，v v1 1=1=13+0=33+0=3，v v2

34、 2=3=33+1=103+1=10，v v3 3=10=103+1=313+1=31，v v4 4=31=313+1=943+1=94，v v5 5=94=943+1=2833+1=283，所以，当，所以，当x=3x=3时，时，f(3)=283.f(3)=283.【防范措施防范措施】1.1.多项式改写要恰当、正确多项式改写要恰当、正确利用秦九韶算法计算多项式的值之前，必须先对多项式进行改写，多利用秦九韶算法计算多项式的值之前，必须先对多项式进行改写，多项式各项的次数按从高到低进行排列，如果有系数为项式各项的次数按从高到低进行排列，如果有系数为0 0的项，要补全，的项，要补全，然后再进行改写，否则容易出现如本题中然后再进行改写，否则容易出现如本题中f(x)=(x+1)x+1)x+1)x+1f(x)=(x+1)x+1)x+1)x+1的错误的错误.2.2.计算要准确计算要准确利用秦九韶算法计算多项式值的过程中，要进行多次计算，每一步中利用秦九韶算法计算多项式值的过程中，要进行多次计算，每一步中间结果要准确，如本题中间结果要准确，如本题中v v0 0，v v1 1，v v2 2，v v3 3，v v4 4，v v5 5的计算都要准确无误，的计算都要准确无误，否则就可能导致错误出现否则就可能导致错误出现.