202X202X學(xué)年高中數(shù)學(xué)第一章算法初步1.3算法案例課件新人教A版必修3

1、1.31.3算法案例算法案例 目標(biāo)導(dǎo)航目標(biāo)導(dǎo)航 課標(biāo)要求課標(biāo)要求1.1.理解輾轉(zhuǎn)相除法與更相減損術(shù)的含義理解輾轉(zhuǎn)相除法與更相減損術(shù)的含義, ,理解其算理解其算法的執(zhí)行過(guò)程法的執(zhí)行過(guò)程. .2.2.理解秦九韶算法的計(jì)算過(guò)程及程序設(shè)計(jì)理解秦九韶算法的計(jì)算過(guò)程及程序設(shè)計(jì). .3.3.理解進(jìn)位制的概念理解進(jìn)位制的概念, ,能進(jìn)行不同進(jìn)位制之間的轉(zhuǎn)能進(jìn)行不同進(jìn)位制之間的轉(zhuǎn)換換, ,了解進(jìn)位制的程序設(shè)計(jì)了解進(jìn)位制的程序設(shè)計(jì). .素養(yǎng)達(dá)成素養(yǎng)達(dá)成通過(guò)算法案例的學(xué)習(xí)通過(guò)算法案例的學(xué)習(xí), ,進(jìn)一步理解算法的基本思想進(jìn)一步理解算法的基本思想, ,提高使用算法解決問(wèn)題的能力提高使用算法解決問(wèn)題的能力. .新知導(dǎo)學(xué)新

2、知導(dǎo)學(xué)素養(yǎng)養(yǎng)成素養(yǎng)養(yǎng)成1.1.求兩個(gè)正整數(shù)的最大公約數(shù)的算法求兩個(gè)正整數(shù)的最大公約數(shù)的算法(1)(1)輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法( (歐幾里得算法歐幾里得算法) )的算法步驟的算法步驟: :第一步第一步, ,給定給定 . .第二步第二步, ,計(jì)算計(jì)算 . .第三步第三步, ., .第四步第四步, ,假設(shè)假設(shè)r=0,r=0,那么那么m,nm,n的最大公約數(shù)等于的最大公約數(shù)等于 ; ;否那么返回否那么返回 . .(2)(2)更相減損術(shù)的算法步驟更相減損術(shù)的算法步驟第一步第一步, ,任意給定兩個(gè)正整數(shù)任意給定兩個(gè)正整數(shù), ,判斷它們是否都是判斷它們是否都是 . .假設(shè)假設(shè)是是, ;, ;假設(shè)不是假設(shè)不是,

3、 ,執(zhí)行執(zhí)行 . .第二步第二步, ,以以 的數(shù)減去的數(shù)減去 的數(shù)的數(shù), ,接著把所得的差與接著把所得的差與 的數(shù)的數(shù)比較比較, ,并以大數(shù)減小數(shù)并以大數(shù)減小數(shù), ,繼續(xù)這個(gè)操作繼續(xù)這個(gè)操作, ,直到所得的數(shù)直到所得的數(shù) 為止為止, ,那么這那么這個(gè)數(shù)個(gè)數(shù)( (等數(shù)等數(shù)) )或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù). .兩個(gè)正整數(shù)兩個(gè)正整數(shù)m,nm,nm m除以除以n n所得的余數(shù)所得的余數(shù)r rm=n,n=rm=n,n=rm m第二步第二步偶數(shù)偶數(shù)用用2 2約簡(jiǎn)約簡(jiǎn)第二步第二步較大較大較小較小較小較小相等相等思考思考1:1:輾轉(zhuǎn)相除法與更相減損

4、術(shù)有何異同輾轉(zhuǎn)相除法與更相減損術(shù)有何異同? ?答案答案: :兩種方法兩種方法輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法更相減損術(shù)更相減損術(shù)計(jì)算法則計(jì)算法則除法除法減法減法終止條件終止條件余數(shù)為余數(shù)為0 0減數(shù)與差相等減數(shù)與差相等最大公約數(shù)最大公約數(shù)的選取的選取最后一步中的除數(shù)最后一步中的除數(shù)最后一步中的減數(shù)最后一步中的減數(shù)計(jì)算次數(shù)計(jì)算次數(shù)步驟較少步驟較少,運(yùn)算復(fù)雜運(yùn)算復(fù)雜步驟較多步驟較多,運(yùn)算簡(jiǎn)單運(yùn)算簡(jiǎn)單相同點(diǎn)相同點(diǎn)同為求兩個(gè)正整數(shù)最大公約數(shù)的方法同為求兩個(gè)正整數(shù)最大公約數(shù)的方法,都是遞都是遞歸過(guò)程歸過(guò)程把一個(gè)把一個(gè)n n次多項(xiàng)式次多項(xiàng)式f(x)=af(x)=an nx xn n+a+an-1n-1x xn-1n-

