高中數(shù)學(xué) 專題1.5 算法案例課件 新人教A版必修3

1、算法案例1.1.輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法 所謂輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)數(shù)，用較大所謂輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)除以較小的數(shù)的數(shù)除以較小的數(shù). .若余數(shù)不為零，則將余數(shù)和較小的若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時(shí)較小的數(shù)就是原來(lái)兩個(gè)數(shù)的最大公約數(shù)除盡，則這時(shí)較小的數(shù)就是原來(lái)兩個(gè)數(shù)的最大公約數(shù). .基礎(chǔ)回顧基礎(chǔ)回顧2 2、作用：輾轉(zhuǎn)相除法是用于求兩個(gè)正整數(shù)、作用：輾轉(zhuǎn)相除法是用于求兩個(gè)正整數(shù)_的一種的一種算法，這種算法是由歐幾里得在公元前算法，這種算法是由歐幾里得在公元前300

2、300年左右首先提出年左右首先提出的，因此又叫的，因此又叫_最大公約數(shù)最大公約數(shù)歐幾里得算法歐幾里得算法【小結(jié)】輾轉(zhuǎn)相除法的步驟：【小結(jié)】輾轉(zhuǎn)相除法的步驟：第一步，給定兩個(gè)正整數(shù)第一步，給定兩個(gè)正整數(shù)m,nm,n不妨令不妨令mn.mn.第二步，計(jì)算第二步，計(jì)算m m除以除以n n所得的余數(shù)所得的余數(shù)r r第三步，第三步，_，_第四步，若第四步，若r=0r=0，則，則m,nm,n的最大公約數(shù)等于的最大公約數(shù)等于_；否則，返回第二步否則，返回第二步m=nm=nn=rn=rm m1 1、算理：、算理： 所謂更相減損術(shù)，就是對(duì)于給定的兩個(gè)數(shù)，用較大的所謂更相減損術(shù)，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)減去

3、較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟，直到差再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟，直到差數(shù)和較小的數(shù)相等，此時(shí)相等的兩數(shù)便為原來(lái)兩個(gè)數(shù)的數(shù)和較小的數(shù)相等，此時(shí)相等的兩數(shù)便為原來(lái)兩個(gè)數(shù)的最大公約數(shù)最大公約數(shù). .類型二類型二：更相減損術(shù) 2 2、作用：更相減損術(shù)是我國(guó)古代數(shù)學(xué)專著、作用：更相減損術(shù)是我國(guó)古代數(shù)學(xué)專著_中中 介紹的一種求兩個(gè)正整數(shù)最大公約數(shù)的方法介紹的一種求兩個(gè)正整數(shù)最大公約數(shù)的方法九章算術(shù)九章算術(shù)（1 1）算法步驟）算法步驟第一步第一步, ,輸入兩個(gè)正整數(shù)輸入兩個(gè)正整數(shù)a,b(a

4、a,b(ab);b);第二步第二步, ,若若a a不等于不等于b ,b ,則執(zhí)行第三步；否則轉(zhuǎn)到第五步；則執(zhí)行第三步；否則轉(zhuǎn)到第五步；第三步第三步, ,把把a(bǔ)-ba-b的差賦予的差賦予r;r;第四步第四步, ,如果如果br, br, 那么把那么把b b賦給賦給a,a,把把r r賦給賦給b;b;否則把否則把r r賦給賦給 a a，執(zhí)行第二步；，執(zhí)行第二步；第五步第五步, ,輸出最大公約數(shù)輸出最大公約數(shù)b.b.3 3、試根據(jù)更相減損術(shù)設(shè)計(jì)一個(gè)計(jì)算機(jī)程序，求兩個(gè)正整數(shù)、試根據(jù)更相減損術(shù)設(shè)計(jì)一個(gè)計(jì)算機(jī)程序，求兩個(gè)正整數(shù)的最大公約數(shù)。的最大公約數(shù)。類型三：類型三：秦九韶算法秦九韶算法1 1秦九韶算法：秦

