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

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

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

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

5、兩個正整數的最大公約數,例1分別用輾轉相除法和更相減損術求261和319的最大公約數.,解方法一(輾轉相除法) 3192611(余58)， 261584(余29)， 58292(余0)， 所以319與261的最大公約數為29.,方法二(更相減損術) 31926158， 26158203， 20358145， 1455887， 875829， 582929， 29290， 所以319與261的最大公約數是29.,解析答案,反思與感悟,反思與感悟,(1)利用輾轉相除法求給定的兩個數的最大公約數，即利用帶余除法，用數對中較大的數除以較小的數，若余數不為零，則將余數和較小的數構成新的數對，再利用帶余除

6、法，直到大數被小數除盡，則這時的較小數就是原來兩個數的最大公約數. (2)利用更相減損術求兩個正整數的最大公約數的一般步驟是：首先判斷兩個正整數是否都是偶數.若是，用2約簡.也可以不除以2，直接求最大公約數，這樣不影響最后結果.,跟蹤訓練1用輾轉相除法求80與36的最大公約數，并用更相減損術檢驗你的結果.,解803628，36844,8420， 即80與36的最大公約數是4. 驗證： 80240,36218；40220,1829； 20911,1192；927,725； 523,321；211,1224； 所以80與36的最大公約數為4.,解析答案,題型二秦九韶算法的應用,例2用秦九韶算法求多

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

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

9、,(2)將8進制數314706(8)化為十進制數.,解314706(8)385184483782081680104902. 所以，化為十進制數是104902.,解析答案,反思與感悟,反思與感悟,(1)將k進制轉化為十進制的方法是：先將這個k進制數寫成各個數位上的數字與k的冪的乘積之和的形式，再按照十進制的運算規(guī)則計算出結果. (2)十進制轉化為k進制，采用除k取余法，也就是除基數，倒取余.,跟蹤訓練3將53(8)轉化為二進制數.,解先將八進制數53(8)轉化為十進制數： 53(8)58138043； 再將十進制數43轉化為二進制數：,所以53(8)101011(2).,解析答案,轉化與化歸思想

10、,思想方法,例4下列各數中，最小的數是() A.85(9) B.210(6)C.1000(4)D.111111(2),分析先將它們轉化為十進制數，再進行比較.,解析85(9)89577, 210(6)26216078, 1000(4)14364, 111111(2)12512412312212163. 故最小的是63.,D,解析答案,解后反思,分析,解后反思合理的轉化是解題的關鍵.對于進位制之間的轉化問題，一般要先把k進制數轉化為十進制數，再轉化為其他進制數.,數制轉化方法掌握不牢致錯,易錯點,例5把十字進制數49化為二進制數.,分析對進位制間的換算，要弄清解題的辦法，將十進制數轉化為k進制數

11、用“除k取余法”.,解,所以49110 001(2).,解后反思本例常出現的錯誤是把上式中各步所得的余數從上到下排列，這是基本方法掌握不牢造成的，應加以注意.,分析,解析答案,解后反思,返回,當堂檢測,1,2,3,4,5,1.1 337與382的最大公約數是() A.3 B.382 C.191 D.201,解析利用輾轉相除法，1 3373823191,3821912， 故兩數的最大公約數為191.,C,解析答案,1,2,3,4,5,2.把189化為三進制數，則末位數字是() A.0 B.1 C.2 D.3,解析采用“除k取余法”，得,即18921 000(3),A,解析答案,1,2,3,4,5

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