5、1+a+a1 1x+ax+a0 0改寫(xiě)成如下形式改寫(xiě)成如下形式: :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. .求多項(xiàng)式的值時(shí)求多項(xiàng)式的值時(shí), ,首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次

6、多項(xiàng)式的值首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值, ,即即v v1 1=a=an nx+ax+an-1n-1, ,然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值, ,即即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次多項(xiàng)式次多項(xiàng)式f(x)f(x)的值就轉(zhuǎn)化為求的值就轉(zhuǎn)化為求n n個(gè)一次多項(xiàng)式的值個(gè)一次多項(xiàng)式的值. .思考思考2 2: :秦九韶算法的步驟是什么秦九韶算法的步驟是什么? ?答案答案: :(1)(1)概念概念: :進(jìn)位制是為了進(jìn)

7、位制是為了 而約定的記數(shù)系統(tǒng)而約定的記數(shù)系統(tǒng),“,“滿(mǎn)幾滿(mǎn)幾進(jìn)一就是幾進(jìn)制進(jìn)一就是幾進(jìn)制, ,幾進(jìn)制的基數(shù)就是幾進(jìn)制的基數(shù)就是 . .(2)(2)不同進(jìn)位制之間的互化不同進(jìn)位制之間的互化: :k k進(jìn)制化為十進(jìn)制的方法進(jìn)制化為十進(jìn)制的方法: :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).十進(jìn)制化為十進(jìn)制化為k k進(jìn)制的方法進(jìn)制的方法 . .思考思考3:3:不同進(jìn)位制之間的數(shù)是否能比較大小不同進(jìn)位制之間的數(shù)是否能比較大小? ?答案答案: :能

8、能. .都可以把其化為一樣進(jìn)位制的數(shù)都可以把其化為一樣進(jìn)位制的數(shù), ,然后比較其大小然后比較其大小. .計(jì)數(shù)和運(yùn)算方便計(jì)數(shù)和運(yùn)算方便幾幾a an nk kn n+a+an-1n-1k kn-1n-1+a+a1 1k+ak+a0 0除除k k取余法取余法名師點(diǎn)津名師點(diǎn)津常見(jiàn)的進(jìn)位制常見(jiàn)的進(jìn)位制(1)(1)二進(jìn)制二進(jìn)制: :只使用只使用0 0和和1 1兩個(gè)數(shù)字兩個(gè)數(shù)字; ;滿(mǎn)二進(jìn)一滿(mǎn)二進(jìn)一, ,如如1+1=10.1+1=10.(2)(2)八進(jìn)制八進(jìn)制: :使用使用0,1,2,3,4,5,6,70,1,2,3,4,5,6,7八個(gè)不同的數(shù)字八個(gè)不同的數(shù)字; ;滿(mǎn)八進(jìn)一滿(mǎn)八進(jìn)一, ,如如7+1=10.7

9、+1=10.(3)(3)十六進(jìn)制十六進(jìn)制: :使用使用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這十六個(gè)不這十六個(gè)不同的數(shù)碼同的數(shù)碼, ,其中其中A,B,C,D,E,FA,B,C,D,E,F分別代表十進(jìn)制中的分別代表十進(jìn)制中的10,11,12,13,14,15;10,11,12,13,14,15;滿(mǎn)十六進(jìn)一滿(mǎn)十六進(jìn)一, ,如如F+1=2+E=10.F+1=2+E=10.課堂探究課堂探究素養(yǎng)提升素養(yǎng)提升題型一求最大公約數(shù)題型一求最大公約數(shù) 例例11 分別用輾轉(zhuǎn)相除法和更相減損術(shù)求分別用輾轉(zhuǎn)相除法和更相減損術(shù)求779