5、九韶算法： 秦九韶算法的是通過(guò)一次式的反復(fù)計(jì)算，逐步求出秦九韶算法的是通過(guò)一次式的反復(fù)計(jì)算，逐步求出n n次次多項(xiàng)式的值因此對(duì)于一個(gè)多項(xiàng)式的值因此對(duì)于一個(gè)n n次多項(xiàng)式，利用秦九韶算法次多項(xiàng)式，利用秦九韶算法求多項(xiàng)式的值，只要做求多項(xiàng)式的值，只要做n n次乘法運(yùn)算和次乘法運(yùn)算和n n次加法運(yùn)算即可次加法運(yùn)算即可2 2、作用：用秦九韶算法求、作用：用秦九韶算法求n n次多項(xiàng)式次多項(xiàng)式f(x)=af(x)=an nx xn n+a+an n1 1x xn n1 1+a+a1 1x+ax+a0 0， 當(dāng)當(dāng)x=xx=x0 0時(shí)的值時(shí)的值. .3 3、基本原理：首先將多項(xiàng)式改寫成如下形式：、基本原理：首

6、先將多項(xiàng)式改寫成如下形式： f(x)=af(x)=an nx xn n+a+an n1 1x xn n1 1+a+a1 1x+ax+a0 0=(a=(an nx xn n1 1+a+an n1 1x xn n2 2+a+a1 1)x+a)x+a0 0 =(a=(an nx xn n2 2+a+an n1 1x xn n3 3+a+a2 2)x+a)x+a1 1)x+a)x+a0 0= _，=(a=(an nx+ax+an n1 1)x+a)x+an n2 2)x+a)x+a1 1)x+a)x+a0 0求多項(xiàng)式的值時(shí)，首先計(jì)算最內(nèi)層括號(hào)內(nèi)的一次多項(xiàng)式的值，求多項(xiàng)式的值時(shí)，首先計(jì)算最內(nèi)層括號(hào)內(nèi)的一

7、次多項(xiàng)式的值，即即v v1 1= _= _，然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，即，然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，即v v2 2=v=v1 1x+ax+an n2 2，v v3 3=v=v2 2x+ax+an n3 3， v vn n= _.= _.這樣，求這樣，求n n次多項(xiàng)式次多項(xiàng)式f(x)f(x)的值就轉(zhuǎn)化為求的值就轉(zhuǎn)化為求_a an nx+ax+an n1 1v vn n1 1x+ax+a0 0n n個(gè)一次多項(xiàng)式的值個(gè)一次多項(xiàng)式的值【小結(jié)】秦九韶算【小結(jié)】秦九韶算 法的步驟法的步驟改寫改寫改寫多項(xiàng)式改寫多項(xiàng)式f(x)=af(x)=an nx xn n+a+an-1n-1x xn-

8、n-1 1+ +a+a1 1x+ax+a0 0為為f(x)=(f(x)=(a(an nx+ax+an-1n-1)x+a)x+an-2n-2)x+a)x+an-n-3 3)x+)x+a+a1 1)x+a)x+a0 0計(jì)算計(jì)算結(jié)論結(jié)論當(dāng)當(dāng)x=xx=x0 0時(shí)，時(shí)，由內(nèi)到外依次計(jì)算由內(nèi)到外依次計(jì)算0nkk-10n-kvav =vx +a (k=1,2,n)，當(dāng)當(dāng)x=xx=x0 0時(shí)，時(shí)，f(x)f(x)的值為的值為f(xf(x0 0)=v)=vn n1. 1. 進(jìn)位制的概念：進(jìn)位制是人們?yōu)橛?jì)數(shù)和運(yùn)算方便而約定的計(jì)數(shù)系進(jìn)位制的概念：進(jìn)位制是人們?yōu)橛?jì)數(shù)和運(yùn)算方便而約定的計(jì)數(shù)系統(tǒng)，約定滿二進(jìn)一，就是統(tǒng)，約

