《山東省高中數(shù)學(xué)(新課標(biāo)人教A版)必修三《1.3算法案例》.ppt》由會員分享，可在線閱讀，更多相關(guān)《山東省高中數(shù)學(xué)(新課標(biāo)人教A版)必修三《1.3算法案例》.ppt（23頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、【課標(biāo)要求】 1理解輾轉(zhuǎn)相除法與更相減損術(shù)的含義，了解其執(zhí)行過程 2理解秦九韶算法的計算過程，并了解它提高計算效率的實質(zhì) 3理解進位制的概念，能進行不同進位制間的轉(zhuǎn)化 4了解進位制的程序框圖和程序 【核心掃描】 1三種算法的原理及應(yīng)用(重難點) 2三種算法的框圖表示及程序(難點) 3不同進位制之間的相互轉(zhuǎn)化(重點) 4秦九韶算法中多項式的改寫(易錯點),1.3算法案例,輾轉(zhuǎn)相除法 (1)輾轉(zhuǎn)相除法，又叫歐幾里得算法，是一種求兩個正整數(shù)的___________的古老而有效的算法 (2)輾轉(zhuǎn)相除法的算法步驟 第一步，給定________________. 第二步，計算_______________
2、____. 第三步， ____________. 第四步，若r0，則m、n的最大公約數(shù)等于___；否則，返回________.,自學(xué)導(dǎo)引,1,最大公約數(shù),兩個正整數(shù)m，n,m除以n所得的余數(shù)r,mn，nr,m,第二步,更相減損術(shù) 第一步，任意給定兩個正整數(shù)，判斷它們是否都是_____若是，用_______；若不是，執(zhí)行_______ 第二步，以_____的數(shù)減去_____的數(shù)，接著把所得的差與_____的數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個操作，直到所得的數(shù)_____為止，則這個數(shù)(等數(shù))或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù) 任意給定兩個正整數(shù)，用輾轉(zhuǎn)相除法和更相減損術(shù)是否都可以求它們
3、的最大公約數(shù)？ 提示是更相減損術(shù)與輾轉(zhuǎn)相除法都能在有限步內(nèi)結(jié)束，故均可以用來求兩個正整數(shù)的最大公約數(shù),2,偶數(shù),2約簡,第二步,較小,較小,相等,較大,秦九韶算法 把一個n次多項式f(x)anxnan1xn1a1xa0改寫成如下形式： (((anxan1)xan2)xa1)xa0， 求多項式的值時，首先計算_____________一次多項式的值，即v1__________，然后由內(nèi)向外逐層計算一次多項式的值，即 v2__________， v3__________， vn__________. 這樣，求n次多項式f(x)的值就轉(zhuǎn)化為求________________的值,3,最內(nèi)層括號內(nèi),a
4、nxan1,v1xan2,v2xan3,vn1xa0,n個一次多項式,進位制 進位制是人們?yōu)榱薩____和_________而約定的記數(shù)系統(tǒng)，“滿k進一”就是k進制，k進制的基數(shù)是k. 把十進制轉(zhuǎn)化為k進制數(shù)時，通常用除k取余法 不同進制間的數(shù)不能比較大小，對嗎？ 提示不對不同的進位制是人們?yōu)榱擞嫈?shù)和運算方便而約定的記數(shù)系統(tǒng)，不同進位制的數(shù)照樣可比較大小，不過一般要轉(zhuǎn)化到十進制下比較大小更方便一些,4,計數(shù),運算方便,1輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別和聯(lián)系,名師點睛,秦九韶算法 (1)特點：通過一次式的反復(fù)計算，逐步得出高次多項式的值，對于一個n次多項式，只需做n次乘法和n次加法即可 (2)
5、算法步驟： 設(shè)Pn(x)anxnan1xn1a1xa0，將其改寫為 Pn(x)(anxn1an1xn2a1)xa0 ((anxn2an1xn3a2)xa1)xa0 (((anxan1)xan2)xa1)xa0. 第一步：計算最內(nèi)層anxan1的值，將anxan1的值賦給一個變量v1(為方便將an賦予變量v0)； 第二步：計算(anxan1)xan2的值，可以改寫為v1xan2，將v1xan2的值賦給一個變量v2；,2.,依次類推，即每一步的計算之后都賦予一個新值vk，即從最內(nèi)層的括號到最外層 括號的值依次賦予變量v1，v2，，vk，，vn，第n步所求值vnvn1xa0即為所求多項式的值 (3)
6、秦九韶算法有以下幾個優(yōu)點： 大大減少了乘法的次數(shù)，使計算量減小在計算機上做一次乘法所需要的時間是做加法、減法的幾倍到十幾倍，減少做乘法的次數(shù)也就加快了計算的速度； 規(guī)律性強，便于利用循環(huán)語句來實現(xiàn)算法； 避免了對自變量x單獨做冪的計算，每次都是計算一個一次多項式的值，從而可以提高計算的精度,關(guān)于進位制應(yīng)注意的問題 (1)十進制的原理是滿十進一一個十進制正整數(shù)N可以寫成an10nan110n1a1101a0100的形式，其中an，an1，，a1，a0都是0至9中的數(shù)字，且an0.例如36531026105. (2)一般地，k進制數(shù)的原理是滿k進一，k進制數(shù)一般在右下角處標(biāo)注(k)，以示區(qū)別例如2
7、70(8)表示270是一個8進制數(shù)但十進制一般省略不寫 (3)在k進制中，有： 有k個不同的數(shù)字符號，即0,1,2,3，，(k1)； “逢k進一”，即每位數(shù)計滿k后向高位進一 一個k進位制的正整數(shù)就是各位數(shù)碼與k的方冪的乘積的和，其中冪指數(shù)等于相應(yīng)數(shù)碼所在位數(shù)(從右往左數(shù))減1. 例如230 451(k)2k53k40k34k25k1.,3,題型一求兩個正整數(shù)的最大公約數(shù),分別用輾轉(zhuǎn)相除法和更相減損術(shù)求261和319的最大公約數(shù) 思路探索 使用輾轉(zhuǎn)相除法可依據(jù)mnqr，反復(fù)執(zhí)行直到余數(shù)為0；更相減損術(shù)則是根據(jù)mnr，反復(fù)執(zhí)行，直到nr為止 解法一(輾轉(zhuǎn)相除法) 3192611(余58)， 26
8、1584(余29)， 58292(余0)， 所以319與261的最大公約數(shù)為29.,【例1】,法二(更相減損術(shù)) 31926158， 26158203， 20358145， 1455887， 875829， 582929， 29290， 所以319與261的最大公約數(shù)是29.,規(guī)律方法(1)利用輾轉(zhuǎn)相除法求給定的兩個數(shù)的最大公約數(shù)，即利用帶余除法，用數(shù)對中較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對，再利用帶余除法，直到大數(shù)被小數(shù)除盡，則這時的較小數(shù)就是原來兩個數(shù)的最大公約數(shù) (2)利用更相減損術(shù)求兩個正整數(shù)的最大公約數(shù)的一般步驟是：首先判斷兩個正整數(shù)是否都是偶數(shù)若是，用
9、2約簡也可以不除以2，直接求最大公約數(shù)，這樣不影響最后結(jié)果,用輾轉(zhuǎn)相除法求80與36的最大公約數(shù)，并用更相減損術(shù)檢驗?zāi)愕慕Y(jié)果 解803628， 36844,8420， 即80與36的最大公約數(shù)是4. 驗證： 8024036218 402201829 209111192 927725 523321 2111224 所以80與36的最大公約數(shù)為4.,【變式1】,將七進制數(shù)235(7)轉(zhuǎn)化為八進制 解235(7)2723715124，利用除8取余法(如圖所示)，所以124174(8) 所以235(7)轉(zhuǎn)化為八進制數(shù)為174(8),題型二進位制之間的轉(zhuǎn)化,【例2】,規(guī)律方法對于非十進制數(shù)之間的互化，通
10、常是把這個數(shù)先轉(zhuǎn)化為十進制數(shù)，然后再利用除k取余法，把十進制數(shù)轉(zhuǎn)化為k進制數(shù)而在使用除k取余法時要注意以下幾點：(1)必須除到所得的商是0為止；(2)各步所得的余數(shù)必須從下到上排列；(3)切記在所求數(shù)的右下角標(biāo)明基數(shù),把下列各數(shù)轉(zhuǎ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)x2的值,題型三秦九韶算法在多項式中的應(yīng)用,【例3】,
11、規(guī)范解答 根據(jù)秦九韶算法，把多項式改寫成如下形式： f(x)((((3x8)x3)x5)x12)x6，按照從內(nèi)到外的順序，依次計算一次多項式當(dāng)x2時的值 (2分) v03， v1v02832814， (4分) v2v123142325， (6分) v3v225252555， (8分) v4v321255212122， v5v42612226238， (10分) 所以當(dāng)x2時，多項式的值為238. (12分),【題后反思】 (1)先將多項式寫成一次多項式的形式，然后運算時從里到外，一步一步地做乘法和加法即可這樣比直接將x2代入原式大大減少了計算量若用計算機計算，則可提高運算效
12、率 (2)注意：當(dāng)多項式中n次項不存在時，可將第n次項看作0 xn.,用秦九韶算法計算f(x)6x54x4x32x29x，需要加法(或減法)與乘法運算的次數(shù)分別為 () A5,4 B5,5 C4,4 D4,5 解析n次多項式需進行n次乘法；若各項均不為零，則需進行n次加法，缺一項就減少一次加法運算f(x)中無常數(shù)項，故加法次數(shù)要減少一次，為514.故選D. 答案D,【變式3】,已知f(x)x52x43x34x25x6，用秦九韶算法求這個多項式當(dāng)x2時的值時，做了幾次乘法？幾次加法？ 錯解 根據(jù)秦九韶算法，把多項式改寫成如下形式f(x)((((x2)x3)x4)x5)x6. 按照從內(nèi)到外的順序，
13、依次計算一次多項式當(dāng)x2時的 值：v1224；v22v1311；v32v2426；v42v3557；v52v46120. 顯然，在v1中未做乘法，只做了1次加法；在v2，v3，v4，v5中各做了1次加法，1次乘法因此，共做了4次乘法，5次加法,誤區(qū)警示對秦九韶算法中的運算次數(shù)理解錯誤,【示例】,在v1中雖然“v1224”，而計算機還是做了1次乘法“v12124”因為用秦九韶算法計算多項式f(x)anxnan1xn1a1xa0當(dāng)xx0時的值時，首先將多項式改寫成f(x)((anxan1)xa1)xa0，然后再計算v1anxan1，v2v1xan2，v3v2xan3，，vnvn1xa0.無論an是不是1，這次的乘法都是要進行的 正解 由上分析可知，共做了5次乘法，5次加法,單擊此處進入 活頁規(guī)范訓(xùn)練,
山東省高中數(shù)學(xué)(新課標(biāo)人教A版)必修三《1.3算法案例》.ppt
