13算法案例課件（人教A必修3）

1、【課標(biāo)要求課標(biāo)要求】1理解輾轉(zhuǎn)相除法與更相減損術(shù)的含義，了解其執(zhí)行過程理解輾轉(zhuǎn)相除法與更相減損術(shù)的含義，了解其執(zhí)行過程2理解秦九韶算法的計算過程，并了解它提高計算效率的實(shí)質(zhì)理解秦九韶算法的計算過程，并了解它提高計算效率的實(shí)質(zhì)3理解進(jìn)位制的概念，能進(jìn)行不同進(jìn)位制間的轉(zhuǎn)化理解進(jìn)位制的概念，能進(jìn)行不同進(jìn)位制間的轉(zhuǎn)化4了解進(jìn)位制的程序框圖和程序了解進(jìn)位制的程序框圖和程序【核心掃描核心掃描】1三種算法的原理及應(yīng)用三種算法的原理及應(yīng)用(重難點(diǎn)重難點(diǎn))2三種算法的框圖表示及程序三種算法的框圖表示及程序(難點(diǎn)難點(diǎn))3不同進(jìn)位制之間的相互轉(zhuǎn)化不同進(jìn)位制之間的相互轉(zhuǎn)化(重點(diǎn)重點(diǎn))4秦九韶算法中多項式的改寫秦九韶算

2、法中多項式的改寫(易錯點(diǎn)易錯點(diǎn))1.3算法案例算法案例輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法(1)輾轉(zhuǎn)相除法，又叫歐幾里得算法，是一種求兩個正整數(shù)輾轉(zhuǎn)相除法，又叫歐幾里得算法，是一種求兩個正整數(shù)的的_的古老而有效的算法的古老而有效的算法(2)輾轉(zhuǎn)相除法的算法步驟輾轉(zhuǎn)相除法的算法步驟第一步，給定第一步，給定_.第二步，計算第二步，計算_.第三步，第三步， _.第四步，若第四步，若r0，則，則m、n的最大公約數(shù)等于的最大公約數(shù)等于_；否則，；否則，返回返回_.自學(xué)導(dǎo)引自學(xué)導(dǎo)引1最大公約數(shù)最大公約數(shù)兩個正整數(shù)兩個正整數(shù)m，nm除以除以n所得的余數(shù)所得的余數(shù)rmn，nrm第二步第二步更相減損術(shù)更相減損術(shù)第一步，任意給定

3、兩個正整數(shù)，判斷它們是否都是第一步，任意給定兩個正整數(shù)，判斷它們是否都是_若若是，用是，用_；若不是，執(zhí)行；若不是，執(zhí)行_ 第二步，以第二步，以_的數(shù)減去的數(shù)減去_的數(shù)，接著把所得的差與的數(shù)，接著把所得的差與_的數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個操作，直到所得的數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個操作，直到所得的數(shù)的數(shù)_為止，則這個數(shù)為止，則這個數(shù)(等數(shù)等數(shù))或這個數(shù)與約簡的數(shù)的乘積或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù)就是所求的最大公約數(shù) 任意給定兩個正整數(shù)，用輾轉(zhuǎn)相除法和更相減損術(shù)是否任意給定兩個正整數(shù)，用輾轉(zhuǎn)相除法和更相減損術(shù)是否都可以求它們的最大公約數(shù)？都可以求它們的最大公約數(shù)？提示提

4、示是更相減損術(shù)與輾轉(zhuǎn)相除法都能在有限步內(nèi)結(jié)束，是更相減損術(shù)與輾轉(zhuǎn)相除法都能在有限步內(nèi)結(jié)束，故均可以用來求兩個正整數(shù)的最大公約數(shù)故均可以用來求兩個正整數(shù)的最大公約數(shù)2偶數(shù)偶數(shù)2約簡約簡第二步第二步較小較小較小較小相等相等較大較大秦九韶算法秦九韶算法把一個把一個n次多項式次多項式f(x)anxnan1xn1a1xa0改寫成如改寫成如下形式：下形式：(anxan1)xan2)xa1)xa0，求多項式的值時，首先計算求多項式的值時，首先計算_一次多項式的值，一次多項式的值，即即v1_，然后由內(nèi)向外逐層計算一次多項式的值，然后由內(nèi)向外逐層計算一次多項式的值，即即v2_，v3_，vn_.這樣，求這樣，求n