10、779與與209209的最大公約數(shù)的最大公約數(shù). .解解: :法一法一輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法: :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的最大公約數(shù)為的最大公約數(shù)為19.19.法二法二更相減損術(shù)法更相減損術(shù)法: :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的最大公約數(shù)為的最大公約數(shù)為19.19.方法技巧方法技巧求兩個(gè)正整數(shù)的最大公約數(shù)的問(wèn)題求兩個(gè)正整數(shù)的最大公約數(shù)的問(wèn)題, ,可以用輾轉(zhuǎn)相除法可以用輾轉(zhuǎn)相除法, ,也可以用更也可以用更相減損術(shù)相減損術(shù). .即時(shí)訓(xùn)練即時(shí)訓(xùn)練1-1:(20211-1:(2021安徽省屯溪第一中學(xué)月考安徽省屯溪第一中學(xué)月考) )數(shù)數(shù)612612和和486486的最大公約的最大公約數(shù)是數(shù)是( () )(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 的 最 大 公 約 數(shù) 是的 最 大 公 約 數(shù)

13、是 1 8 .1 8 . 應(yīng) 選應(yīng) 選 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,當(dāng)當(dāng)x=2x=2時(shí)時(shí), ,有有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,故當(dāng)故當(dāng)x=2x=2時(shí)時(shí), ,多項(xiàng)式多項(xiàng)式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 用秦九韶算法求多項(xiàng)式用秦九韶算法求多項(xiàng)式f(x)=6xf(x)=6x6 6+5x+5x5 5+4x+4x4 4+3x+3x3 3+2x+2x2 2+x,+x,當(dāng)當(dāng)x=2x=2時(shí)時(shí)的值的值. .方法技巧方法技巧在運(yùn)用秦九韶算法進(jìn)展計(jì)算時(shí)在運(yùn)用秦九韶算法進(jìn)展計(jì)算時(shí), ,應(yīng)注意每一步的運(yùn)算結(jié)果應(yīng)注意每一步的運(yùn)算結(jié)果, ,像這種一環(huán)像這種一環(huán)扣一環(huán)的運(yùn)算扣一環(huán)的運(yùn)算, ,如果錯(cuò)一步如果錯(cuò)一步, ,那么下一步那么下一步, ,

15、一直到最后一步就會(huì)全部算一直到最后一步就會(huì)全部算錯(cuò)錯(cuò), ,在計(jì)算這種題時(shí)應(yīng)格外小心在計(jì)算這種題時(shí)應(yīng)格外小心. .即時(shí)訓(xùn)練即時(shí)訓(xùn)練2-1:(20212-1:(2021福建仙游一中月考福建仙游一中月考) )利用秦九韶算法計(jì)算利用秦九韶算法計(jì)算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,當(dāng)當(dāng)x=2x=2時(shí)時(shí),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.應(yīng)選應(yīng)選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.題型三進(jìn)位制題型三進(jìn)位制 例例3 3 (1)(1)將將101 111 011101 111 011(2)(2)轉(zhuǎn)化為十進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù); ;(2)(2)將將235235(7)(7)轉(zhuǎn)化為十進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù); ;解解: :(3)(3)因?yàn)橐驗(yàn)?37=3137=36 62 2+4+46+5,6+5,所以所以137=345137=345(6)(6). .(3)(3)將將137137轉(zhuǎn)化為六進(jìn)制數(shù)轉(zhuǎn)化為六進(jìn)制數(shù); ;解解: :(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)轉(zhuǎn)化為二進(jìn)制數(shù)轉(zhuǎn)化為二進(jìn)制數(shù). .方法技巧方法技巧k k進(jìn)制數(shù)化為十進(jìn)制數(shù)的步驟進(jìn)制數(shù)化為十進(jìn)制數(shù)的步驟(1)(1)把把k k進(jìn)制數(shù)寫(xiě)成不同數(shù)位上的數(shù)字與進(jìn)制數(shù)寫(xiě)成不同數(shù)位上的數(shù)字與k k的冪的乘積之和的形式的冪的乘積之和的形式. .(2)(2)按十進(jìn)制數(shù)的運(yùn)算規(guī)那么采用短除法運(yùn)算出結(jié)果按十進(jìn)制數(shù)的運(yùn)算規(guī)那么采用短除法運(yùn)算出結(jié)果. .即時(shí)訓(xùn)練即時(shí)訓(xùn)練3-1:(1)(20213-1:(1)(2021安徽屯溪一中學(xué)月考安徽屯溪一中學(xué)月考)729)729化成六進(jìn)制化成六進(jìn)制, ,其結(jié)果其結(jié)果是是( () )(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).應(yīng)選應(yīng)選C.C.(2)(2)假設(shè)六進(jìn)制數(shù)假設(shè)六進(jìn)制數(shù)13m502(6)13m502(6)化為十進(jìn)制數(shù)等于化為十進(jìn)制數(shù)等于12 710,12 710,求數(shù)字求數(shù)字m m的值的值. .(2)(2)解解: :因?yàn)橐驗(yàn)?3m50213m502(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.課堂達(dá)標(biāo)課堂達(dá)標(biāo)解析解析: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,所以需要進(jìn)展所以需要進(jìn)展6 6次乘法次乘法和和6 6次加法次加法. .1.1.用秦九韶算法計(jì)算多項(xiàng)式用秦九韶算法計(jì)算多項(xiàng)式f(x)=3xf(x)=3x6 6+4x+4x5 5+5x+5x4 4+6x+6x3 3+7x+7x2 2+8x+1.+8x+1.當(dāng)時(shí)的值當(dāng)時(shí)的值時(shí)時(shí), ,需要做乘法和加法的次數(shù)分別是需要做乘法和加法的次數(shù)分別是( ( ) )(A)6,6(A)6,6 (B)5,6(B)5,6 (C)5,5(C)5,5 (D)