9、定滿二進(jìn)一，就是_進(jìn)制；滿十進(jìn)一，就是進(jìn)制；滿十進(jìn)一，就是_進(jìn)制；進(jìn)制；,也也就是說(shuō)，就是說(shuō)，“滿幾進(jìn)一滿幾進(jìn)一”就是就是_進(jìn)制，幾進(jìn)制的基數(shù)就是進(jìn)制，幾進(jìn)制的基數(shù)就是_._.二二十十幾幾幾幾類型四：類型四：二進(jìn)制2 2、表示：一般地，若、表示：一般地，若k k是一個(gè)大于是一個(gè)大于1 1的整數(shù)，那么以的整數(shù)，那么以k k為基數(shù)的為基數(shù)的k k進(jìn)進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式：制數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式：a an na an-n-1 1aa1 1a a0(k)0(k)(a(an n,a,an-1n-1,a,a1 1,a,a0 0n,0n,0a an n_,0_a_,0_an

10、-1n-1,a,a1 1,a,a0 0k)k)k k3.3.進(jìn)位制之間的轉(zhuǎn)化進(jìn)位制之間的轉(zhuǎn)化(1)k(1)k進(jìn)制的數(shù)轉(zhuǎn)化為十進(jìn)制：若進(jìn)制的數(shù)轉(zhuǎn)化為十進(jìn)制：若a an na an-1n-1aa1 1a a0(k)0(k)表示一個(gè)表示一個(gè)k k進(jìn)進(jìn) 制的數(shù)，則轉(zhuǎn)化為十進(jìn)制數(shù)為制的數(shù)，則轉(zhuǎn)化為十進(jìn)制數(shù)為: : a an na an-1n-1aa1 1a a0(k)0(k)=_.=_.(2)(2)將十進(jìn)制化為將十進(jìn)制化為k k進(jìn)制進(jìn)制: :用除用除k k取余法，用取余法，用k k連續(xù)去除連續(xù)去除_，直到，直到_為止，然后將所得的余數(shù)為止，然后將所得的余數(shù)_，即為相應(yīng)的，即為相應(yīng)的k k進(jìn)制數(shù)進(jìn)制數(shù).

11、.a an nkkn n+a+an-1n-1kkn-1n-1+a+a1 1kk1 1+a+a0 0十進(jìn)制數(shù)所得的商十進(jìn)制數(shù)所得的商商為零商為零倒序?qū)懗龅剐驅(qū)懗鲱愋鸵弧㈩愋鸵弧?求最大公約數(shù)求最大公約數(shù)問(wèn)題探討與解題研究問(wèn)題探討與解題研究例例1.1.分別用輾轉(zhuǎn)相除法和更相減損術(shù)求分別用輾轉(zhuǎn)相除法和更相減損術(shù)求779779與與209209的最大公約數(shù)的最大公約數(shù). .【分析】【分析】(1)(1)輾轉(zhuǎn)相除法的操作是較大的數(shù)除以較小的數(shù)，直輾轉(zhuǎn)相除法的操作是較大的數(shù)除以較小的數(shù)，直到余數(shù)為零到余數(shù)為零(2)(2)更相減損術(shù)的操作是以大數(shù)減小數(shù)，直到減數(shù)和差相等更相減損術(shù)的操作是以大數(shù)減小數(shù)，直到減數(shù)和

