2017-2018版高中數(shù)學(xué) 第二章 算法初步疑難規(guī)律方法學(xué)案 北師大版必修3

1、第二章 算法初步1算法概念的詮釋同學(xué)們也許對算法這個概念很陌生，但其實大家在日常生活中已經(jīng)接觸過很多算法了，廣義地說，算法就是做某一件事情的步驟或程序菜譜是做菜肴的“算法”，洗衣機的使用說明書是操作洗衣機的“算法”每個算法都閃耀著人類的智慧，閱讀和學(xué)習(xí)這些東西會給我們帶來一種難以用語言表達的滿足感和快感在以后的學(xué)習(xí)和工作中我們會不斷從實際應(yīng)用中了解和領(lǐng)會算法是如何解決各個領(lǐng)域的實際問題，推動人類文明的發(fā)展的一、算法的特征1確定性算法中的每條運算規(guī)則必須是明確定義的、可行的，每一個步驟只能有一個確定的后繼步驟，運行終止應(yīng)得到問題的解答或指出問題沒有解答2有限性一個算法必須保證在執(zhí)行有限步后結(jié)束，

2、至少不能出現(xiàn)無限循環(huán)或死循環(huán)在此基礎(chǔ)上越簡潔越快越好越簡潔，占用內(nèi)存越少，對設(shè)備的要求越基本；越快，這個意義就不用說了吧比如一個計算對方導(dǎo)彈軌跡的算法，如果等你算出來，那邊導(dǎo)彈已經(jīng)落地了，那還有什么意義？二、算法的思想專業(yè)的事交給專業(yè)的人去做普通人只要按專業(yè)人士給出的步驟一步一步地去完成，這就是算法的思想，即程序思想，你也可以理解為傻瓜化思想另外，算法強調(diào)的是通性通法，即給出一個算法，實際上是給出了一種解決一類問題的方法比如你給出一個計算圓的面積的算法，它應(yīng)該能計算各種半徑的圓的面積，而不是只適用于半徑為某一具體數(shù)的圓三、特別提示1算法中的每一步應(yīng)該是確定的并且能夠有效地執(zhí)行且得到確定的結(jié)果，

3、而不應(yīng)當(dāng)模棱兩可，如求的近似值卻沒有要求近似的精確度，則該問題不能求解2現(xiàn)代算法主要是面向計算機的，如果算法中沒有輸出，程序也能運行 ，但是運行結(jié)果無法輸出如果想要得到結(jié)果，那就要有輸出3只要有公式可以利用，利用公式解決問題是最理想、最簡便的方法，比如在寫解方程x23x40的算法時，用求根公式來做，步驟則較為簡潔4求解某一個問題的算法一般不是唯一的，我們通常選擇較為簡單的算法四、典例分析例1已知一個等邊三角形的周長為a，求這個三角形的面積，設(shè)計一個算法解決這個問題分析對于已知等邊三角形的邊長求面積的題目同學(xué)們已經(jīng)很熟悉，回顧其中的解題過程不難得到這個問題的算法步驟但學(xué)會清晰條理地表達自己的想法

4、，也是一個基本的要求解算法步驟如下：第一步，輸入a的值第二步，計算l的值第三步，計算Sl2的值第四步，輸出S的值例2下面給出了一個問題的算法：第一步，輸入x.第二步，若x4，則執(zhí)行第三步，否則執(zhí)行第四步第三步，輸出2x1.第四步，輸出x22x3.這個算法解決的問題是什么？分析依據(jù)題目給出的算法步驟依次執(zhí)行，是讀懂算法的一個重要而基本的辦法解這個算法先是輸入一個變量x，當(dāng)x4時輸出2x1，當(dāng)x4時輸出x22x3，不難發(fā)現(xiàn)這個算法解決的問題是求分段函數(shù)f(x)的函數(shù)值.2典型算法舉例1解方程(方程組)、不等式的算法例1用自然語言描述求一元二次方程ax2bxc0的根的算法思維切入對于求方程的根，解方

5、程組這樣的數(shù)值型的問題，我們都有具體的計算方法，只要我們把平時的計算方法嚴(yán)格地按步驟描述出來即可因此我們很容易得到下面的算法解用自然語言來描述算法，第一步，計算b24ac；第二步，如果0，則原方程無實數(shù)解，輸出“無實數(shù)解”；否則(0)x1，x2，輸出x1，x2的值點評第二步中包含了一個判斷b24ac是否小于零的條件，并根據(jù)判斷結(jié)果進行不同的處理算法是否“健壯”，也是衡量算法優(yōu)劣的重要指標(biāo)如果思維不嚴(yán)謹(jǐn)，比如這個算法忘記考慮b24ac小于零的情形，實際運算一旦遇到，則會導(dǎo)致不是出錯就是死機，那這個算法就是不“健壯”的例2寫出解x24x30的算法思維切入只要把平時的固定解法有條理地寫出來，即為解不

