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

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