5、次多項式次多項式f(x)的值就轉(zhuǎn)化為求的值就轉(zhuǎn)化為求_的的值值3最內(nèi)層括號內(nèi)最內(nèi)層括號內(nèi)anxan1v1xan2v2xan3vn1xa0n個一次多項式個一次多項式進(jìn)位制進(jìn)位制進(jìn)位制是人們?yōu)榱诉M(jìn)位制是人們?yōu)榱薩和和_而約定的記數(shù)系統(tǒng)，而約定的記數(shù)系統(tǒng)，“滿滿k進(jìn)一進(jìn)一”就是就是k進(jìn)制，進(jìn)制，k進(jìn)制的基數(shù)是進(jìn)制的基數(shù)是k.把十進(jìn)制轉(zhuǎn)化為把十進(jìn)制轉(zhuǎn)化為k進(jìn)制數(shù)時，通常用除進(jìn)制數(shù)時，通常用除k取余法取余法 不同進(jìn)制間的數(shù)不能比較大小，對嗎？不同進(jìn)制間的數(shù)不能比較大小，對嗎？提示提示不對不同的進(jìn)位制是人們?yōu)榱擞嫈?shù)和運(yùn)算方便而不對不同的進(jìn)位制是人們?yōu)榱擞嫈?shù)和運(yùn)算方便而約定的記數(shù)系統(tǒng)，不同進(jìn)位制的數(shù)照樣可比

6、較大小，不過約定的記數(shù)系統(tǒng)，不同進(jìn)位制的數(shù)照樣可比較大小，不過一般要轉(zhuǎn)化到十進(jìn)制下比較大小更方便一些一般要轉(zhuǎn)化到十進(jìn)制下比較大小更方便一些4計數(shù)計數(shù)運(yùn)算方便運(yùn)算方便1輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別和聯(lián)系輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別和聯(lián)系名師點(diǎn)睛名師點(diǎn)睛名稱名稱輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法更相減損術(shù)更相減損術(shù)區(qū)別區(qū)別以除法為主以除法為主兩個整數(shù)差值較大兩個整數(shù)差值較大時運(yùn)算次數(shù)較少時運(yùn)算次數(shù)較少相除余數(shù)為零時得相除余數(shù)為零時得結(jié)果結(jié)果以減法為主以減法為主兩個整數(shù)的差值較大兩個整數(shù)的差值較大時，運(yùn)算次數(shù)較多時，運(yùn)算次數(shù)較多相減，兩數(shù)相等得結(jié)相減，兩數(shù)相等得結(jié)果果相減前要做是否都是相減前要做是否都是偶數(shù)的判斷

7、偶數(shù)的判斷聯(lián)系聯(lián)系都是求兩個正整數(shù)的最大公約數(shù)的方法都是求兩個正整數(shù)的最大公約數(shù)的方法二者的實(shí)質(zhì)都是遞推的過程二者的實(shí)質(zhì)都是遞推的過程二者都要用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)二者都要用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)秦九韶算法秦九韶算法(1)特點(diǎn)：通過一次式的反復(fù)計算，逐步得出高次多項式的特點(diǎn)：通過一次式的反復(fù)計算，逐步得出高次多項式的值，對于一個值，對于一個n次多項式，只需做次多項式，只需做n次乘法和次乘法和n次加法即次加法即可可(2)算法步驟：算法步驟：設(shè)設(shè)Pn(x)anxnan1xn1a1xa0，將其改寫為，將其改寫為Pn(x)(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1

8、)xan2)xa1)xa0.第一步：計算最內(nèi)層第一步：計算最內(nèi)層anxan1的值，將的值，將anxan1的值賦給的值賦給一個變量一個變量v1(為方便將為方便將an賦予變量賦予變量v0)；第二步：計算第二步：計算(anxan1)xan2的值，可以改寫為的值，可以改寫為v1xan2，將，將v1xan2的值賦給一個變量的值賦給一個變量v2；2.依次類推，即每一步的計算之后都賦予一個新值依次類推，即每一步的計算之后都賦予一個新值vk，即從，即從最內(nèi)層的括號到最外層最內(nèi)層的括號到最外層括號的值依次賦予變量括號的值依次賦予變量v1，v2，vk，vn，第，第n步所步所求值求值vnvn1xa0即為所求多項式的

9、值即為所求多項式的值(3)秦九韶算法有以下幾個優(yōu)點(diǎn)：秦九韶算法有以下幾個優(yōu)點(diǎn)：大大減少了乘法的次數(shù)，使計算量減小在計算機(jī)上做大大減少了乘法的次數(shù)，使計算量減小在計算機(jī)上做一次乘法所需要的時間是做加法、減法的幾倍到十幾倍，一次乘法所需要的時間是做加法、減法的幾倍到十幾倍，減少做乘法的次數(shù)也就加快了計算的速度；減少做乘法的次數(shù)也就加快了計算的速度；規(guī)律性強(qiáng)，便于利用循環(huán)語句來實(shí)現(xiàn)算法；規(guī)律性強(qiáng)，便于利用循環(huán)語句來實(shí)現(xiàn)算法；避免了對自變量避免了對自變量x單獨(dú)做冪的計算，每次都是計算一個單獨(dú)做冪的計算，每次都是計算一個一次多項式的值，從而可以提高計算的精度一次多項式的值，從而可以提高計算的精度關(guān)于進(jìn)位