12、差相等【解析】方法一：輾轉(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.所以，所以，779779與與209209的最大公約數(shù)為的最大公約數(shù)為19.19.方法二：更相減損術(shù)方法二：更相減損術(shù)779-209=570,779-209=570,570-209=361,570-209=361,361-209=152,361-209=152,209-152=57,209-152=57,152-57=95,152

13、-57=95,95-57=38,95-57=38,57-38=19,57-38=19,38-19=19.38-19=19.所以所以779779和和209209的最大公約數(shù)為的最大公約數(shù)為19. 19. 【練習(xí)】【練習(xí)】(1)(1)用更相減損術(shù)求用更相減損術(shù)求7878與與3636的最大公約數(shù)；的最大公約數(shù)； (2) (2)用輾轉(zhuǎn)相除法求用輾轉(zhuǎn)相除法求7878與與3636的最大公約數(shù)的最大公約數(shù)【解析】【解析】(1)78(1)7836364242，424236366 6，36366 63030，30306 62424，24246 61818， 18 186 61212，12126 66 6(2)(

14、2)由輾轉(zhuǎn)相除法得，由輾轉(zhuǎn)相除法得，787836362 26 6，36366 66 6，故故7878與與3636的最大公約數(shù)是的最大公約數(shù)是6 6【小結(jié)】輾轉(zhuǎn)相除法與更相減損術(shù)的比較【小結(jié)】輾轉(zhuǎn)相除法與更相減損術(shù)的比較: : （1 1）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主除法以除法為主，更相減損術(shù)以減法為主; ;計(jì)算次數(shù)上計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯。區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯。（2 2）從結(jié)果體現(xiàn)形式來(lái)看，輾轉(zhuǎn)相

15、除法體現(xiàn)結(jié)）從結(jié)果體現(xiàn)形式來(lái)看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為果是以相除余數(shù)為0 0則得到，而更相減損術(shù)則以減數(shù)與則得到，而更相減損術(shù)則以減數(shù)與差相等而得到差相等而得到. .例例2 2、已知、已知f(x)=5xf(x)=5x4 4+10 x+10 x3 3+10 x+10 x2 2+5x+1+5x+1，用秦九韶算法求，用秦九韶算法求x=2x=2時(shí)時(shí)f(x)f(x)的值的值類型二、類型二、 利用秦九韶算法求多項(xiàng)式的值利用秦九韶算法求多項(xiàng)式的值【分析】根據(jù)秦九韶算法的運(yùn)算法則，將函數(shù)【分析】根據(jù)秦九韶算法的運(yùn)算法則，將函數(shù)f(x)f(x)化為下面的形化為下面的形 式：式：f(x)=(5x+10)

16、x+10)x+5)x+1f(x)=(5x+10)x+10)x+5)x+1，然后從里向外逐步，然后從里向外逐步 計(jì)算，共進(jìn)行計(jì)算，共進(jìn)行4 4次乘法，次乘法，5 5次加法運(yùn)算，就得到次加法運(yùn)算，就得到x=x=2 2時(shí)時(shí)f(x)f(x) 的值的值【解析】因?yàn)椤窘馕觥恳驗(yàn)閒(x)=5xf(x)=5x4 4+10 x+10 x3 3+10 x+10 x2 2+5x+1+5x+1 所以所以f(x)=(5x+10)x+10)x+5)x+1v v0 0=5=5，v v1 1=5=5( (2)+10=02)+10=0，v v2 2=0=0( (2)+10=102)+10=10，v v3 3=10=10( (2

17、)+5=-152)+5=-15，v v4 4= =（-15-15）( (2)+1=-292)+1=-29，所以，當(dāng)所以，當(dāng)x=x=2 2時(shí)，時(shí)，f(x)=f(x)=2929 【練習(xí)】已知一個(gè)【練習(xí)】已知一個(gè)5 5次多項(xiàng)式為次多項(xiàng)式為f(x)f(x)4x4x5 52x2x4 43 35x5x3 32 26x6x2 21 17x7x0 08 8，用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)，用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x x5 5時(shí)的值時(shí)的值【解析】將【解析】將f(x)f(x)改寫為改寫為f(x)f(x)(4x(4x2)x2)x3 35)x5)x2 26)x6)x1 17)x7)x0 08 8，由內(nèi)向外依次計(jì)算一次多

