PAGE1-2.1算法的基本思想[航向標·學(xué)習(xí)目標]1．理解算法的概念與特點．2．學(xué)會用自然語言描述算法．3．通過解決詳細問題的實例感受理解算法的特點，體會算法的基本思想，學(xué)會借助已有數(shù)學(xué)問題的解決方法和步驟設(shè)計算法．[讀教材·自主學(xué)習(xí)]1．算法的概念：算法是指依據(jù)肯定規(guī)則解決某一類問題的明確的過程和有限的eq\o(□,\s\up1(01))步驟，算法具有如下特點：(1)eq\o(□,\s\up1(02))明確性：即每一個算法都有明確的目的．(2)eq\o(□,\s\up1(03))有效性：即我們所設(shè)計的算法必需是有效的，并在有限步的操作后解決問題．(3)eq\o(□,\s\up1(04))邏輯性：即我們設(shè)計的算法要符合邏輯規(guī)律，能從頭到尾運行下去．(4)eq\o(□,\s\up1(05))普遍性：我們所設(shè)計的算法必需能夠解決一類問題，而不是某一個問題．(5)eq\o(□,\s\up1(06))不唯一性：算法不是唯一的，可有另外不同的設(shè)計方法．2．排序：為了便于查詢和檢索，我們經(jīng)常依據(jù)某種要求把被查詢的對象用數(shù)字(或者符號)表示出來，并把數(shù)字按大小eq\o(□,\s\up1(07))排列，是信息處理中一項基本的工作，通常稱為排序．3．有序列：按eq\o(□,\s\up1(08))依次排列的數(shù)據(jù)列為有序列．[看名師·疑難剖析]1．對算法含義的理解(1)算法是機械的算法的設(shè)計要“四平八穩(wěn)”不能省略任何一個小小的步驟，有時可能要進行大量重復(fù)計算，但只要按步驟一步一步地執(zhí)行，總能得到結(jié)果．算法的這種機械化的特點，在設(shè)計出算法后，便于把詳細過程交給計算機去完成．(2)算法是普遍存在的事實上處理任何問題都須要算法，如國際象棋的棋譜、走法、輸贏的評判標準，郵寄物品的相關(guān)手續(xù)，求一個二元一次方程組的解等等．(3)求解某個詳細問題的算法一般是不唯一的算法事實上是解決問題的步驟和方法，求解問題的動身點不同，就會得到不同的算法．如求二元一次方程組的解有代入消元法和加減消元法，但不同的算法可能會有“優(yōu)劣”之分．2．算法與數(shù)學(xué)問題解法的區(qū)分與聯(lián)系(1)聯(lián)系算法與解法是一般與特別的關(guān)系，也是抽象與詳細的關(guān)系．如，由詳細的二元一次方程組的求解過程(解法)動身，歸納出了二元一次方程組求解的步驟；同時指出，這樣的求解步驟也適合有限制條件的二元一次方程組，這些步驟就構(gòu)成了二元一次方程組的算法．算法的獲得要借助一般意義上詳細問題的求解方法，而任何一個詳細問題都可利用這類問題的一般算法解決．(2)區(qū)分算法是解決某一類問題所須要的程序和步驟的統(tǒng)稱，也可理解為數(shù)學(xué)中的“通法通解”；而解法是解決某一個詳細問題的過程和步驟，是詳細的解題過程．考點一算法的概念例1下列關(guān)于算法的描述正確的是()A．算法與求解一個問題的方法相同B．算法只能解決一個問題，不能重復(fù)運用C．算法過程要一步一步執(zhí)行，每步執(zhí)行的操作必需準確D．有的算法執(zhí)行完后，可能無結(jié)果[分析]由題目可獲得以下主要信息：①給出的四個選項均與算法含義和特點有關(guān)；②對各選項要做正誤推斷．解答本題要先弄清晰算法的含義和特點，然后逐一判定選項命題的真假即可．[解析]算法與求解一個問題的方法既有區(qū)分又有聯(lián)系，故A不對；算法能重復(fù)運用，故B不對；每個算法執(zhí)行后必需有結(jié)果，故D不對；由算法的有序性和確定性可知C正確．[答案]C類題通法算法事實上是解決問題的一種程序性方法，它通常指向某一個或一類問題，而解決的過程是程序性和構(gòu)造性的.算法也可以看成解決問題的特別的、有效的方法.eq\a\vs4\al()eq\a\vs4\al([變式訓(xùn)練1])下列關(guān)于算法的說法，正確的有()①求解某一類問題的算法是唯一的；②算法必需在有限步操作之后停止；③算法的每一步操作必需是明確的，不能有歧義和模糊；④算法執(zhí)行后肯定產(chǎn)生確定的結(jié)果．A．1個B．2個C．3個D．4個答案C解析本題是在嫻熟駕馭算法概念的基礎(chǔ)上的一個躍升，即對算法概念進行進一步的挖掘，理解其內(nèi)涵．從而借助概念分析、解決問題．由于算法具有有窮性、確定性和可執(zhí)行性，因而②③④正確．解決問題的算法不肯定是唯一的，從而①錯，故選C.考點二數(shù)值計算問題的算法設(shè)計例2寫出一個算法，求二元一次方程組eq\b\lc\{\rc\(\a\vs4\al\co1(a1x＋b1y＝c1，①,a2x＋b2y＝c2'②))的解．[分析]聯(lián)系該方程組的實際解法過程，但要留意對待定系數(shù)的分類探討．因為是二元一次方程組，所以a1、a2不能同時為0，b1，b2也不能同時為0.[解]算法如下：1.若a1≠0，由①×eq\b\lc\(\rc\)(\a\vs4\al\co1(－\f(a2,a1)))＋②，得到eq\b\lc\(\rc\)(\a\vs4\al\co1(b2－\f(a2b1,a1)))y＝c2－eq\f(a2c1,a1).即方程組化為eq\b\lc\{\rc\(\a\vs4\al\co1(a1x＋b1y＝c1，①,a1b2－a2b1y＝a1c2－a2c1.③))2．若a1b2－a2b2≠0，解③得y＝eq\f(a1c2－a2c1,a1b2－a2b1).④3.將④代入①，整理得x＝eq\f(b2c1－b1c2,a1b2－a2b1).4.輸出結(jié)果x，y.5.假如a1b2－a2b1＝0，從③可以看出，方程組無解或有無窮多組解．6.假如a1＝0，則b1≠0，所以y＝eq\f(c1,b1).⑤7.將⑤代入②，得x＝eq\f(b1c2－b2c1,a2b1).8.輸出結(jié)果x，y.類題通法對于設(shè)計數(shù)值計算問題的算法，可以借助數(shù)學(xué)的常規(guī)解法或數(shù)學(xué)公式，將過程分解成清晰的步驟，使之條理化，但應(yīng)留意多個數(shù)進行四則運算時應(yīng)分步計算，依次進行，直到算出結(jié)果.本題中，把解方程組的過程轉(zhuǎn)化為算法的步驟，應(yīng)用了數(shù)學(xué)的轉(zhuǎn)化思想.eq\a\vs4\al()eq\a\vs4\al([變式訓(xùn)練2])寫出解方程x2－2x－3＝0的一個算法．解解法一：第一步，移項，得x2－2x＝3.①其次步，①兩邊同加1并配方，得(x－1)2＝4.②第三步，②式兩邊開方，得x－1＝±2.③第四步，解③，得x＝3或x＝－1.解法二：第一步，計算方程的判別式并推斷其符號：Δ＝22＋4×3＝16>0.其次步，將a＝1，b＝－2，c＝－3代入求根公式x＝eq\f(－b±\r(b2－4ac),2a)，得x1＝3，x2＝－1.考點三推斷性問題的算法設(shè)計例3設(shè)計一個算法，推斷7是否為質(zhì)數(shù)．[分析]只能被1和自身整除的大于1的整數(shù)叫質(zhì)數(shù)．因而要推斷一個數(shù)是否為質(zhì)數(shù)，只需用比這個數(shù)小的任一個大于1的整數(shù)來除該數(shù)，然后利用余數(shù)是否為0來推斷．[解]算法步驟如下：(1)用2除7，得到余數(shù)1.因為余數(shù)不為0，所以2不能整除7.(2)用3除7，得到余數(shù)1.因為余數(shù)不為0，所以3不能整除7.(3)用4除7，得到余數(shù)3.因為余數(shù)不為0，所以4不能整除7.(4)用5除7，得到余數(shù)2.因為余數(shù)不為0，所以5不能整除7.(5)用6除7，得到余數(shù)1.因為余數(shù)不為0，所以6不能整除7.(6)推斷7是否為質(zhì)數(shù)：7是質(zhì)數(shù)．類題通法從本例可以看出，本類問題的算法具有很強的機械重復(fù)性，因而對于隨意給定一個大于2的整數(shù)n，我們推斷它是否為質(zhì)數(shù)的算法為：第一步：令i＝2.其次步，用i除n，得余數(shù)r.第三步，推斷“r＝0”是否成立，若是，則n不是質(zhì)數(shù)，結(jié)束算法；否則，將i的值增加1，仍用i表示.第四步，推斷“i>n－1”是否成立，若是，則n是質(zhì)數(shù)，結(jié)束算法；否則，返回其次步.分步處理是本類問題的特色，也是算法思想的重要體現(xiàn).eq\a\vs4\al()eq\a\vs4\al([變式訓(xùn)練3])設(shè)計算法，將1260分解成素因數(shù)的乘積．解算法步驟如下：(1)推斷1260是否為素數(shù)：否．(2)確定1260的最小素因數(shù)：2.1260＝2×630.(3)推斷630是否為素數(shù)：否．(4)確定630的最小素因數(shù)：2.630＝2×315.(5)推斷315足否為素數(shù)：否．(6)確定315的最小素因數(shù)：3.315＝3×105.(7)推斷105是否為素數(shù)：否．(8)確定105的最小素因數(shù)：3.105＝3×35.(9)推斷35是否為素數(shù)：否．(10)確定35的最小素因數(shù)：5.35＝5×7.(11)推斷7是否為素數(shù)：7是素數(shù)，所以分解結(jié)束．分解結(jié)果是：1260＝2×2×3×3×5×7.考點四關(guān)于整除性問題的算法設(shè)計例4設(shè)計一個算法，求1764與840的最大公約數(shù)．[分析]首先，將兩個數(shù)分別進行素因數(shù)分解，1764＝22×32×72,840＝23×3×5×7.其次，確定兩個數(shù)的公共素因數(shù)2,3,7.接著，確定公共素因數(shù)的指數(shù)：對于公共素因數(shù)2,22是1764的因數(shù)，23是840的因數(shù)，因此22是這兩個數(shù)的公因數(shù)，同樣可以確定公因數(shù)3和7的指數(shù)均為1.這樣就確定了1764與840的最大公因數(shù)為22×3×7＝84.[解]算法步驟如下：(1)將1764進行素因數(shù)分解，1764＝22×32×72.(2)將840進行素因數(shù)分解，840＝23×3×5×7.(3)確定它們的公共素因數(shù)為2,3,7.(4)確定公共素因數(shù)的指數(shù)．公共素因數(shù)2,3,7的指數(shù)分別為2,1,1.(5)最大公因數(shù)為22×31×71＝84.類題通法1正確理解算法的概念，一個程序的算法要本著便利簡捷的原則，還要講求科學(xué)性，算法的步驟是依據(jù)肯定依次進行的，不具有可逆性.,2在設(shè)計算法的過程當中要堅固把握住它的五個特性：有限性、確定性、可行性、輸入、輸出.eq\a\vs4\al()eq\a\vs4\al([變式訓(xùn)練4])求8251與6105的最大公因數(shù)．解算法步驟如下：(1)先將8251進行素因數(shù)分解：8251＝37×223；(2)然后將6105進行素因數(shù)分解：6105＝3×5×11×37；(3)確定它們的公共素因數(shù)：37；(4)確定公共素因數(shù)的指數(shù)：1；(5)最大公因數(shù)為37.考點五排序問題的算法設(shè)計例5對于有序列{32,36,50,56,81}，現(xiàn)在要將數(shù)據(jù)51插入到有序列中．請設(shè)計算法確定數(shù)據(jù)51在有序列中的位置，并用自然語言描述算法．[分析]我們可以將51與有序列中的數(shù)據(jù)從右到左依次進行比較，來確定51在有序列中的位置，也可以將51與有序列中的數(shù)據(jù)從左向右依次進行比較，來確定51在有序列中的位置．[解]將51與有序列中的數(shù)據(jù)從右向左逐個進行比較，從而確定51在有序列中的位置．其算法如下：1.比較51與81,51<81.2.比較51與56,51<56.3.比較51與50,51>50.4.將51插入到56和50之間，得到一個新的有序列{32,36,50,51,56,81}．類題通法本例的排序算法是有序列干脆插入排序，解決本類問題也可以用折半插入排序法進行.eq\a\vs4\al()eq\a\vs4\al([變式訓(xùn)練5])將52插入有序列{13,27,38,39,43,47,48,51,57,66,74,82}中，構(gòu)成一個新的有序列．解首先選擇有序列中具有中間位置序號的數(shù)據(jù)47，將52與47進行比較，明顯52>47，故52不能插入到47的左邊的任何位置．所以，應(yīng)當排在47的右邊，再將余下數(shù)據(jù)的中間位置的數(shù)據(jù)57與52比較，明顯52<57，因此應(yīng)插到57的左邊，又51<52，則52插入到51的右邊，57的左邊，即可得到52的位置.考點六實際問題的算法設(shè)計例6漢諾塔問題：如圖三根柱子，甲柱上從大到小放置了三個圓環(huán)A、B、C，現(xiàn)在要將這三個圓環(huán)移至乙柱，也要從大到小放置．要求一次移動一個，移動過程中，大圓環(huán)不能放于小圓環(huán)上，應(yīng)如何移動？[分析]這是一個古典的數(shù)學(xué)問題．要把甲柱的n個環(huán)移到乙柱，必需先把上面的n－1個環(huán)移到丙柱，然后把第n個環(huán)移到乙柱，最終再把丙柱的第n－1個環(huán)移過來．解決n個環(huán)的問題，先要解決n－1個環(huán)的問題，而這個問題與前一個是類似的，可以用相同的方法解決．最終，得到只有一個環(huán)的狀況，很簡潔，干脆把環(huán)從甲柱移到乙柱即可．[解]假如移動一次算一步，則可按以下步驟進行：第一步，將C環(huán)移至乙柱．其次步，將B環(huán)移至丙柱．第三步，將C環(huán)移至丙柱．第四步，將A環(huán)移至乙柱．第五步，將C環(huán)移至甲柱．第六步，將B環(huán)移至乙柱．第七步，將C環(huán)移至乙柱．eq\a\vs4\al([變式訓(xùn)練6])一個人帶著三只狼和三只羊過河，只有一條船，該船可容納一個人和兩只動物；沒有人在的時候，假如狼的數(shù)量不少于羊的數(shù)量，狼就會吃羊，該人如何能將動物轉(zhuǎn)移過河？請設(shè)計算法．解第一步，人帶兩只狼過河，并自己返回；其次步，人帶一只狼過河，自己返回；第三步，人帶兩只羊過河，并帶兩只狼返回；第四步，人帶一只羊過河，自己返回；第五步，人帶兩只狼過河．規(guī)范解答分段函數(shù)的算法設(shè)計[例](12分)已知分段函數(shù)f(x)＝eq\b\lc\{\rc\(\a\vs4\al\co1(x2－1，－1≤x≤1，,lnx，x>1，))請設(shè)計一個算法，輸入隨意一個不小于－1的實數(shù)x0，輸出相應(yīng)的f(x0)的值．(一)精妙思路點撥(二)分層規(guī)范細解1．輸入x0；3分2.eq\a\vs4\al(若x0<－1)①，則輸出“輸入的數(shù)據(jù)有誤”，結(jié)束算法，否則執(zhí)行第3步；6分3．若－1≤x0≤1，則f(x0)＝xeq\o\al(2,0)－1，否則f(x0)＝lnx0；9分4.eq\a\vs4\al(輸出fx0的值)②，結(jié)束算法.12分(三)來自一線的報告通過閱卷后分析，對解答本題的失分警示和解題啟示總結(jié)如下：(注：此處的①②見分層規(guī)范細解過程)(四)類題練筆駕馭已知函數(shù)f(x)＝eq\b\lc\{\rc\(\a\vs4\al\co1(2x－1，x≤1，,\r(x)，1<x≤4，,x－2，x>4.))解1.輸入x0；2．若x0≤1，則計算f(x0)＝2x0－1，否則執(zhí)行第3步；3．若x0≤4，則計算f(x0)＝eq\r(x0)，否則執(zhí)行第4步；4．計算f(x0)＝x0－2；5．輸出f(x0)的值，結(jié)束算法．(五)解題設(shè)問解答本題時，需對誰進行分類探討？________.答案自變量x1.以下給出關(guān)于算法的幾種說法，其中正確的是()A．算法就是某一個問題的解題方法B．對于給定的一個問題，其算法不肯定是唯一的C．一個算法可以不產(chǎn)生確定的結(jié)果D．算法的步驟可以無限地執(zhí)行下去不停止答案B解析算法是做某一件事