6、等式的算法解第一步，求出對應(yīng)方程的根x11，x23；第二步，確定根的大小x1x2；第三步，寫出解集x|1xr，則直線與圓相離，dr則直線與圓相切，dr則相離，如果dr則相切，如果dr則相交點評算法要求分解成簡單計算，不要直接計算d.一個比較大的程序，會分成若干模塊，一個模塊出了問題只需要修改這一個模塊，而不需要全盤翻工4累加、累乘問題的算法例5用自然語言描述求解mul123456問題的算法思維切入根據(jù)算法的特點，我們學(xué)過的加、減、乘、除運算法則都是算法，只要按照具體的規(guī)則有步驟地描述過程，便有了該題的算法解第一步，計算12，得2；第二步，將第一步中的運算結(jié)果2與3相乘得6；第三步，將第二步中的

7、運算結(jié)果6與4相乘得24；第四步，將第三步中的運算結(jié)果24與5相乘得120；第五步，將第四步中的運算結(jié)果120與6相乘得720.點評如果讓人一步一步地做，太枯燥了但這恰好是計算機的優(yōu)勢所以算法好不好，還分讓誰來執(zhí)行，對人來講是奇笨無比的辦法，對計算機卻可能是一個好辦法思維拓展該算法包含一個重復(fù)操作的過程是循環(huán)結(jié)構(gòu)，我們可將算法改造得更為簡練、科學(xué)解第一步，設(shè)i1，P1；第二步，如果i6執(zhí)行第三步，否則執(zhí)行第五步；第三步，計算Pi并將結(jié)果代替P；第四步，將i1代替i，轉(zhuǎn)去執(zhí)行第二步；第五步，輸出P.點評i稱為計數(shù)變量，每一次循環(huán)它的值增加1，由1變到6，P是一個累乘變量，每一次循環(huán)得到一個新的結(jié)

8、果，然后新的結(jié)果代替原值.3算法框圖畫法全知曉一、畫算法框圖的基本步驟第一步，設(shè)計算法，因為算法的設(shè)計是畫算法框圖的基礎(chǔ)，所以畫算法框圖前，首先寫出相應(yīng)的算法步驟，并分析算法需要用哪種基本邏輯結(jié)構(gòu)(順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu))完成第二步，把算法步驟轉(zhuǎn)化為對應(yīng)的算法框圖，在這種轉(zhuǎn)化過程中往往需要考慮很多細節(jié)，是一個將算法“細化”的過程第三步，將所有步驟的算法框圖用流程線連接起來，并加上終端框，得到整個表示算法的算法框圖二、畫算法框圖的規(guī)則1使用標(biāo)準(zhǔn)的框圖符號2框圖一般按從上到下、從左到右的方向來畫3除判斷框外，大多數(shù)框圖符號只有一個進入點和一個退出點，判斷框是唯一具有超過一個退出點的符號4在圖

9、形符號內(nèi)描述的語言要簡練清楚三、典例分析1順序結(jié)構(gòu)順序結(jié)構(gòu)是最簡單的算法結(jié)構(gòu)，是任何一個算法都離不開的結(jié)構(gòu)若一個算法由若干個依次執(zhí)行的步驟組成，則在畫算法框圖時，可直接由順序結(jié)構(gòu)完成因為在其他的結(jié)構(gòu)中都會涉及到順序結(jié)構(gòu)，所以關(guān)于順序結(jié)構(gòu)的畫法，在此不再單獨敘述2選擇結(jié)構(gòu)設(shè)計算法框圖時，若是分段函數(shù)或執(zhí)行時需要先判斷才能執(zhí)行的問題，則需要用到判斷框，引入選擇結(jié)構(gòu)例1如圖，在邊長為4的正方形ABCD的邊上有一點P，沿著BCDA的方向由點B向點A運動，設(shè)點P運動的路程為x(0x12)，APB的面積為y，畫出y關(guān)于x的關(guān)系式的算法框圖分析隨著點P的位置不同，APB的面積與路程x有不同的對應(yīng)關(guān)系，所以需

10、要先判斷點P的位置，這就需要用到選擇結(jié)構(gòu)，先根據(jù)題意寫出算法，再根據(jù)算法畫出算法框圖即第一步，按照題意，y與x的關(guān)系滿足分段函數(shù)：y第二步，用合適的含選擇結(jié)構(gòu)的算法框圖表示該分段函數(shù)解算法框圖如圖所示點評該題中的分段函數(shù)是分三段的函數(shù)，需引入兩個判斷框至于判斷框的內(nèi)容是沒有順序的，但與下一圖形的內(nèi)容或操作必須相互對應(yīng)同時，在畫算法框圖時，要特別注意圖形符號的規(guī)范性3循環(huán)結(jié)構(gòu)如果問題中進行了重復(fù)的運算，且有相同的規(guī)律，就可根據(jù)需要引入相關(guān)變量，利用這些規(guī)律組成一個循環(huán)體，用循環(huán)結(jié)構(gòu)來解決例2 某機械廠為增加產(chǎn)值進行了技術(shù)革新?lián)y(tǒng)計2009年的生產(chǎn)總值為500萬元，技術(shù)革新后預(yù)計每年的生產(chǎn)總值比上

