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

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

.第二步,計算

.第三步,

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

;否則返回

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

.若是,

;若不是,執(zhí)行

.第二步,以

的數(shù)減去

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

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

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

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

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

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

.思考3:不同進位制之間的數(shù)是否能比較大小?答案:能.都可以把其化為相同進位制的數(shù),然后比較其大小.計數(shù)和運算方便幾an×kn+an-1×kn-1+…+a1×k+a0除k取余法名師點津常見的進位制(1)二進制:①只使用0和1兩個數(shù)字;②滿二進一,如1+1=10.(2)八進制:①使用0,1,2,3,4,5,6,7八個不同的數(shù)字;②滿八進一,如7+1=10.(3)十六進制:①使用0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F這十六個不同的數(shù)碼,其中A,B,C,D,E,F分別代表十進制中的10,11,12,13,14,15;②滿十六進一,如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.方法技巧求兩個正整數(shù)的最大公約數(shù)的問題,可以用輾轉(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,當x=2時,有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,故當x=2時,多項式f(x)=6x6+5x5+4x4+3x3+2x2+x的值為642.題型二秦九韶算法[例2]用秦九韶算法求多項式f(x)=6x6+5x5+4x4+3x3+2x2+x,當x=2時的值.方法技巧在運用秦九韶算法進行計算時,應注意每一步的運算結(jié)果,像這種一環(huán)扣一環(huán)的運算,如果錯一步,那么下一步,一直到最后一步就會全部算錯,在計算這種題時應格外小心.解析:由題意可知:f(x)=(((x+4)x-3)x+1)x+5,當x=2時,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.題型三進位制[例3](1)將101111011(2)轉(zhuǎn)化為十進制數(shù);(2)將235(7)轉(zhuǎn)化為十進制數(shù);解:(3)因為137=3×62+4×6+5,所以137=345(6).(3)將137轉(zhuǎn)化為六進制數(shù);解:(4)53(8)=5×81+3×80=43.所以53(8)=101011(2).(4)將53(8)轉(zhuǎn)化為二進制數(shù).方法技巧k進制數(shù)化為十進制數(shù)的步驟(1)把k進制數(shù)寫成不同數(shù)位上的數(shù)字與k的冪的乘積之和的形式.(2)按十進制數(shù)的運算規(guī)則采用短除法運算出結(jié)果.(1)解析:由題得則729=3213(6).故選C.(2)若六進制數(shù)13m502(6)化為十進制數(shù)等于12710,求數(shù)字m的值.(2)解:因為13m502(6)=1×65+3×64+m×63+5×62+0×61+2×60=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.當時的值時,需要做乘法和加法的次數(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當x=-4時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ù),需要運算的次數(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