高中數(shù)學(xué) 第1章 算法初步 1.3 算法案例 新人教版必修3

1、第一章算法初步,1.3算法案例,學(xué)習(xí)目標(biāo),1.理解輾轉(zhuǎn)相除法與更相減損術(shù)的含義，了解其執(zhí)行過程. 2.理解秦九韶算法的計(jì)算過程，并了解它提高計(jì)算效率的實(shí)質(zhì). 3.理解進(jìn)位制的概念，能進(jìn)行不同進(jìn)位制間的轉(zhuǎn)化. 4.了解進(jìn)位制的程序框圖和程序,知識梳理 自主學(xué)習(xí),題型探究 重點(diǎn)突破,當(dāng)堂檢測 自查自糾,欄目索引,知識梳理 自主學(xué)習(xí),知識點(diǎn)一輾轉(zhuǎn)相除法與更相減損術(shù),1.輾轉(zhuǎn)相除法 (1)輾轉(zhuǎn)相除法，又叫歐幾里得算法，是一種求兩個(gè)正整數(shù)的 的古老而有效的算法. (2)輾轉(zhuǎn)相除法的算法步驟 第一步，給定 . 第二步，計(jì)算 . 第三步， . 第四步，若r0，則m，n的最大公約數(shù)等于 ；否則，返回,最大公約

2、數(shù),兩個(gè)正整數(shù)m，n,m除以n所得的余數(shù)r,mn，nr,m,第二步,答案,2.更相減損術(shù) 第一步，任意給定兩個(gè)正整數(shù)，判斷它們是否都是 .若是，用 約簡；若不是，執(zhí)行 . 第二步，以 的數(shù)減去 的數(shù)，接著把所得的差與 的數(shù)比較，并以大數(shù)減小數(shù).繼續(xù)這個(gè)操作，直到所得的數(shù) 為止，則這個(gè)數(shù)(等數(shù))或這個(gè)數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù),偶數(shù),2,第二步,較大,較小,較小,相等,答案,3.輾轉(zhuǎn)相除法和更相減損術(shù)的區(qū)別與聯(lián)系,思考實(shí)際應(yīng)用更相減損術(shù)時(shí)要做的第一步工作是什么,答先判斷a，b是否為偶數(shù)，若是，都除以2再進(jìn)行,答案,知識點(diǎn)二秦九韶算法,1.秦九韶算法簡介 (1)秦九韶算法要解決的問題是

3、求多項(xiàng)式的值. (2)秦九韶算法的特點(diǎn)： 通過一次式的反復(fù)計(jì)算，逐步得到高次多項(xiàng)式的值，即將一個(gè)n次多項(xiàng)式的求值問題歸結(jié)為重復(fù)計(jì)算n個(gè)一次多項(xiàng)式的值的問題,3)秦九韶算法的原理： 將f(x)anxnan1xn1a1xa0改寫為： f(x)(anxn1an1xn2a1)xa0 (anxn2an1xn3a2)xa1)xa0,先計(jì)算最內(nèi)層括號內(nèi)一次多項(xiàng)式的值，即v1anxan1，再由內(nèi)向外逐層計(jì)算一次多項(xiàng)式vk的值,2.秦九韶算法的操作方法 (1)算法步驟如下： 第一步，輸入多項(xiàng)式次數(shù)n、最高次項(xiàng)的系數(shù)an和x的值. 第二步，將v的值初始化為an，將i的值初始化為n1. 第三步，輸入i次項(xiàng)的系數(shù)ai

