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

1.3算法案例[目標(biāo)導(dǎo)航]課標(biāo)要求1.理解輾轉(zhuǎn)相除法與更相減損術(shù)的含義,理解其算法的執(zhí)行過(guò)程.2.理解秦九韶算法的計(jì)算過(guò)程及程序設(shè)計(jì).3.理解進(jìn)位制的概念,能進(jìn)行不同進(jìn)位制之間的轉(zhuǎn)換,了解進(jìn)位制的程序設(shè)計(jì).素養(yǎng)達(dá)成通過(guò)算法案例的學(xué)習(xí),進(jìn)一步理解算法的基本思想,提高使用算法解決問(wèn)題的能力.新知導(dǎo)學(xué)·素養(yǎng)養(yǎng)成1.求兩個(gè)正整數(shù)的最大公約數(shù)的算法(1)輾轉(zhuǎn)相除法(歐幾里得算法)的算法步驟:第一步,給定

.第二步,計(jì)算

.第三步,

.第四步,若r=0,則m,n的最大公約數(shù)等于

;否則返回

.(2)更相減損術(shù)的算法步驟第一步,任意給定兩個(gè)正整數(shù),判斷它們是否都是

.若是,

;若不是,執(zhí)行

.第二步,以

的數(shù)減去

的數(shù),接著把所得的差與

的數(shù)比較,并以大數(shù)減小數(shù),繼續(xù)這個(gè)操作,直到所得的數(shù)

為止,則這個(gè)數(shù)(等數(shù))或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù).兩個(gè)正整數(shù)m,nm除以n所得的余數(shù)rm=n,n=rm第二步偶數(shù)用2約簡(jiǎn)第二步較大較小較小相等思考1:輾轉(zhuǎn)相除法與更相減損術(shù)有何異同?答案:兩種方法輾轉(zhuǎn)相除法更相減損術(shù)計(jì)算法則除法減法終止條件余數(shù)為0減數(shù)與差相等最大公約數(shù)的選取最后一步中的除數(shù)最后一步中的減數(shù)計(jì)算次數(shù)步驟較少,運(yùn)算復(fù)雜步驟較多,運(yùn)算簡(jiǎn)單相同點(diǎn)同為求兩個(gè)正整數(shù)最大公約數(shù)的方法,都是遞歸過(guò)程把一個(gè)n次多項(xiàng)式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.求多項(xiàng)式的值時(shí),首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值,即v1=anx+an-1,然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,即v2=v1x+an-2,v3=v2x+an-3,…vn=vn-1x+a0.這樣,求n次多項(xiàng)式f(x)的值就轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值.思考2:秦九韶算法的步驟是什么?答案:(1)概念:進(jìn)位制是為了

而約定的記數(shù)系統(tǒng),“滿幾進(jìn)一”就是幾進(jìn)制,幾進(jìn)制的基數(shù)就是

.(2)不同進(jìn)位制之間的互化:①k進(jìn)制化為十進(jìn)制的方法:anan-1…a1a0(k)=

(an,an-1,…,a1,a0∈N,0<an<k,0≤an-1,…,a1,a0<k).②十進(jìn)制化為k進(jìn)制的方法——

.思考3:不同進(jìn)位制之間的數(shù)是否能比較大小?答案:能.都可以把其化為相同進(jìn)位制的數(shù),然后比較其大小.計(jì)數(shù)和運(yùn)算方便幾an×kn+an-1×kn-1+…+a1×k+a0除k取余法名師點(diǎn)津常見(jiàn)的進(jìn)位制(1)二進(jìn)制:①只使用0和1兩個(gè)數(shù)字;②滿二進(jìn)一,如1+1=10.(2)八進(jìn)制:①使用0,1,2,3,4,5,6,7八個(gè)不同的數(shù)字;②滿八進(jìn)一,如7+1=10.(3)十六進(jìn)制:①使用0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F這十六個(gè)不同的數(shù)碼,其中A,B,C,D,E,F分別代表十進(jìn)制中的10,11,12,13,14,15;②滿十六進(jìn)一,如F+1=2+E=10.課堂探究·素養(yǎng)提升題型一求最大公約數(shù)[例1]

分別用輾轉(zhuǎn)相除法和更相減損術(shù)求779與209的最大公約數(shù).解:法一

