人教A高中数学必修三课件算法案例.ppt
1.3算法案例,目标导航,新知导学素养养成,1.求两个正整数的最大公约数的算法(1)辗转相除法(欧几里得算法)的算法步骤:第一步,给定.第二步,计算.第三步,.第四步,若r=0,则m,n的最大公约数等于;否则返回.(2)更相减损术的算法步骤第一步,任意给定两个正整数,判断它们是否都是.若是,;若不是,执行.第二步,以的数减去的数,接着把所得的差与的数比较,并以大数减小数,继续这个操作,直到所得的数为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.,两个正整数m,n,m除以n所得的余数r,m=n,n=r,m,第二步,偶数,用2约简,第二步,较大,较小,较小,相等,思考1:辗转相除法与更相减损术有何异同?,答案:,2.秦九韶算法把一个n次多项式f(x)=anxn+an-1xn-1+a1x+a0改写成如下形式:f(x)=anxn+an-1xn-1+a1x+a0=(anxn-1+an-1xn-2+a1)x+a0=(anxn-2+an-1xn-3+a2)x+a1)x+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个一次多项式的值.,思考2:秦九韶算法的步骤是什么?,答案:,3.进位制(1)概念:进位制是为了而约定的记数系统,“满几进一”就是几进制,几进制的基数就是.(2)不同进位制之间的互化:k进制化为十进制的方法:anan-1a1a0(k)=(an,an-1,a1,a0N,0<an<k,0an-1,a1,a0<k).十进制化为k进制的方法.,思考3:不同进位制之间的数是否能比较大小?,答案:能.都可以把其化为相同进位制的数,然后比较其大小.,计数和运算方便,几,ankn+an-1kn-1+a1k+a0,除k取余法,名师点津,常见的进位制(1)二进制:只使用0和1两个数字;满二进一,如1+1=10.(2)八进制:使用0,1,2,3,4,5,6,7八个不同的数字;满八进一,如7+1=10.(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.,课堂探究素养提升,题型一求最大公约数例1分别用辗转相除法和更相减损术求779与209的最大公约数.,解:法一辗转相除法:779=2093+152,209=1521+57,152=572+38,57=381+19,38=192.所以,779与209的最大公约数为19.,法二更相减损术法:779-209=570,570-209=361,361-209=152,209-152=57,152-57=95,95-57=38,57-38=19,38-19=19.所以779和209的最大公约数为19.,方法技巧,求两个正整数的最大公约数的问题,可以用辗转相除法,也可以用更相减损术.,即时训练1-1:(2019安徽省屯溪第一中学月考)数612和486的最大公约数是()(A)12(B)14(C)16(D)18,解析: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.因此612与486的最大公约数是18.故选D.,解:f(x)=(6x+5)x+4)x+3)x+2)x+1)x,当x=2时,有v0=6,v1=62+5=17,v2=172+4=38,v3=382+3=79,v4=792+2=160,v5=1602+1=321,v6=3212=642,故当x=2时,多项式f(x)=6x6+5x5+4x4+3x3+2x2+x的值为642.,题型二秦九韶算法例2用秦九韶算法求多项式f(x)=6x6+5x5+4x4+3x3+2x2+x,当x=2时的值.,方法技巧,在运用秦九韶算法进行计算时,应注意每一步的运算结果,像这种一环扣一环的运算,如果错一步,那么下一步,一直到最后一步就会全部算错,在计算这种题时应格外小心.,即时训练2-1:(2019福建仙游一中月考)利用秦九韶算法计算f(x)=x5+4x4-3x2+x+5,x=2,v3等于()(A)43(B)19(C)12(D)6,解析:由题意可知:f(x)=(x+4)x-3)x+1)x+5,当x=2时,v0=1,v1=v0 x+4=12+4=6,v2=v1x-3=62-3=9,v3=v2x+1=92+1=19.故选B.,解:(1)101111011(2)=128+027+126+125+124+123+022+121+120=379.(2)235(7)=272+371+570=124.,题型三进位制例3(1)将101111011(2)转化为十进制数;(2)将235(7)转化为十进制数;,解:(3)因为137=362+46+5,所以137=345(6).,(3)将137转化为六进制数;,解:(4)53(8)=581+380=43.所以53(8)=101011(2).,(4)将53(8)转化为二进制数.,方法技巧,k进制数化为十进制数的步骤(1)把k进制数写成不同数位上的数字与k的幂的乘积之和的形式.(2)按十进制数的运算规则采用短除法运算出结果.,即时训练3-1:(1)(2019安徽屯溪一中学月考)729化成六进制,其结果是()(A)3321(6)(B)3223(6)(C)3213(6)(D)3123(6),(1)解析:由题得则729=3213(6).故选C.,(2)若六进制数13m502(6)化为十进制数等于12710,求数字m的值.,(2)解:因为13m502(6)=165+364+m63+562+061+260=216m+11846,令216m+11846=12710,所以m=4.,课堂达标,解析:f(x)=(3x+4)x+5)x+6)x+7)x+8)x+1,所以需要进行6次乘法和6次加法.,1.用秦九韶算法计算多项式f(x)=3x6+4x5+5x4+6x3+7x2+8x+1.当x=0.4时的值时,需要做乘法和加法的次数分别是()(A)6,6(B)5,6(C)5,5(D)6,5,A,2.(2019河南林州一中月考)用秦九韶算法求多项式f(x)=12+35x-8x2+79x3+6x4+5x5+3x6在x=-4时的值时,其中v4的值为()(A)-57(B)124(C)-845(D)220,解析:f(x)=(3x+5)x+6)x+79)x-8)x+35)x+12当x=-4时v4=(3x+5)x+6)x+79)x-8=220.故选D.,D,3.(2019河南省开封一中月考)下列各数中与1010(4)相等的数是()(A)76(9)(B)103(8)(C)1000100(2)(D)2111(3),解析:1010(4)=143+042+141+040=68(10),1000100(2)=126+122=68(10).故选C.,C,4.用辗转相除法和更相减损术求1515与600的最大公约数,需要运算的次数分别为()(A)4,15(B)5,14(C)5,13(D)4,12,解析:辗转相除法:1515=6002+315;600=3151+285,315=2851+30,285=309+15,30=152,故最大公约数为15,且需计算5次.用更相减损术法:1515-600=915,915-600=315,600-315=285,315-285=30,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,故最大公约数为15,且需计算14次.故选B.,B,
