《2019-2020学年高中数学 第一章 算法初步 1.3 算法案例课件 新人教A版必修3》由会员分享，可在线阅读，更多相关《2019-2020学年高中数学 第一章 算法初步 1.3 算法案例课件 新人教A版必修3（26页珍藏版）》请在金锄头文库上搜索。
1、1.31.3算法案例算法案例 目标导航目标导航 课标要求课标要求1.1.理解理解辗转相除法与更相减相除法与更相减损术的含的含义, ,理解其算理解其算法的法的执行行过程程. .2.2.理解秦九韶算法的理解秦九韶算法的计算算过程及程序程及程序设计. .3.3.理解理解进位制的概念位制的概念, ,能能进行不同行不同进位制之位制之间的的转换, ,了解了解进位制的程序位制的程序设计. .素养达成素养达成通通过算法案例的学算法案例的学习, ,进一步理解算法的基本思想一步理解算法的基本思想, ,提高使用算法解决提高使用算法解决问题的能力的能力. .新知导学新知导学素养养成素养养成1.1.求两个正整数的最大公
2、约数的算法求两个正整数的最大公约数的算法(1)(1)辗转相除法辗转相除法( (欧几里得算法欧几里得算法) )的算法步骤的算法步骤: :第一步第一步, ,给定给定 . .第二步第二步, ,计算计算 . .第三步第三步, , . .第四步第四步, ,若若r=0,r=0,则则m,nm,n的最大公约数等于的最大公约数等于 ; ;否则返回否则返回 . .(2)(2)更相减损术的算法步骤更相减损术的算法步骤第一步第一步, ,任意给定两个正整数任意给定两个正整数, ,判断它们是否都是判断它们是否都是 . .若是若是, , ; ;若不是若不是, ,执行执行 . .第二步第二步, ,以以 的数减去的数减去 的数
3、的数, ,接着把所得的差与接着把所得的差与 的数的数比较比较, ,并以大数减小数并以大数减小数, ,继续这个操作继续这个操作, ,直到所得的数直到所得的数 为止为止, ,则这个则这个数数( (等数等数) )或这个数与约简的数的乘积就是所求的最大公约数或这个数与约简的数的乘积就是所求的最大公约数. .两个正整数两个正整数m,nm,nm m除以除以n n所得的余数所得的余数r rm=n,n=rm=n,n=rm m第二步第二步偶数偶数用用2 2约简约简第二步第二步较大较大较小较小较小较小相等相等思考思考1:1:辗转相除法与更相减损术有何异同辗转相除法与更相减损术有何异同? ?答案答案: :两种方法两
4、种方法辗转相除法辗转相除法更相减损术更相减损术计算法则计算法则除法除法减法减法终止条件终止条件余数为余数为0 0减数与差相等减数与差相等最大公约数最大公约数的选取的选取最后一步中的除数最后一步中的除数最后一步中的减数最后一步中的减数计算次数计算次数步骤较少步骤较少,运算复杂运算复杂步骤较多步骤较多,运算简单运算简单相同点相同点同为求两个正整数最大公约数的方法同为求两个正整数最大公约数的方法,都是递归都是递归过程过程2.2.秦九韶算法秦九韶算法把一个把一个n n次多项式次多项式f(x)=af(x)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0改写成如
5、下形式改写成如下形式: :f(x)=af(x)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0=(a=(an nx xn-1n-1+a+an-1n-1x xn-2n-2+a+a1 1)x+a)x+a0 0=(a=(an nx xn-2n-2+a+an-1n-1x xn-3n-3+a+a2 2)x+a)x+a1 1)x+a)x+a0 0=(a=(an nx+ax+an-1n-1)x+a)x+an-2n-2)x+a)x+a1 1)x+a)x+a0 0. .求多项式的值时求多项式的值时, ,首先计算最内层括号内一次多项式的值首先计算最内层括号内一次多项式的
6、值, ,即即v v1 1=a=an nx+ax+an-1n-1, ,然后由内向外逐层计算一次多项式的值然后由内向外逐层计算一次多项式的值, ,即即v v2 2=v=v1 1x+ax+an-2n-2,v,v3 3=v=v2 2x+ax+an-3n-3,v,vn n=v=vn-1n-1x+ax+a0 0. .这样这样, ,求求n n次多项式次多项式f(x)f(x)的值就转化为求的值就转化为求n n个一次多项式的值个一次多项式的值. .思考思考2 2: :秦九韶算法的步骤是什么秦九韶算法的步骤是什么? ?答案答案: :3.3.进位制进位制(1)(1)概念概念: :进位制是为了进位制是为了 而约定的记
7、数系统而约定的记数系统, ,“满几满几进一进一”就是几进制就是几进制, ,几进制的基数就是几进制的基数就是 . .(2)(2)不同进位制之间的互化不同进位制之间的互化:k:k进制化为十进制的方法进制化为十进制的方法: :a an na an-1n-1aa1 1a a0(k)0(k)= = (a(an n,a,an-1n-1,a,a1 1,a,a0 0N N, ,0a0an nk,0ak,0an-1n-1,a,a1 1,a,a0 0k).k).十进制化为十进制化为k k进制的方法进制的方法 . .思考思考3:3:不同进位制之间的数是否能比较大小不同进位制之间的数是否能比较大小? ?答案答案: :
8、能能. .都可以把其化为相同进位制的数都可以把其化为相同进位制的数, ,然后比较其大小然后比较其大小. .计数和运算方便计数和运算方便几几a an nkkn n+a+an-1n-1kkn-1n-1+a+a1 1k+ak+a0 0除除k k取余法取余法名师点津名师点津常见的进位制常见的进位制(1)(1)二进制二进制:只使用只使用0 0和和1 1两个数字两个数字;满二进一满二进一, ,如如1+1=10.1+1=10.(2)(2)八进制八进制:使用使用0,1,2,3,4,5,6,70,1,2,3,4,5,6,7八个不同的数字八个不同的数字;满八进一满八进一, ,如如7+1=10.7+1=10.(3)
9、(3)十六进制十六进制:使用使用0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F这十六个不这十六个不同的数码同的数码, ,其中其中A,B,C,D,E,FA,B,C,D,E,F分别代表十进制中的分别代表十进制中的10,11,12,13,14,15;10,11,12,13,14,15;满十六进一满十六进一, ,如如F+1=2+E=10.F+1=2+E=10.课堂探究课堂探究素养提升素养提升题型一求最大公约数题型一求最大公约数 例例11 分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求779779与与209209
10、的最大公约数的最大公约数. .解解: :法一法一辗转相除法辗转相除法: :779=209779=2093+152,3+152,209=152209=1521+57,1+57,152=57152=572+38,2+38,57=3857=381+19,1+19,38=1938=192.2.所以所以,779,779与与209209的最大公约数为的最大公约数为19.19.法二法二更相减损术法更相减损术法: :779-209=570,570-209=361,361-209=152,209-152=57,152-57=95,779-209=570,570-209=361,361-209=152,209-1
11、52=57,152-57=95,95-57=38,57-38=19,38-19=19.95-57=38,57-38=19,38-19=19.所以所以779779和和209209的最大公约数为的最大公约数为19.19.方法技巧方法技巧求两个正整数的最大公约数的问题求两个正整数的最大公约数的问题, ,可以用辗转相除法可以用辗转相除法, ,也可以用更也可以用更相减损术相减损术. .即时训练即时训练1 1- -1:1:(2019(2019安徽省屯溪第一中学月考安徽省屯溪第一中学月考) )数数612612和和486486的最大公约的最大公约数是数是( () )(A)12(A)12(B)14(B)14(C
12、)16(C)16(D)18(D)18解解 析析: :6 61 12 2- -4 48 86 6= =1 12 26 6, ,4 48 86 6- -1 12 26 6= =3 36 60 0, ,3 36 60 0- -1 12 26 6= =2 23 34 4, ,2 23 34 4- -1 12 26 6= =1 10 08 8, ,126-108=18,108-18=90,90-18=72,72-18=54,54-18=36,36-18=18.126-108=18,108-18=90,90-18=72,72-18=54,54-18=36,36-18=18.因此因此612612与与4864
13、86的最大公约数是的最大公约数是18.18.故选故选D.D.解解: :f(x)=(6x+5)x+4)x+3)x+2)x+1)x,f(x)=(6x+5)x+4)x+3)x+2)x+1)x,当当x=2x=2时时, ,有有v v0 0=6,=6,v v1 1=6=62+5=17,2+5=17,v v2 2=17=172+4=38,2+4=38,v v3 3=38=382+3=79,2+3=79,v v4 4=79=792+2=160,2+2=160,v v5 5=160=1602+1=321,2+1=321,v v6 6=321=3212=642,2=642,故当故当x=2x=2时时, ,多项式多项
14、式f(x)=6xf(x)=6x6 6+5x+5x5 5+4x+4x4 4+3x+3x3 3+2x+2x2 2+x+x的值为的值为642.642.题型二秦九韶算法题型二秦九韶算法 例例2 2 用秦九韶算法求多项式用秦九韶算法求多项式f(x)=6xf(x)=6x6 6+5x+5x5 5+4x+4x4 4+3x+3x3 3+2x+2x2 2+x,+x,当当x=2x=2时时的值的值. .方法技巧方法技巧在运用秦九韶算法进行计算时在运用秦九韶算法进行计算时, ,应注意每一步的运算结果应注意每一步的运算结果, ,像这种一环像这种一环扣一环的运算扣一环的运算, ,如果错一步如果错一步, ,那么下一步那么下一
15、步, ,一直到最后一步就会全部算一直到最后一步就会全部算错错, ,在计算这种题时应格外小心在计算这种题时应格外小心. .即即时时训训练练2 2- -1 1:(2019:(2019福福建建仙仙游游一一中中月月考考) )利利用用秦秦九九韶韶算算法法计计算算f(x)=xf(x)=x5 5+4x+4x4 4-3x-3x2 2+x+5,x=2,v+x+5,x=2,v3 3等于等于( () )(A)43(A)43(B)19(B)19(C)12(C)12(D)6(D)6解析解析: :由题意可知由题意可知:f(x)=(x+4)x-3)x+1)x+5,:f(x)=(x+4)x-3)x+1)x+5,当当x=2x=
16、2时时,v,v0 0=1,v=1,v1 1=v=v0 0x+4=1x+4=12+4=6,2+4=6,v v2 2=v=v1 1x-3=6x-3=62-3=9,v2-3=9,v3 3=v=v2 2x+1=9x+1=92+1=19.2+1=19.故选故选B.B.解解: :(1)101 111 011(1)101 111 011(2)(2)=1=12 28 8+0+02 27 7+1+12 26 6+1+12 25 5+1+12 24 4+1+12 23 3+0+02 22 2+ +1 12 21 1+1+12 20 0=379.=379.(2)235(2)235(7)(7)=2=27 72 2+3
17、+37 71 1+5+57 70 0=124.=124.题型三进位制题型三进位制 例例3 3 (1)(1)将将101 111 011101 111 011(2)(2)转化为十进制数转化为十进制数; ;(2)(2)将将235235(7)(7)转化为十进制数转化为十进制数; ;解解: :(3)(3)因为因为137=3137=36 62 2+4+46+5,6+5,所以所以137=345137=345(6)(6). .(3)(3)将将137137转化为六进制数转化为六进制数; ;解解: :(4)53(4)53(8)(8)=5=58 81 1+3+38 80 0=43.=43.所以所以5353(8)(8
18、)=101 011=101 011(2)(2). .(4)(4)将将5353(8)(8)转化为二进制数转化为二进制数. .方法技巧方法技巧k k进制数化为十进制数的步骤进制数化为十进制数的步骤(1)(1)把把k k进制数写成不同数位上的数字与进制数写成不同数位上的数字与k k的幂的乘积之和的形式的幂的乘积之和的形式. .(2)(2)按十进制数的运算规则采用短除法运算出结果按十进制数的运算规则采用短除法运算出结果. .即时训练即时训练3 3- -1:1:(1)(1)(2019(2019安徽屯溪一中学月考安徽屯溪一中学月考) )729729化成六进制化成六进制, ,其结果其结果是是( () )(A
19、)3 321(A)3 321(6)(6)(B)3 223(B)3 223(6)(6)(C)3 213(C)3 213(6)(6)(D)3 123(D)3 123(6)(6)(1)(1)解析解析: :由题得由题得则则729=3 213729=3 213(6)(6). .故选故选C.C.(2)(2)若六进制数若六进制数13m50213m502(6)(6)化为十进制数等于化为十进制数等于12 710,12 710,求数字求数字m m的值的值. .(2)(2)解解: :因为因为13m50213m502(6)(6)=1=16 65 5+3+36 64 4+m+m6 63 3+5+56 62 2+0+06
20、 61 1+2+26 60 0=216m+11 846,=216m+11 846,令令216m+11 846=12 710,216m+11 846=12 710,所以所以m=4.m=4.课堂达标课堂达标解析解析: :f(x)=(3x+4)x+5)x+6)x+7)x+8)x+1,f(x)=(3x+4)x+5)x+6)x+7)x+8)x+1,所以需要进行所以需要进行6 6次乘法次乘法和和6 6次加法次加法. .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=
21、0.4x=0.4时时的值时的值时, ,需要做乘法和加法的次数分别是需要做乘法和加法的次数分别是( ( ) )(A)6,6(A)6,6 (B)5,6(B)5,6 (C)5,5(C)5,5 (D)6,5(D)6,5A A2.2.(2019(2019河南林州一中月考河南林州一中月考) )用秦九韶算法求多项式用秦九韶算法求多项式f(x)=12+35x-8xf(x)=12+35x-8x2 2+ +79x79x3 3+6x+6x4 4+5x+5x5 5+3x+3x6 6在在x=-4x=-4时的值时时的值时, ,其中其中v v4 4的值为的值为( ( ) )(A)-57(A)-57 (B)124(B)124
22、 (C)-845(C)-845(D)220(D)220解析解析: :f(x)=(3x+5)x+6)x+79)x-8)x+35)x+12f(x)=(3x+5)x+6)x+79)x-8)x+35)x+12当当x=-4x=-4时时v v4 4=(3x+5)x+6)x+79)x-8=220.=(3x+5)x+6)x+79)x-8=220.故选故选D.D.D D3.3.(2019(2019河南省开封一中月考河南省开封一中月考) )下列各数中与下列各数中与1 0101 010(4)(4)相等的数是相等的数是( () )(A)76(A)76(9) (9) (B)103(B)103(8)(8)(C)1 000
23、 100(C)1 000 100(2)(2)(D)2 111(D)2 111(3)(3)解析解析: :1 0101 010(4)(4)=1=14 43 3+0+04 42 2+1+14 41 1+0+04 40 0=68=68(10)(10), ,1 000 1001 000 100(2)(2)=1=12 26 6+1+12 22 2=68=68(10)(10). .故选故选C.C.C C4.4.用辗转相除法和更相减损术求用辗转相除法和更相减损术求1 5151 515与与600600的最大公约数的最大公约数, ,需要运算的需要运算的次数分别为次数分别为( ( ) )(A)4,15 (A)4,1
24、5 (B)5,14 (B)5,14 (C)5,13 (C)5,13 (D)4,12(D)4,12解解析析: :辗辗转转相相除除法法 : :1 1 5 51 15 5= =6 60 00 02 2+ +3 31 15 5; ;6 60 00 0= =3 31 15 51 1+ +2 28 85 5, , 3 31 15 5= =2 28 85 51 1+ +3 30 0, , 2 28 85 5= =3 30 09 9+ +1 15 5, , 3 30 0= =1 15 52 2 , , 故故最最大大公公约约数数为为 1 15 5, , 且且需需计计算算 5 5次次. .用用更更相相减减损损术术
25、法法 : :1 1 5 51 15 5- -6 60 00 0= =9 91 15 5, ,9 91 15 5- -6 60 00 0= =3 31 15 5, ,6 60 00 0- -3 31 15 5= =2 28 85 5, ,3 31 15 5- -2 28 85 5= =3 30 0, ,285-30=255,255-30=225,225-30=195,195-30=165,165-30=135,135-285-30=255,255-30=225,225-30=195,195-30=165,165-30=135,135-30=105,105-30=75,75-30=45,45-30=15,30-15=15,30=105,105-30=75,75-30=45,45-30=15,30-15=15,故故最最大大公公约约数数为为15,15,且需计算且需计算1414次次. .故选故选B.B.B B