11、一年增加5%，問最早要到哪一年生產(chǎn)總值才能超過600萬元，試用算法框圖表示分析用變量n，a分別表示所經(jīng)過的年數(shù)和生產(chǎn)總值的數(shù)量，注意變量的初始值以及遞加的值是多少由題意知第n年后的生產(chǎn)總值為a500(10.05)n，此時為(2009n)年由于題中進行了重復(fù)的運算，故應(yīng)引入循環(huán)結(jié)構(gòu)解算法框圖如圖所示4例說選擇結(jié)構(gòu)選擇結(jié)構(gòu)是三種基本邏輯結(jié)構(gòu)之一，可以解決一些含有條件判斷的算法問題，如分段函數(shù)求值問題、比較大小問題、分類討論問題和一些實際問題等下面就其應(yīng)用略舉兩例，供同學(xué)們學(xué)習(xí)時參考一、分段函數(shù)求值問題例1 已知函數(shù)y請設(shè)計算法框圖，要求輸入自變量x，輸出函數(shù)值y.分析輸入自變量x的值，首先判斷x與

12、0的大小關(guān)系，再代入相應(yīng)的表達式求函數(shù)值解算法框圖如圖點評求分段函數(shù)的函數(shù)值，需先判斷再執(zhí)行步驟，需要引入選擇結(jié)構(gòu)在使用選擇結(jié)構(gòu)時，要注意判斷條件的設(shè)定不重不漏，確保各種可能的判斷值有正確、唯一的流向二、實際應(yīng)用問題例2 郵政電子匯款單筆最高限額為1萬元，每筆匯款的資費標(biāo)準(zhǔn)為匯款金額的1%，最低收費為2元，最高收費為50元試編寫一算法框圖求出當(dāng)匯款x (02 011.解兩種方法：算法框圖如圖1和如圖2所示點評涉及求多項的和與積的算法框圖要用到循環(huán)結(jié)構(gòu)和選擇結(jié)構(gòu)畫圖時要注意循環(huán)變量的初始值、終值以及循環(huán)變量的增量在程序中的作用本題代表了一類相鄰兩個數(shù)的差為常數(shù)的求和問題的解法，在設(shè)計算法框圖時要

13、注意前后兩個加數(shù)相差2，此時計數(shù)變量不是ii1，而是ii2，要根據(jù)題意靈活地改變算法中的相應(yīng)部分二、疊加求值例2畫出求式子(共9個3)的值的一個算法框圖分析本題是一個疊加問題，由于前后重復(fù)了多次相同的運算，所以應(yīng)采用循環(huán)結(jié)構(gòu)來設(shè)計算法，但利用循環(huán)結(jié)構(gòu)實現(xiàn)算法需搞清初始值是什么本題中初始值可設(shè)定為a1，第一次循環(huán)得到a2，第二次循環(huán)得到a3，a9，共循環(huán)了8次解算法框圖如圖所示點評如果算法問題里涉及的運算有許多重復(fù)的步驟，且數(shù)之間有相同的規(guī)律，那么可引入變量，應(yīng)用循環(huán)結(jié)構(gòu)在循環(huán)結(jié)構(gòu)中，要注意根據(jù)條件，設(shè)計合理的計數(shù)變量、累計變量，特別要注意條件的表述要恰當(dāng)、精確，以免出現(xiàn)多一次循環(huán)或少一次循環(huán)的

14、情況.6三種邏輯結(jié)構(gòu)辨與析算法中有三種邏輯結(jié)構(gòu)，即順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，同學(xué)們初學(xué)這三種結(jié)構(gòu)，容易混淆本文將這三種結(jié)構(gòu)進行比較，希望同學(xué)們能深刻體會這三種結(jié)構(gòu)的差異與共同點一、三種基本邏輯結(jié)構(gòu)順序結(jié)構(gòu)按照語句的先后順序，從上而下依次執(zhí)行這些語句，該結(jié)構(gòu)不具備控制流程的作用，是任何一個算法都離不開的基本結(jié)構(gòu)選擇結(jié)構(gòu)根據(jù)是否滿足某種條件來選擇程序的走向當(dāng)條件滿足時，運行一個分支，不滿足時，運行另一個分支循環(huán)結(jié)構(gòu)從某處開始，按照一定的條件，反復(fù)執(zhí)行某一處理步驟的情況用來處理一些進行反復(fù)操作的問題.二、三種基本邏輯結(jié)構(gòu)的共同特點1只有一個入口2只有一個出口，注意一個菱形判斷框有兩個出口，而一個

15、選擇結(jié)構(gòu)只有一個出口，不要將菱形框的出口和選擇結(jié)構(gòu)的出口混為一談3結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行到，即對每一個框來說都應(yīng)當(dāng)有一條從入口到出口的路徑通過它，如圖1中的A，沒有一條從入口到出口的路徑通過它，是不符合要求的算法框圖4結(jié)構(gòu)內(nèi)不存在死循環(huán)，即無終止的循環(huán)，如圖2就是一個死循環(huán)，在算法框圖中是不允許有死循環(huán)出現(xiàn)的三種基本結(jié)構(gòu)的這些共同特點，也是檢查一個算法框圖或算法是否正確、合理的方法和試金石.7條件語句小聚1“IfThen”語句“IfThen”語句的一般格式如下If條件Then語句End If對應(yīng)的框圖如圖1所示圖1計算機在執(zhí)行“IfThen”語句時，首先對If后的條件進行判斷，如果符合

16、條件，就執(zhí)行Then后面的語句，若不符合條件，則直接結(jié)束該條件語句，轉(zhuǎn)而執(zhí)行后面的語句2“IfThenElse”語句“IfThenElse”語句的一般格式如下If條件Then 語句1Else 語句2End If對應(yīng)的框圖如圖2所示圖2計算機在執(zhí)行“IfThenElse”語句時，首先對If后的條件進行判斷，如果符合條件，則執(zhí)行Then后面的“語句1”；若不符合條件，則執(zhí)行Else后面的“語句2”3條件語句“IfThenElse”可以嵌套，其格式為If條件1Then語句1ElseIf條件2Then 語句2Else語句3End IfEnd If注意：使用條件語句時應(yīng)注意以下幾點：(1)條件語句必須以

17、If語句開始，以End If語句結(jié)束，一個End If語句必須和一個If語句對應(yīng)(2)如果我們的程序只需對條件為真的情況作出處理，不需處理條件為假的情況，則條件語句省略Else，格式由IfThenElse語句變成IfThen語句.8透析循環(huán)語句兩種循環(huán)語句1For語句的一般形式是For循環(huán)變量初始值To終值循環(huán)體Next執(zhí)行步驟：當(dāng)計算機執(zhí)行For語句時，一般先執(zhí)行一次循環(huán)體，當(dāng)循環(huán)變量在初始值與終值之間時，執(zhí)行循環(huán)體；當(dāng)循環(huán)變量超過終值時，不再執(zhí)行循環(huán)體，跳出循環(huán)體執(zhí)行后面的語句2Do Loop語句的一般形式是Do循環(huán)體Loop While條件為真執(zhí)行步驟：計算機執(zhí)行Do Loop語句，先執(zhí)

18、行一次循環(huán)體，若符合條件，繼續(xù)執(zhí)行循環(huán)體；當(dāng)不符合條件時，跳出循環(huán)，執(zhí)行Loop While后的語句.9算法在生活實際中的應(yīng)用數(shù)學(xué)來源于生活，服務(wù)于社會，數(shù)學(xué)與生活息息相關(guān)，數(shù)學(xué)是有用的，在生活中做一件事情的方法和步驟有多種，生活中的許多問題都可以用算法描述，用算法框圖表達下面請欣賞三例算法問題一、第29屆奧林匹克運動會的申辦例1北京成功舉辦了2008年第29屆奧林匹克運動會你知道在申辦奧運會的最后階段，國際奧委會是如何通過投票決定主辦權(quán)歸屬的嗎？對選出的5個申辦城市進行表決的操作程序是首先進行第一輪投票，如果有一個城市得票數(shù)超過總票數(shù)的一半，那么該城市將獲得舉辦權(quán)；如果所有申辦城市的得票數(shù)都不超過總票數(shù)的一半，則將得票數(shù)最少的城市淘汰，然后重復(fù)上述過程，直到選出一個申辦城市為止請設(shè)計一個算法表述上面過程，并畫出算法框圖解算法步驟如下：第一步，投票；第二步，統(tǒng)計票數(shù)，如果有一個城市得票數(shù)超過總票數(shù)的一半，那么該城市就獲得主辦權(quán)；否則淘汰得票數(shù)最少的城市，轉(zhuǎn)第一步；第三步，宣布主辦城市算法框圖如圖所示：點評算法本身就是用計算機解決一些實際問題的方法，一定要充分理解算法的特點二、獎金的發(fā)放例2某科研所決定拿出一定量的資金對科研人員進行獎勵，按照科研成果價值的大小決定獎勵前10名第1名