10、制應(yīng)注意的問題關(guān)于進(jìn)位制應(yīng)注意的問題(1)十進(jìn)制的原理是滿十進(jìn)一一個十進(jìn)制正整數(shù)十進(jìn)制的原理是滿十進(jìn)一一個十進(jìn)制正整數(shù)N可以寫可以寫成成an10nan110n1a1101a0100的形式，的形式，其中其中an，an1，a1，a0都是都是0至至9中的數(shù)字，且中的數(shù)字，且an0.例例如如36531026105.(2)一般地，一般地，k進(jìn)制數(shù)的原理是滿進(jìn)制數(shù)的原理是滿k進(jìn)一，進(jìn)一，k進(jìn)制數(shù)一般在右進(jìn)制數(shù)一般在右下角處標(biāo)注下角處標(biāo)注(k)，以示區(qū)別例如，以示區(qū)別例如270(8)表示表示270是一個是一個8進(jìn)進(jìn)制數(shù)但十進(jìn)制一般省略不寫制數(shù)但十進(jìn)制一般省略不寫(3)在在k進(jìn)制中，有：進(jìn)制中，有：有有k個不

11、同的數(shù)字符號，即個不同的數(shù)字符號，即0,1,2,3，(k1)；“逢逢k進(jìn)一進(jìn)一”，即每位數(shù)計滿，即每位數(shù)計滿k后向高位進(jìn)一后向高位進(jìn)一一個一個k進(jìn)位制的正整數(shù)就是各位數(shù)碼與進(jìn)位制的正整數(shù)就是各位數(shù)碼與k的方冪的乘積的的方冪的乘積的和，其中冪指數(shù)等于相應(yīng)數(shù)碼所在位數(shù)和，其中冪指數(shù)等于相應(yīng)數(shù)碼所在位數(shù)(從右往左數(shù)從右往左數(shù))減減1.例如例如230 451(k)2k53k40k34k25k1.3題型一題型一求兩個正整數(shù)的最大公約數(shù)求兩個正整數(shù)的最大公約數(shù) 分別用輾轉(zhuǎn)相除法和更相減損術(shù)求分別用輾轉(zhuǎn)相除法和更相減損術(shù)求261和和319的最大公的最大公約數(shù)約數(shù)思路探索思路探索 使用輾轉(zhuǎn)相除法可依據(jù)使用輾轉(zhuǎn)

12、相除法可依據(jù)mnqr，反復(fù)執(zhí)行直，反復(fù)執(zhí)行直到余數(shù)為到余數(shù)為0；更相減損術(shù)則是根據(jù)；更相減損術(shù)則是根據(jù)mnr，反復(fù)執(zhí)行，反復(fù)執(zhí)行，直到直到nr為止為止解解法一法一(輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法)3192611(余余58)，261584(余余29)，58292(余余0)，所以所以319與與261的最大公約數(shù)為的最大公約數(shù)為29.【例例1】法二法二(更相減損術(shù)更相減損術(shù))31926158，26158203，20358145，1455887，875829，582929，29290，所以所以319與與261的最大公約數(shù)是的最大公約數(shù)是29.規(guī)律方法規(guī)律方法(1)利用輾轉(zhuǎn)相除法求給定的兩個數(shù)的最大公約利用輾轉(zhuǎn)相

13、除法求給定的兩個數(shù)的最大公約數(shù)，即利用帶余除法，用數(shù)對中較大的數(shù)除以較小的數(shù)，數(shù)，即利用帶余除法，用數(shù)對中較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對，再利若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對，再利用帶余除法，直到大數(shù)被小數(shù)除盡，則這時的較小數(shù)就是用帶余除法，直到大數(shù)被小數(shù)除盡，則這時的較小數(shù)就是原來兩個數(shù)的最大公約數(shù)原來兩個數(shù)的最大公約數(shù)(2)利用更相減損術(shù)求兩個正整數(shù)的最大公約數(shù)的一般步驟利用更相減損術(shù)求兩個正整數(shù)的最大公約數(shù)的一般步驟是：首先判斷兩個正整數(shù)是否都是偶數(shù)若是，用是：首先判斷兩個正整數(shù)是否都是偶數(shù)若是，用2約約簡也可以不除以簡也可以不除以2，直接

