學必求其心得，業必貴于專精學必求其心得，業必貴于專精PAGE29學必求其心得，業必貴于專精PAGE第二章算法初步1算法概念的詮釋同學們也許對算法這個概念很陌生,但其實大家在日常生活中已經接觸過很多算法了，廣義地說，算法就是做某一件事情的步驟或程序．菜譜是做菜肴的“算法”，洗衣機的使用說明書是操作洗衣機的“算法”．每個算法都閃耀著人類的智慧，閱讀和學習這些東西會給我們帶來一種難以用語言表達的滿足感和快感．在以后的學習和工作中我們會不斷從實際應用中了解和領會算法是如何解決各個領域的實際問題,推動人類文明的發展的．一、算法的特征1．確定性算法中的每條運算規則必須是明確定義的、可行的，每一個步驟只能有一個確定的后繼步驟,運行終止應得到問題的解答或指出問題沒有解答．2．有限性一個算法必須保證在執行有限步后結束,至少不能出現無限循環或死循環．在此基礎上越簡潔越快越好．越簡潔，占用內存越少，對設備的要求越基本;越快，這個意義就不用說了吧．比如一個計算對方導彈軌跡的算法，如果等你算出來，那邊導彈已經落地了，那還有什么意義？二、算法的思想專業的事交給專業的人去做．普通人只要按專業人士給出的步驟一步一步地去完成，這就是算法的思想，即程序思想，你也可以理解為傻瓜化思想．另外,算法強調的是通性通法，即給出一個算法，實際上是給出了一種解決一類問題的方法．比如你給出一個計算圓的面積的算法，它應該能計算各種半徑的圓的面積,而不是只適用于半徑為某一具體數的圓．三、特別提示1．算法中的每一步應該是確定的并且能夠有效地執行且得到確定的結果，而不應當模棱兩可,如求的近似值卻沒有要求近似的精確度,則該問題不能求解．2．現代算法主要是面向計算機的，如果算法中沒有輸出，程序也能運行,但是運行結果無法輸出．如果想要得到結果，那就要有輸出．3．只要有公式可以利用，利用公式解決問題是最理想、最簡便的方法,比如在寫解方程x2－3x－4＝0的算法時,用求根公式來做，步驟則較為簡潔．4．求解某一個問題的算法一般不是唯一的，我們通常選擇較為簡單的算法．四、典例分析例1已知一個等邊三角形的周長為a，求這個三角形的面積，設計一個算法解決這個問題．分析對于已知等邊三角形的邊長求面積的題目同學們已經很熟悉,回顧其中的解題過程不難得到這個問題的算法步驟．但學會清晰條理地表達自己的想法，也是一個基本的要求．解算法步驟如下：第一步,輸入a的值．第二步，計算l＝eq\f(a,3)的值．第三步，計算S＝eq\f（\r(3）,4）×l2的值．第四步,輸出S的值．例2下面給出了一個問題的算法：第一步,輸入x.第二步，若x≥4,則執行第三步，否則執行第四步．第三步，輸出2x－1.第四步，輸出x2－2x＋3.這個算法解決的問題是什么？分析依據題目給出的算法步驟依次執行，是讀懂算法的一個重要而基本的辦法．解這個算法先是輸入一個變量x，當x≥4時輸出2x－1，當x<4時輸出x2－2x＋3，不難發現這個算法解決的問題是求分段函數f(x)＝eq\b\lc\{\rc\(\a\vs4\al\co1(2x－1，x≥4，，x2－2x＋3，x〈4）)的函數值.2典型算法舉例1．解方程(方程組)、不等式的算法例1用自然語言描述求一元二次方程ax2＋bx＋c＝0的根的算法．思維切入對于求方程的根,解方程組這樣的數值型的問題，我們都有具體的計算方法,只要我們把平時的計算方法嚴格地按步驟描述出來即可．因此我們很容易得到下面的算法．解用自然語言來描述算法,第一步，計算Δ＝b2－4ac；第二步，如果Δ〈0,則原方程無實數解，輸出“無實數解”;否則(Δ≥0）x1＝eq\f（－b＋\r（b2－4ac）,2a），x2＝eq\f(－b－\r(b2－4ac），2a),輸出x1，x2的值．點評第二步中包含了一個判斷Δ＝b2－4ac是否小于零的條件，并根據判斷結果進行不同的處理．算法是否“健壯”，也是衡量算法優劣的重要指標．如果思維不嚴謹，比如這個算法忘記考慮Δ＝b2－4ac小于零的情形，實際運算一旦遇到，則會導致不是出錯就是死機,那這個算法就是不“健壯”的．例2寫出解x2－4x＋3〈0的算法．思維切入只要把平時的固定解法有條理地寫出來，即為解不等式的算法．解第一步，求出對應方程的根x1＝1,x2＝3；第二步，確定根的大小x1〈x2;第三步，寫出解集{x｜1<x<3｝．2．套用公式求值的算法例3已知攝氏溫度C與華氏溫度F的關系是F＝C×eq\f(9，5)＋32，寫出由攝氏溫度求華氏溫度的算法．思維切入這是一個函數求值問題，給C賦值再代入解析式求F。解第一步,輸入攝氏溫度C；第二步,代入F＝C×eq\f（9，5）＋32;第三步，輸出華氏溫度F。點評平時計算我們只注重第二步，其他步驟往往忽略了，算法卻講究“按部就班"，這類問題的算法一般分為三步:第一步輸入值,第二步套用公式，第三步輸出結果．3．判斷性質型問題的算法例4試描述判斷圓(x－a）2＋(y－b）2＝r2和直線Ax＋By＋C＝0位置關系的算法．思維切入直線與圓的關系有三種:相離、相切、相交,如果圓心到直線的距離d>r，則直線與圓相離，d＝r則直線與圓相切，d<r則直線與圓相交．因此我們可以先求出圓心到直線的距離d，然后再和r比較．解第一步，輸入圓心的坐標、直線方程的系數和半徑r；第二步，計算z1＝Ax0＋By0＋C；第三步，計算z2＝A2＋B2；第四步，計算d＝eq\f（｜z1|，\r（z2)）；第五步，如果d〉r則相離，如果d＝r則相切，如果d〈r則相交．點評算法要求分解成簡單計算,不要直接計算d＝eq\f(｜Ax0＋By0＋C|，\r(A2＋B2)）。一個比較大的程序，會分成若干模塊,一個模塊出了問題只需要修改這一個模塊，而不需要全盤翻工．4．累加、累乘問題的算法例5用自然語言描述求解mul＝1×2×3×4×5×6問題的算法．思維切入根據算法的特點,我們學過的加、減、乘、除運算法則都是算法，只要按照具體的規則有步驟地描述過程，便有了該題的算法．解第一步，計算1×2，得2;第二步,將第一步中的運算結果2與3相乘得6;第三步,將第二步中的運算結果6與4相乘得24;第四步，將第三步中的運算結果24與5相乘得120;第五步，將第四步中的運算結果120與6相乘得720。點評如果讓人一步一步地做，太枯燥了．但這恰好是計算機的優勢．所以算法好不好，還分讓誰來執行，對人來講是奇笨無比的辦法,對計算機卻可能是一個好辦法．思維拓展該算法包含一個重復操作的過程是循環結構,我們可將算法改造得更為簡練、科學．解第一步，設i＝1，P＝1；第二步,如果i≤6執行第三步,否則執行第五步；第三步，計算P×i并將結果代替P；第四步，將i＋1代替i，轉去執行第二步；第五步,輸出P.點評i稱為計數變量，每一次循環它的值增加1，由1變到6，P是一個累乘變量，每一次循環得到一個新的結果，然后新的結果代替原值.3算法框圖畫法全知曉一、畫算法框圖的基本步驟第一步，設計算法，因為算法的設計是畫算法框圖的基礎，所以畫算法框圖前,首先寫出相應的算法步驟，并分析算法需要用哪種基本邏輯結構（順序結構、選擇結構、循環結構）完成．第二步，把算法步驟轉化為對應的算法框圖，在這種轉化過程中往往需要考慮很多細節，是一個將算法“細化"的過程．第三步，將所有步驟的算法框圖用流程線連接起來，并加上終端框，得到整個表示算法的算法框圖．二、畫算法框圖的規則1．使用標準的框圖符號．2．框圖一般按從上到下、從左到右的方向來畫．3．除判斷框外，大多數框圖符號只有一個進入點和一個退出點，判斷框是唯一具有超過一個退出點的符號．4．在圖形符號內描述的語言要簡練清楚．三、典例分析1．順序結構順序結構是最簡單的算法結構，是任何一個算法都離不開的結構．若一個算法由若干個依次執行的步驟組成，則在畫算法框圖時，可直接由順序結構完成．因為在其他的結構中都會涉及到順序結構，所以關于順序結構的畫法，在此不再單獨敘述．2．選擇結構設計算法框圖時，若是分段函數或執行時需要先判斷才能執行的問題，則需要用到判斷框，引入選擇結構．例1如圖,在邊長為4的正方形ABCD的邊上有一點P，沿著BCDA的方向由點B向點A運動，設點P運動的路程為x(0〈x〈12)，△APB的面積為y,畫出y關于x的關系式的算法框圖．分析隨著點P的位置不同，△APB的面積與路程x有不同的對應關系，所以需要先判斷點P的位置，這就需要用到選擇結構，先根據題意寫出算法，再根據算法畫出算法框圖．即第一步，按照題意，y與x的關系滿足分段函數：y＝eq\b\lc\{\rc\（\a\vs4\al\co1（2x,0〈x≤4,,8，4<x≤8，，212－x，8<x〈12.))第二步，用合適的含選擇結構的算法框圖表示該分段函數．解算法框圖如圖所示．點評該題中的分段函數是分三段的函數，需引入兩個判斷框．至于判斷框的內容是沒有順序的，但與下一圖形的內容或操作必須相互對應．同時，在畫算法框圖時，要特別注意圖形符號的規范性．3．循環結構如果問題中進行了重復的運算，且有相同的規律，就可根據需要引入相關變量，利用這些規律組成一個循環體,用循環結構來解決．例2某機械廠為增加產值進行了技術革新．據統計2009年的生產總值為500萬元,技術革新后預計每年的生產總值比上一年增加5％，問最早要到哪一年生產總值才能超過600萬元,試用算法框圖表示．分析用變量n,a分別表示所經過的年數和生產總值的數量，注意變量的初始值以及遞加的值是多少．由題意知第n年后的生產總值為a＝500（1＋0。05）n，此時為（2009＋n)年．由于題中進行了重復的運算，故應引入循環結構．解算法框圖如圖所示．4例說選擇結構選擇結構是三種基本邏輯結構之一，可以解決一些含有條件判斷的算法問題，如分段函數求值問題、比較大小問題、分類討論問題和一些實際問題等．下面就其應用略舉兩例,供同學們學習時參考．一、分段函數求值問題例1已知函數y＝eq\b\lc\｛\rc\(\a\vs4\al\co1（－x＋1，x>0，,0，x＝0，,x＋3,x〈0，)）請設計算法框圖,要求輸入自變量x,輸出函數值y。分析輸入自變量x的值，首先判斷x與0的大小關系，再代入相應的表達式求函數值．解算法框圖如圖．點評求分段函數的函數值，需先判斷再執行步驟，需要引入選擇結構．在使用選擇結構時，要注意判斷條件的設定不重不漏，確保各種可能的判斷值有正確、唯一的流向．二、實際應用問題例2郵政電子匯款單筆最高限額為1萬元，每筆匯款的資費標準為匯款金額的1%，最低收費為2元，最高收費為50元．試編寫一算法框圖求出當匯款x(0〈x≤10000）元時，應交納資費多少元．分析由題意分析，當x≤200時，應交納資費2元，當x≥5000時,應交納資費50元，所以引入選擇結構，200和5000是兩個分段點．解算法框圖如圖．點評很多在一些需要判斷的實際問題，比如水電費,納稅額，結構工資，身體各項指標是否正常等，一般都會用到選擇結構，在設計算法框圖時，可先根據題意，設計算法，再根據算法畫出算法框圖．5循環結構的應用在循環結構中，經常會出現兩個變量:計數變量和累計變量．計數變量往往出現在循環結構中，起到循環計數的作用，這個變量一般出現在執行或終止循環體的條件中;而累計變量用于輸出結果，往往與計數變量同步執行，一般有累加與累乘兩種．下面舉例說明循環結構的應用．一、求和或求積問題例1設計兩個求1＋3＋5＋…＋2011的值的算法的算法框圖．分析本題是一個累加問題，由于加數較多,采用逐一相加的思路不可取，引入變量,應用循環結構解決：（1)設一個循環變量為i，初始值為1；再設一個累加變量為S，初始值為0.（2）循環體為S＝S＋i,i＝i＋2。（3）終止條件為i〉2011。解兩種方法:算法框圖如圖1和如圖2所示．點評涉及求多項的和與積的算法框圖要用到循環結構和選擇結構．畫圖時要注意循環變量的初始值、終值以及循環變量的增量在程序中的作用．本題代表了一類相鄰兩個數的差為常數的求和問題的解法，在設計算法框圖時要注意前后兩個加數相差2，此時計數變量不是i＝i＋1，而是i＝i＋2，要根據題意靈活地改變算法中的相應部分．二、疊加求值例2畫出求式子（共9個3)的值的一個算法框圖．分析本題是一個疊加問題，由于前后重復了多次相同的運算,所以應采用循環結構來設計算法,但利用循環結構實現算法需搞清初始值是什么．本題中初始值可設定為a1＝eq\f（1，3)，第一次循環得到a2＝eq\f(1,3＋a1)，第二次循環得到a3＝eq\f（1，3＋a2），……，a9＝eq\f(1,3＋a8)，共循環了8次．解算法框圖如圖所示．點評如果算法問題里涉及的運算有許多重復的步驟,且數之間有相同的規律,那么可引入變量,應用循環結構．在循環結構中，要注意根據條件，設計合理的計數變量、累計變量,特別要注意條件的表述要恰當、精確,以免出現多一次循環或少一次循環的情況。6三種邏輯結構辨與析算法中有三種邏輯結構，即順序結構、選擇結構、循環結構，同學們初學這三種結構，容易混淆．本文將這三種結構進行比較,希望同學們能深刻體會這三種結構的差異與共同點．一、三種基本邏輯結構順序結構按照語句的先后順序,從上而下依次執行這些語句,該結構不具備控制流程的作用，是任何一個算法都離不開的基本結構．選擇結構根據是否滿足某種條件來選擇程序的走向．當條件滿足時，運行一個分支，不滿足時，運行另一個分支．循環結構從某處開始，按照一定的條件，反復執行某一處理步驟的情況．用來處理一些進行反復操作的問題。二、三種基本邏輯結構的共同特點1．只有一個入口．2．只有一個出口,注意一個菱形判斷框有兩個出口，而一個選擇結構只有一個出口,不要將菱形框的出口和選擇結構的出口混為一談．3．結構內的每一部分都有機會被執行到,即對每一個框來說都應當有一條從入口到出口的路徑通過它，如圖1中的A，沒有一條從入口到出口的路徑通過它,是不符合要求的算法框圖．4．結構內不存在死循環，即無終止的循環，如圖2就是一個死循環，在算法框圖中是不允許有死循環出現的．三種基本結構的這些共同特點,也是檢查一個算法框圖或算法是否正確、合理的方法和試金石.7條件語句小聚1．“If—Then"語句“If-Then”語句的一般格式如下If條件Then語句EndIf對應的框圖如圖1所示圖1計算機在執行“If—Then”語句時，首先對If后的條件進行判斷,如果符合條件，就執行Then后面的語句，若不符合條件,則直接結束該條件語句,轉而執行后面的語句．2．“If—Then—Else”語句“If—Then—Else”語句的一般格式如下If條件Then語句1Else語句2EndIf對應的框圖如圖2所示圖2計算機在執行“If—Then—Else”語句時，首先對If后的條件進行判斷，如果符合條件，則執行Then后面的“語句1"；若不符合條件，則執行Else后面的“語句2”．3．條件語句“If—Then—Else"可以嵌套，其格式為If條件1Then語句1ElseIf條件2Then語句2Else語句3EndIfEndIf注意：使用條件語句時應注意以下幾點：(1)條件語句必須以If語句開始，以EndIf語句結束,一個EndIf語句必須和一個If語句對應．（2）如果我們的程序只需對條件為真的情況作出處理,不需處理條件為假的情況，則條件語句省略Else，格式由If—Then—Else語句變成If-Then語句。8透析循環語句兩種循環語句1．For語句的一般形式是For循環變量＝初始值To終值循環體Next執行步驟:當計算機執行For語句時，一般先執行一次循環體,當循環變量在初始值與終值之間時，執行循環體；當循環變量超過終值時，不再執行循環體，跳出循環體執行后面的語句．2．DoLoop語句的一般形式是Do循環體LoopWhile條件為真執行步驟：計算機執行DoLoop語句，先執行一次循環體,若符合條件,繼續執行循環體；當不符合條件時，跳出循環,執行LoopWhile后的語句。9算法在生活實際中的應用數學來源于生活,服務于社會，數學與生活息息相關,數學是有用的,在生活中做一件事情的方法和步驟有多種，生活中的許多問題都可以用算法描述,用算法框圖表達．下面請欣賞三例算法問題．一、第29屆奧林匹克運動會的申辦例1北京成功舉辦了2008年第29屆奧林匹克運動會．你知道在申辦奧運會的最后階段，國際奧委會是如何通過投票決定主辦權歸屬的嗎？對選出的5個申辦城市進行表決的操作程序是首先進行第一輪投票，如果有一個城市得票數超過總票數的一半，那么該城市將獲得舉辦權;如果所有申辦城市的得票數都不超過總票數的一半，則將得票數最少的城市淘汰,然后重復上述過程，直到選出一個申辦城市為止．請設計一個算法表述上面過程，并畫出算法框圖．解算法步驟如下：第一步，投票；第二步,統計票數，如果有一個城市得票數超過總票數的一半,那么該城市就獲得主辦權；否則淘汰得票數最少的城市，轉第一步；第三步,宣布主辦城市．算法框圖如圖所示：點評算法本身就是用計算機解決一些實際問題的方法，一定要充分理解算法的特點．二、獎金的發放例2某科研所決定拿出一定量的資金對科研人員進行獎勵,按照科研成果價值的大小決定獎勵前10名．第1名得全部獎金的一半多1萬元，第2名得剩余的獎金的一半多1萬元，第3名再得剩余獎金的一