4、. 第四步，vvxai，ii1. 第五步，判斷i是否大于或等于0.若是，則返回第三步；否則，輸出多項(xiàng)式的值v,2)程序框圖如圖所示,3)程序如下,知識點(diǎn)三進(jìn)位制,1.進(jìn)位制的概念 進(jìn)位制是為了計(jì)數(shù)和運(yùn)算方便而約定的記數(shù)系統(tǒng)，約定“滿幾進(jìn)一”就是幾進(jìn)制，幾進(jìn)制的基數(shù)(大于1的整數(shù))就是幾. 2.常見的進(jìn)位制 (1)二進(jìn)制： 只使用0和1兩個(gè)數(shù)學(xué)； 滿二進(jìn)一，即1110(2). (2)八進(jìn)制； 使用0,1,2,3,4,5,6,7這八個(gè)不同數(shù)學(xué)； 滿八進(jìn)一，即7110(8,思考任何進(jìn)位制中都要用到的數(shù)字是什么,答0和1,返回,答案,題型探究 重點(diǎn)突破,題型一求兩個(gè)正整數(shù)的最大公約數(shù),例1分別用輾轉(zhuǎn)相

5、除法和更相減損術(shù)求261和319的最大公約數(shù),解方法一(輾轉(zhuǎn)相除法) 3192611(余58)， 261584(余29)， 58292(余0)， 所以319與261的最大公約數(shù)為29,方法二(更相減損術(shù)) 31926158， 26158203， 20358145， 1455887， 875829， 582929， 29290， 所以319與261的最大公約數(shù)是29,解析答案,反思與感悟,反思與感悟,1)利用輾轉(zhuǎn)相除法求給定的兩個(gè)數(shù)的最大公約數(shù)，即利用帶余除法，用數(shù)對中較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對，再利用帶余除法，直到大數(shù)被小數(shù)除盡，則這時(shí)的較小數(shù)就是原來兩

6、個(gè)數(shù)的最大公約數(shù). (2)利用更相減損術(shù)求兩個(gè)正整數(shù)的最大公約數(shù)的一般步驟是：首先判斷兩個(gè)正整數(shù)是否都是偶數(shù).若是，用2約簡.也可以不除以2，直接求最大公約數(shù)，這樣不影響最后結(jié)果,跟蹤訓(xùn)練1用輾轉(zhuǎn)相除法求80與36的最大公約數(shù)，并用更相減損術(shù)檢驗(yàn)?zāi)愕慕Y(jié)果,解803628，36844,8420， 即80與36的最大公約數(shù)是4. 驗(yàn)證： 80240,36218；40220,1829； 20911,1192；927,725； 523,321；211,1224； 所以80與36的最大公約數(shù)為4,解析答案,題型二秦九韶算法的應(yīng)用,例2用秦九韶算法求多項(xiàng)式f(x)x55x410 x310 x25x1當(dāng)x2

7、時(shí)的值,解f(x)x55x410 x310 x25x1(x5)x10)x10)x5)x1. 當(dāng)x2時(shí)，有v01； v1v0 xa41(2)53； v2v1xa33(2)104； v3v2xa24(2)102； v4v3xa12(2)51； v5v4xa01(2)11. 故f(2)1,解析答案,反思與感悟,反思與感悟,1)先將多項(xiàng)式寫成一次多項(xiàng)式的形式，然后運(yùn)算時(shí)從里到外，一步一步地做乘法和加法即可.這樣比直接將x2代入原式大大減少了計(jì)算量.若用計(jì)算機(jī)計(jì)算，則可提高運(yùn)算效率. (2)注意：當(dāng)多項(xiàng)式中n次項(xiàng)不存在時(shí)，可將第n次項(xiàng)看作0 xn,跟蹤訓(xùn)練2用秦九韶算法計(jì)算多項(xiàng)式f(x)x612x560

8、 x4160 x3240 x2192x64當(dāng)x2時(shí)的值,解根據(jù)秦九韶算法，把多項(xiàng)式改寫成如下形式： f(x)(x12)x60)x160)x240)x192)x64. 由內(nèi)向外依次計(jì)算一次多項(xiàng)式當(dāng)x2時(shí)的值； v01；v1121210； v21026040；v340216080； v480224080；v580219232； v6322640. 所以當(dāng)x2時(shí)，多項(xiàng)式的值為0,解析答案,題型三進(jìn)位制之間的互化,例3(1)把二進(jìn)制數(shù)1110011(2)化為十進(jìn)制數(shù),解1110011(2)1261251240230221211115,2)將8進(jìn)制數(shù)314706(8)化為十進(jìn)制數(shù),解314706(8)3