14、求最大公約數(shù)，這樣不影響最，直接求最大公約數(shù)，這樣不影響最后結(jié)果后結(jié)果 用輾轉(zhuǎn)相除法求用輾轉(zhuǎn)相除法求80與與36的最大公約數(shù)，并用更相減的最大公約數(shù)，并用更相減損術(shù)檢驗?zāi)愕慕Y(jié)果損術(shù)檢驗?zāi)愕慕Y(jié)果解解803628，36844,8420，即即80與與36的最大公約數(shù)是的最大公約數(shù)是4.驗證：驗證：80240362184022018292091111929277255233212111224所以所以80與與36的最大公約數(shù)為的最大公約數(shù)為4.【變式變式1】 將七進(jìn)制數(shù)將七進(jìn)制數(shù)235(7)轉(zhuǎn)化為八進(jìn)制轉(zhuǎn)化為八進(jìn)制解解235(7)2723715124，利用除，利用除8取余法取余法(如圖所示如圖所示)，所

15、以，所以124174(8)所以所以235(7)轉(zhuǎn)化為八進(jìn)制數(shù)為轉(zhuǎn)化為八進(jìn)制數(shù)為174(8)題型題型二二進(jìn)位制之間的轉(zhuǎn)化進(jìn)位制之間的轉(zhuǎn)化【例例2】規(guī)律方法規(guī)律方法對于非十進(jìn)制數(shù)之間的互化，通常是把這個數(shù)對于非十進(jìn)制數(shù)之間的互化，通常是把這個數(shù)先轉(zhuǎn)化為十進(jìn)制數(shù)，然后再利用除先轉(zhuǎn)化為十進(jìn)制數(shù)，然后再利用除k取余法，把十進(jìn)制數(shù)取余法，把十進(jìn)制數(shù)轉(zhuǎn)化為轉(zhuǎn)化為k進(jìn)制數(shù)而在使用除進(jìn)制數(shù)而在使用除k取余法時要注意以下幾點(diǎn)：取余法時要注意以下幾點(diǎn)：(1)必須除到所得的商是必須除到所得的商是0為止；為止；(2)各步所得的余數(shù)必須從各步所得的余數(shù)必須從下到上排列；下到上排列；(3)切記在所求數(shù)的右下角標(biāo)明基數(shù)切記在

16、所求數(shù)的右下角標(biāo)明基數(shù) 把下列各數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)把下列各數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)(1)101 101(2)；(2)2 102(3)；(3)4 301(6)解解(1)101 101(2)12502412312202145.(2)2 102(3)233132265.(3)4 301(6)4633621973.【變式變式2】 用秦九韶算法求用秦九韶算法求f(x)3x58x43x35x212x6，當(dāng)，當(dāng)x2的值的值題型題型三三秦九韶算法在多項式中的應(yīng)用秦九韶算法在多項式中的應(yīng)用【例例3】規(guī)范解答規(guī)范解答 根據(jù)秦九韶算法，把多項式改寫成如下形式：根據(jù)秦九韶算法，把多項式改寫成如下形式：f(x)(3x8)x3)x

17、5)x12)x6，按照從內(nèi)到外的順，按照從內(nèi)到外的順序，依次計算一次多項式當(dāng)序，依次計算一次多項式當(dāng)x2時的值時的值 (2分分)v03，v1v02832814， (4分分)v2v123142325， (6分分)v3v225252555， (8分分)v4v321255212122，v5v42612226238， (10分分)所以當(dāng)所以當(dāng)x2時，多項式的值為時，多項式的值為238. (12分分)【題后反思題后反思】 (1)先將多項式寫成一次多項式的形式，然先將多項式寫成一次多項式的形式，然后運(yùn)算時從里到外，一步一步地做乘法和加法即可這樣后運(yùn)算時從里到外，一步一步地做乘法和加法即可這樣比直接將比直接

18、將x2代入原式大大減少了計算量若用計算機(jī)計代入原式大大減少了計算量若用計算機(jī)計算，則可提高運(yùn)算效率算，則可提高運(yùn)算效率(2)注意：當(dāng)多項式中注意：當(dāng)多項式中n次項不存在時，可將第次項不存在時，可將第n次項看作次項看作0 xn. 用秦九韶算法計算用秦九韶算法計算f(x)6x54x4x32x29x，需，需要加法要加法(或減法或減法)與乘法運(yùn)算的次數(shù)分別為與乘法運(yùn)算的次數(shù)分別為 ()A5,4 B5,5 C4,4 D4,5解析解析n次多項式需進(jìn)行次多項式需進(jìn)行n次乘法；若各項均不為零，則需次乘法；若各項均不為零，則需進(jìn)行進(jìn)行n次加法，缺一項就減少一次加法運(yùn)算次加法，缺一項就減少一次加法運(yùn)算f(x)中無常數(shù)中無常數(shù)項，故加法次數(shù)要減少一次，為項，故加法次數(shù)要減少一次，為514.故選故選D.答案答案D【變式變式3】 已知已知f(x)x52x43x34x25x6，用秦九韶算法，用秦九韶算法求這個多項式當(dāng)求這個多項式當(dāng)x2時的