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