18、項(xiàng)式，當(dāng)由內(nèi)向外依次計(jì)算一次多項(xiàng)式，當(dāng)x x5 5時(shí)的值：時(shí)的值：v v0 04 4； v v1 14 45 52 22222； v v2 222225 53 35 51131135 5；v v3 31131135 55 52 26 65645649 9； v v4 45645649 95 51 17 72 8262 8262 2；v v5 52 8262 8262 25 50 08 814 13014 1302 2所以當(dāng)所以當(dāng)x x5 5時(shí)，多項(xiàng)式的值等于時(shí)，多項(xiàng)式的值等于14 13014 1302 2【小結(jié)】秦九韶算法是求一元多項(xiàng)式的值的一種方法【小結(jié)】秦九韶算法是求一元多項(xiàng)式的值的一種方

19、法. .它的特點(diǎn)是它的特點(diǎn)是: :把求一個(gè)把求一個(gè)n n次多項(xiàng)式的值轉(zhuǎn)化為求次多項(xiàng)式的值轉(zhuǎn)化為求n n個(gè)一次個(gè)一次多項(xiàng)式的值多項(xiàng)式的值, ,通過(guò)這種轉(zhuǎn)化通過(guò)這種轉(zhuǎn)化, ,把運(yùn)算的次數(shù)由至多把運(yùn)算的次數(shù)由至多n(n+1)/2n(n+1)/2次乘次乘法運(yùn)算和法運(yùn)算和n n次加法運(yùn)算次加法運(yùn)算, ,減少為減少為n n次乘法運(yùn)算和次乘法運(yùn)算和n n次加法運(yùn)算次加法運(yùn)算, ,大大大提高了運(yùn)算效率大提高了運(yùn)算效率. .例例1.1.已知一個(gè)已知一個(gè)k k進(jìn)制數(shù)進(jìn)制數(shù)132132與十進(jìn)制數(shù)與十進(jìn)制數(shù)3030相等相等, ,那么那么k k等于等于( )( ) (a)-7 (a)-7或或4 (b)-7 (c)4 (

20、d)4 (b)-7 (c)4 (d)都不對(duì)都不對(duì)類型三、類型三、 利用秦九韶算法求多項(xiàng)式的值利用秦九韶算法求多項(xiàng)式的值【分析】【分析】1.1.根據(jù)根據(jù)k k進(jìn)制數(shù)化十進(jìn)制數(shù)的規(guī)則列出進(jìn)制數(shù)化十進(jìn)制數(shù)的規(guī)則列出k k的方程即可的方程即可. .【解析】選【解析】選c.c.由由1 1k k2 2+3+3k k1 1+2+2k k0 0=30,=30, 得得k k2 2+3k-28=0 +3k-28=0 即即k=4k=4或或k=-7(k=-7(舍舍).).例例2.2.把十進(jìn)制數(shù)把十進(jìn)制數(shù)111111化為五進(jìn)制數(shù)是化為五進(jìn)制數(shù)是( )( ) (a)421 (a)421(5)(5) (b)521 (b)5

21、21(5) (5) (c)423(c)423(5)(5) (d)332 (d)332(5)(5)【分析】用【分析】用5 5連續(xù)去除連續(xù)去除111111，直到商為，直到商為0 0為止，然后將各步所得為止，然后將各步所得 的余數(shù)倒序?qū)懗?，即為相?yīng)的五進(jìn)制數(shù)的余數(shù)倒序?qū)懗?，即為相?yīng)的五進(jìn)制數(shù). .【解析】選【解析】選a.a.【練習(xí)】【練習(xí)】210(6)210(6)化成十進(jìn)制數(shù)為化成十進(jìn)制數(shù)為_，8585化成七進(jìn)制數(shù)為化成七進(jìn)制數(shù)為_【解析】【解析】210(6)210(6)2 262621 16 67878，所以所以8585151(7)151(7)【答案】【答案】7878151(7)151(7)b 課堂檢測(cè)2.4902.490和和910910的最大公約數(shù)為的最大公約數(shù)為( () )a a2 2b b1010c