輾轉(zhuǎn)相除法:779=209×3+152,209=152×1+57,152=57×2+38,57=38×1+19,38=19×2.所以,779與209的最大公約數(shù)為19.法二更相減損術(shù)法: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的最大公約數(shù)為19.方法技巧求兩個(gè)正整數(shù)的最大公約數(shù)的問(wèn)題,可以用輾轉(zhuǎn)相除法,也可以用更相減損術(shù).解析: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的最大公約數(shù)是18.故選D.解:f(x)=(((((6x+5)x+4)x+3)x+2)x+1)x,當(dāng)x=2時(shí),有v0=6,v1=6×2+5=17,v2=17×2+4=38,v3=38×2+3=79,v4=79×2+2=160,v5=160×2+1=321,v6=321×2=642,故當(dāng)x=2時(shí),多項(xiàng)式f(x)=6x6+5x5+4x4+3x3+2x2+x的值為642.題型二秦九韶算法[例2]用秦九韶算法求多項(xiàng)式f(x)=6x6+5x5+4x4+3x3+2x2+x,當(dāng)x=2時(shí)的值.方法技巧在運(yùn)用秦九韶算法進(jìn)行計(jì)算時(shí),應(yīng)注意每一步的運(yùn)算結(jié)果,像這種一環(huán)扣一環(huán)的運(yùn)算,如果錯(cuò)一步,那么下一步,一直到最后一步就會(huì)全部算錯(cuò),在計(jì)算這種題時(shí)應(yīng)格外小心.解析:由題意可知:f(x)=(((x+4)x-3)x+1)x+5,當(dāng)x=2時(shí),v0=1,v1=v0x+4=1×2+4=6,v2=v1x-3=6×2-3=9,v3=v2x+1=9×2+1=19.故選B.解:(1)101111011(2)=1×28+0×27+1×26+1×25+1×24+1×23+0×22+1×21+1×20=379.(2)235(7)=2×72+3×71+5×70=124.題型三進(jìn)位制[例3](1)將101111011(2)轉(zhuǎn)化為十進(jìn)制數(shù);(2)將235(7)轉(zhuǎn)化為十進(jìn)制數(shù);解:(3)因?yàn)?37=3×62+4×6+5,所以137=345(6).(3)將137轉(zhuǎn)化為六進(jìn)制數(shù);解:(4)53(8)=5×81+3×80=43.所以53(8)=101011(2).(4)將53(8)轉(zhuǎn)化為二進(jìn)制數(shù).方法技巧k進(jìn)制數(shù)化為十進(jìn)制數(shù)的步驟(1)把k進(jìn)制數(shù)寫成不同數(shù)位上的數(shù)字與k的冪的乘積之和的形式.(2)按十進(jìn)制數(shù)的運(yùn)算規(guī)則采用短除法運(yùn)算出結(jié)果.(1)解析:由題得則729=3213(6).故選C.(2)若六進(jìn)制數(shù)13m502(6)化為十進(jìn)制數(shù)等于12710,求數(shù)字m的值.(2)解:因?yàn)?3m502(6)=1×65+3×64+m×63+5×62+0×61+2×60=216m+11846,令216m+11846=12710,所以m=4.課堂達(dá)標(biāo)解析:f(x)=(((((3x+4)x+5)x+6)x+7)x+8)x+1,所以需要進(jìn)行6次乘法和6次加法.1.用秦九韶算法計(jì)算多項(xiàng)式f(x)=3x6+4x5+5x4+6x3+7x2+8x+1.當(dāng)時(shí)的值時(shí),需要做乘法和加法的次數(shù)分別是(

)(A)6,6 (B)5,6 (C)5,5 (D)6,5A解析:f(x)=(((((3x+5)x+6)x+79)x-8)x+35)x+12當(dāng)x=-4時(shí)v4=(((3x+5)x+6)x+79)x-8=220.故選D.D解析:1010(4)=1×43+0×42+1×41+0×40=68(10),1000100(2)=1×26+1×22=68(10).故選C.C4.用輾轉(zhuǎn)相除法和更相減損術(shù)求1515與600的最大公約數(shù),需要運(yùn)算的次數(shù)分別為(

)(A)4,15 (B)5,14 (C)5,13 (D)4,12解析:輾轉(zhuǎn)相除法:1515=600×2+315;600=315×1+285,315=285×1+30,285=30×9+15,30=15