學必求其心得，業必貴于專精學必求其心得，業必貴于專精PAGEPAGE16學必求其心得，業必貴于專精1.3算法案例［學習目標］1。理解輾轉相除法與更相減損術的含義,了解其執行過程.2.理解秦九韶算法的計算過程，并了解它提高計算效率的實質.3.理解進位制的概念，能進行不同進位制間的轉化。4。了解進位制的程序框圖和程序．知識點一輾轉相除法與更相減損術1．輾轉相除法（1）輾轉相除法，又叫歐幾里得算法,是一種求兩個正整數的最大公約數的古老而有效的算法．（2）輾轉相除法的算法步驟第一步，給定兩個正整數m，n.第二步,計算m除以n所得的余數r。第三步，m＝n，n＝r.第四步，若r＝0，則m,n的最大公約數等于m；否則,返回第二步．2．更相減損術第一步,任意給定兩個正整數，判斷它們是否都是偶數．若是，用2約簡；若不是,執行第二步．第二步,以較大的數減去較小的數，接著把所得的差與較小的數比較，并以大數減小數．繼續這個操作，直到所得的數相等為止，則這個數（等數）或這個數與約簡的數的乘積就是所求的最大公約數．3．輾轉相除法和更相減損術的區別與聯系：名稱輾轉相除法更相減損術區別（1）以除法為主；(2）兩個整數的差值較大時，運算次數較少；(3)相除，余數為0時得結果（1)以減法為主；(2）兩個整數的差值較大時，運算次數較多；(3）相減，減數與差相等時得結果；（4）相減前要進行是否都是偶數的判斷聯系(1)都是求兩個正整數最大公約數的方法；(2）二者的實質都是遞推的過程；（3)二者都要用循環結構來實現思考實際應用更相減損術時要做的第一步工作是什么？答先判斷a，b是否為偶數，若是,都除以2再進行．知識點二秦九韶算法1．秦九韶算法簡介(1）秦九韶算法要解決的問題是求多項式的值．(2)秦九韶算法的特點:通過一次式的反復計算，逐步得到高次多項式的值，即將一個n次多項式的求值問題歸結為重復計算n個一次多項式的值的問題．(3)秦九韶算法的原理：將f（x)＝anxn＋an－1xn－1＋…＋a1x＋a0改寫為：f(x）＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0＝((anxn－2＋an－1xn－3＋…＋a2）x＋a1）x＋a0＝…先計算最內層括號內一次多項式的值，即v1＝anx＋an－1,再由內向外逐層計算一次多項式vk的值．2．秦九韶算法的操作方法（1）算法步驟如下：第一步，輸入多項式次數n、最高次項的系數an和x的值．第二步，將v的值初始化為an，將i的值初始化為n－1。第三步，輸入i次項的系數ai。第四步，v＝vx＋ai,i＝i－1.第五步,判斷i是否大于或等于0.若是，則返回第三步;否則，輸出多項式的值v。(2)程序框圖如圖所示．(3)程序如下：INPUT“n＝”；nINPUT“an＝”；aINPUT“x＝”；xv＝ai＝n－1WHILEi＞＝0PRINT“i＝”；iINPUT“ai＝”;av＝v*x＋ai＝i－1WENDPRINTvEND知識點三進位制1．進位制的概念進位制是為了計數和運算方便而約定的記數系統,約定“滿幾進一”就是幾進制,幾進制的基數(大于1的整數）就是幾．2．常見的進位制(1）二進制:①只使用0和1兩個數學；②滿二進一,即1＋1＝10（2)．(2)八進制：①使用0，1，2,3,4，5，6，7這八個不同數學；②滿八進一，即7＋1＝10(8）．(3）十六進制：①使用0～9十個數字和A～F表示10～15；②F＋1＝10（16）思考任何進位制中都要用到的數字是什么？答0和1.題型一求兩個正整數的最大公約數例1分別用輾轉相除法和更相減損術求261和319的最大公約數．解方法一(輾轉相除法)319÷261＝1（余58)，261÷58＝4（余29）,58÷29＝2（余0)，所以319與261的最大公約數為29.方法二(更相減損術）319－261＝58,261－58＝203,203－58＝145，145－58＝87,87－58＝29，58－29＝29,29－29＝0，所以319與261的最大公約數是29。反思與感悟(1）利用輾轉相除法求給定的兩個數的最大公約數，即利用帶余除法，用數對中較大的數除以較小的數,若余數不為零，則將余數和較小的數構成新的數對，再利用帶余除法，直到大數被小數除盡，則這時的較小數就是原來兩個數的最大公約數．（2）利用更相減損術求兩個正整數的最大公約數的一般步驟是：首先判斷兩個正整數是否都是偶數．若是,用2約簡．也可以不除以2,直接求最大公約數，這樣不影響最后結果．跟蹤訓練1用輾轉相除法求80與36的最大公約數,并用更相減損術檢驗你的結果．解80＝36×2＋8，36＝8×4＋4，8＝4×2＋0，即80與36的最大公約數是4.驗證：80÷2＝40,36÷2＝18；40÷2＝20,18÷2＝9；20—9＝11,11－9＝2；9－2＝7,7－2＝5；5－2＝3，3－2＝1;2－1＝1,1×2×2＝4；所以80與36的最大公約數為4。題型二秦九韶算法的應用例2用秦九韶算法求多項式f（x）＝x5＋5x4＋10x3＋10x2＋5x＋1當x＝－2時的值．解f（x）＝x5＋5x4＋10x3＋10x2＋5x＋1＝(（(（x＋5)x＋10)x＋10）x＋5）x＋1。當x＝－2時，有v0＝1；v1＝v0x＋a4＝1×(－2)＋5＝3；v2＝v1x＋a3＝3×（－2）＋10＝4；v3＝v2x＋a2＝4×（－2)＋10＝2；v4＝v3x＋a1＝2×(－2)＋5＝1；v5＝v4x＋a0＝1×(－2）＋1＝－1。故f（－2)＝－1。反思與感悟(1）先將多項式寫成一次多項式的形式,然后運算時從里到外，一步一步地做乘法和加法即可．這樣比直接將x＝－2代入原式大大減少了計算量．若用計算機計算，則可提高運算效率．(2）注意：當多項式中n次項不存在時，可將第n次項看作0·xn。跟蹤訓練2用秦九韶算法計算多項式f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64當x＝2時的值．解根據秦九韶算法，把多項式改寫成如下形式：f（x)＝（（（（(x－12)x＋60)x－160）x＋240)x－192)x＋64。由內向外依次計算一次多項式當x＝2時的值；v0＝1；v1＝1×2－12＝－10；v2＝－10×2＋60＝40；v3＝40×2－160＝－80;v4＝－80×2＋240＝80；v5＝80×2－192＝－32；v6＝－32×2＋64＝0。所以當x＝2時，多項式的值為0。題型三進位制之間的互化例3（1）把二進制數1110011(2）化為十進制數．（2)將8進制數314706（8)化為十進制數．解(1)1110011（2）＝1×26＋1×25＋1×24＋0×23＋0×22＋1×21＋1＝115.（2)314706（8)＝3×85＋1×84＋4×83＋7×82＋0×81＋6×80＝104902.所以，化為十進制數是104902。反思與感悟（1）將k進制轉化為十進制的方法是：先將這個k進制數寫成各個數位上的數字與k的冪的乘積之和的形式，再按照十進制的運算規則計算出結果．（2)十進制轉化為k進制，采用除k取余法，也就是除基數，倒取余．跟蹤訓練3將53（8)轉化為二進制數．解先將八進制數53（8)轉化為十進制數:53(8)＝5×81＋3×80＝43；再將十進制數43轉化為二進制數:所以53(8）＝101011（2)．轉化與化歸思想例4下列各數中，最小的數是（）A．85（9) B．210（6）C．1000(4） D．111111（2)分析先將它們轉化為十進制數,再進行比較．解析85（9)＝8×9＋5＝77，210(6）＝2×62＋1×6＋0＝78，1000(4）＝1×43＝64，111111（2)＝1×25＋1×24＋1×23＋1×22＋1×2＋1＝63.故最小的是63。答案D解后反思合理的轉化是解題的關鍵．對于進位制之間的轉化問題，一般要先把k進制數轉化為十進制數，再轉化為其他進制數．數制轉化方法掌握不牢致錯例5把十字進制數49化為二進制數．分析對進位制間的換算，要弄清解題的辦法，將十進制數轉化為k進制數用“除k取余法”．解所以49＝110001(2)．解后反思本例常出現的錯誤是把上式中各步所得的余數從上到下排列,這是基本方法掌握不牢造成的，應加以注意．1．1337與382的最大公約數是（）A．3B．382C．191D．201答案C解析利用輾轉相除法，1337＝382×3＋191，382＝191×2,故兩數的最大公約數為191.2．把189化為三進制數，則末位數字是（）A．0B．1C．2D．3答案A解析采用“除k取余法"，得即189＝21000(3）3．用秦九韶算法求n次多項式f（x)＝anxn＋an－1xn－1＋…＋a1x＋a0當x＝x0時的值，求f(x0）需要乘方、乘法、加法的次數分別為（)A.eq\f（nn＋1，2），n，n B．n，2n，nC．0,2n，n D．0，n，n答案D解析因為f（x)＝(…（(anx＋an－1)x＋an－2）x＋…＋a1)x＋a0，所以乘方、乘法、加法的次數分別為0，n,n。4．秦九韶是我國南宋時期的數學家,普州(現四川省安岳縣)人，他在所著的《數書九章》中提出的多項式求值的秦九韶算法,至今仍是比較先進的算法．如圖所示的程序框圖給出了利用秦九韶算法求某多項式值的一個實例,若輸入n，x的值分別為3,2，則輸出v的值為(）A．9B．18C．20D．35答案B解析初始值n＝3,x＝2，程序運行過程如下v＝1i＝2v＝1×2＋2＝4i＝1v＝4×2＋1＝9i＝0v＝9×2＋0＝18i＝－1跳出循環，輸出v＝18，選B。5．用更相減損術求36與134的最大公約數，第一步應為________．答案先除以2，得到18與67解析∵36與134都是偶數，∴第一步應為：先除以2,得到18與67。1.求兩個正整數的最大公約數的問題，可以用輾轉相除法，也可以用更相減損術．用輾轉相除法，即根據a＝nb＋r這個式子,反復相除,直到r＝0為止；用更相減損術，即根據r＝|a－b｜這個式子,反復相減，直到r＝0為止．2．秦九韶算法的關鍵在于把n次多項式轉化為一次多項式,注意體會遞推的實現過程,實施運算時要由內向外，