202X202X学年高中数学第一章算法初步1.3算法案例课件新人教A版必修3

1、1.31.3算法案例算法案例 目标导航目标导航 课标要求课标要求1.1.理解辗转相除法与更相减损术的含义理解辗转相除法与更相减损术的含义, ,理解其算理解其算法的执行过程法的执行过程. .2.2.理解秦九韶算法的计算过程及程序设计理解秦九韶算法的计算过程及程序设计. .3.3.理解进位制的概念理解进位制的概念, ,能进行不同进位制之间的转能进行不同进位制之间的转换换, ,了解进位制的程序设计了解进位制的程序设计. .素养达成素养达成通过算法案例的学习通过算法案例的学习, ,进一步理解算法的基本思想进一步理解算法的基本思想, ,提高使用算法解决问题的能力提高使用算法解决问题的能力. .新知导学新

2、知导学素养养成素养养成1.1.求两个正整数的最大公约数的算法求两个正整数的最大公约数的算法(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减数与差相等减数与差相等最大公约数最大公约数的选取的选取最后一步中的除数最后一步中的除数最后一步中的减数最后一步中的减数计算次数计算次数步骤较少步骤较少,运算复杂运算复杂步骤较多步骤较多,运算简单运算简单相同点相同点同为求两个正整数最大公约数的方法同为求两个正整数最大公约数的方法,都是递都是递归过程归过程把一个把一个n n次多项式次多项式f(x)=af(x)=an nx xn n+a+an-1n-1x xn-1n-

5、1+a+a1 1x+ax+a0 0改写成如下形式改写成如下形式: :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: :秦九韶算法的步骤是什么秦九韶算法的步骤是什么? ?答案答案: :(1)(1)概念概念: :进位制是为了进

7、位制是为了 而约定的记数系统而约定的记数系统,“,“满几满几进一就是几进制进一就是几进制, ,几进制的基数就是几进制的基数就是 . .(2)(2)不同进位制之间的互化不同进位制之间的互化: :k k进制化为十进制的方法进制化为十进制的方法: :anan-1a1a0(k)= (an,an-anan-1a1a0(k)= (an,an-1,a1,a0N,1,a1,a0N,0ank,0an-1,a1,a0k).0ank,0an-1,a1,a0k).十进制化为十进制化为k k进制的方法进制的方法 . .思考思考3:3:不同进位制之间的数是否能比较大小不同进位制之间的数是否能比较大小? ?答案答案: :能

8、能. .都可以把其化为一样进位制的数都可以把其化为一样进位制的数, ,然后比较其大小然后比较其大小. .计数和运算方便计数和运算方便几几a an nk kn n+a+an-1n-1k kn-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

9、+1=10.(3)(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 分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求779

10、779与与209209的最大公约数的最大公约数. .解解: :法一法一辗转相除法辗转相除法: :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-20

11、9=152,209-152=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:(20211-1:(2021安徽省屯溪第一中学月考安徽省屯溪第一中学月考) )数数612612和和486486的最大公约的最大公约数是数是( () )(A)12(A)12(B)

12、14(B)14(C)16(C)16(D)18(D)18解析解析:612-486=126,486-126=360,360-126=234,234-126=108,:612-486=126,486-126=360,360-126=234,234-126=108,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.因 此因 此 6 1 26 1 2 与与 4 8 64 8 6 的 最 大 公 约 数 是的 最 大 公 约 数

13、是 1 8 .1 8 . 应 选应 选 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时时, ,多项式多项式f(x

14、)=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-1:(20212-1:(2021福建仙游一中月考福建仙游一中月考) )利用秦九韶算法计算利用秦九韶算法计算f(x)=x5+4x4-3x2+x+5,x=2,v3f(x)=x5+4x4-3x2+x+5,x=2,v3等于等于( () )(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=2时时,v0=1,v1

16、=v0 x+4=1,v0=1,v1=v0 x+4=12+4=6,2+4=6,v2=v1x-3=6v2=v1x-3=62-3=9,v3=v2x+1=92-3=9,v3=v2x+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+37 71 1+5+57 70

17、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)=101 011=101 011

18、(2)(2). .(4)(4)将将5353(8)(8)转化为二进制数转化为二进制数. .方法技巧方法技巧k k进制数化为十进制数的步骤进制数化为十进制数的步骤(1)(1)把把k k进制数写成不同数位上的数字与进制数写成不同数位上的数字与k k的幂的乘积之和的形式的幂的乘积之和的形式. .(2)(2)按十进制数的运算规那么采用短除法运算出结果按十进制数的运算规那么采用短除法运算出结果. .即时训练即时训练3-1:(1)(20213-1:(1)(2021安徽屯溪一中学月考安徽屯溪一中学月考)729)729化成六进制化成六进制, ,其结果其结果是是( () )(A)3 321(6)(A)3 321(

19、6)(B)3 223(6)(B)3 223(6)(C)3 213(6)(C)3 213(6)(D)3 123(6)(D)3 123(6)(1)(1)解析解析: :由题得由题得那么那么729=3 213(6).729=3 213(6).应选应选C.C.(2)(2)假设六进制数假设六进制数13m502(6)13m502(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 61 1+2+26 60 0

20、=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.当时的值当时的值时时, ,需要做乘法和加法的次数分别是需要做乘法和加法的次数分别是( ( ) )(A)6,6(A)6,6 (B)5,6(B)5,6 (C)5,5(C)5,5 (D)