9、85184483782081680104902. 所以，化為十進(jìn)制數(shù)是104902,解析答案,反思與感悟,反思與感悟,1)將k進(jìn)制轉(zhuǎn)化為十進(jìn)制的方法是：先將這個(gè)k進(jìn)制數(shù)寫成各個(gè)數(shù)位上的數(shù)字與k的冪的乘積之和的形式，再按照十進(jìn)制的運(yùn)算規(guī)則計(jì)算出結(jié)果. (2)十進(jìn)制轉(zhuǎn)化為k進(jìn)制，采用除k取余法，也就是除基數(shù)，倒取余,跟蹤訓(xùn)練3將53(8)轉(zhuǎn)化為二進(jìn)制數(shù),解先將八進(jìn)制數(shù)53(8)轉(zhuǎn)化為十進(jìn)制數(shù)： 53(8)58138043； 再將十進(jìn)制數(shù)43轉(zhuǎn)化為二進(jìn)制數(shù),所以53(8)101011(2,解析答案,轉(zhuǎn)化與化歸思想,思想方法,例4下列各數(shù)中，最小的數(shù)是() A.85(9) B.210(6)C.1000

10、(4)D.111111(2,分析先將它們轉(zhuǎn)化為十進(jìn)制數(shù)，再進(jìn)行比較,解析85(9)89577, 210(6)26216078, 1000(4)14364, 111111(2)12512412312212163. 故最小的是63,D,解析答案,解后反思,分析,解后反思合理的轉(zhuǎn)化是解題的關(guān)鍵.對于進(jìn)位制之間的轉(zhuǎn)化問題，一般要先把k進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)，再轉(zhuǎn)化為其他進(jìn)制數(shù),數(shù)制轉(zhuǎn)化方法掌握不牢致錯(cuò),易錯(cuò)點(diǎn),例5把十字進(jìn)制數(shù)49化為二進(jìn)制數(shù),分析對進(jìn)位制間的換算，要弄清解題的辦法，將十進(jìn)制數(shù)轉(zhuǎn)化為k進(jìn)制數(shù)用“除k取余法,解,所以49110 001(2,解后反思本例常出現(xiàn)的錯(cuò)誤是把上式中各步所得的余數(shù)從

11、上到下排列，這是基本方法掌握不牢造成的，應(yīng)加以注意,分析,解析答案,解后反思,返回,當(dāng)堂檢測,1,2,3,4,5,1.1 337與382的最大公約數(shù)是() A.3 B.382 C.191 D.201,解析利用輾轉(zhuǎn)相除法，1 3373823191,3821912， 故兩數(shù)的最大公約數(shù)為191,C,解析答案,1,2,3,4,5,2.把189化為三進(jìn)制數(shù)，則末位數(shù)字是() A.0 B.1 C.2 D.3,解析采用“除k取余法”，得,即18921 000(3,A,解析答案,1,2,3,4,5,3.用秦九韶算法求n次多項(xiàng)式f(x)anxnan1xn1a1xa0當(dāng)xx0時(shí)的值，求f(x0)需要乘方、乘法、

12、加法的次數(shù)分別為(,A. ，n，n B.n,2n，n C.0,2n，n D.0，n，n,解析因?yàn)閒(x)(anxan1)xan2)xa1)xa0， 所以乘方、乘法、加法的次數(shù)分別為0，n，n,D,解析答案,1,2,3,4,5,4.用秦九韶算法求多項(xiàng)式f(x)7x66x53x22，當(dāng)x4時(shí)的值時(shí)，先算的是() A.4416 B.7428 C.44464 D.74634,解析因?yàn)閒(x)anxnan1xn1a1xa0 (anxan1)xan2)xa1)xa0， 所以用秦九韶算法求多項(xiàng)式f(x)7x66x53x22當(dāng)x4時(shí)的值時(shí)，先算的是74634,D,解析答案,1,2,3,4,5,5.用更相減損術(shù)求36與134的最大公約數(shù)，第一步應(yīng)為_ _,解析36與134都是偶數(shù)， 第一步應(yīng)為：先除以2，得到18與67,先除以2，得到,18與67,解析答案,課堂小結(jié),返回,1.求兩個(gè)正整數(shù)的最大公約數(shù)的問題，可以用輾轉(zhuǎn)相除法，也可以用更相減損術(shù).用輾轉(zhuǎn)相除法，即根據(jù)anbr這個(gè)式子，反復(fù)相除，直到r0為止；用更相減損術(shù)，即根據(jù)r|ab|這個(gè)式子，反復(fù)相減，