A版2020屆高考數(shù)學(xué)一輪復(fù)習(xí)講義：算法與程序框圖_20210103224738

1、算法與程序框圖知識講解一、算法1.算法的概念：由基本運算及規(guī)定的運算順序所構(gòu)成的完整的解題步驟，或者看成按照一定規(guī)則解決某一類問題的明確的和有限的步驟，稱為算法（algorithm）通常可以編成計算機程序，讓計算機執(zhí)行并解決問題2.算法的特征：1）有窮性：算法必須在執(zhí)行有限步后結(jié)束，通常還理解為實際上能夠容忍的合理限度；2）確定性：算法的每一個步驟必須有確定的含義；3）可行性：組成算法的每個步驟和操作必須是相當(dāng)基本的，原則上都是能精確地執(zhí)行的；4）輸入：有零個或多個輸入：5）輸出：有一個或多個輸出3.算法的描述：用自然語言；用數(shù)學(xué)語言；用算法語言（程序設(shè)計語言）；用程序框圖（流程圖）4.算法的

2、三種基本邏輯結(jié)構(gòu)：1）順序結(jié)構(gòu)：最簡單的算法結(jié)構(gòu)，語句與語句之間，框與框之間是按從上到下的順序進行的如下圖，只有在執(zhí)行完A框指定的操作后，才能接著執(zhí)行B框指定的操作；2）條件（分支）結(jié)構(gòu)：在一個算法中，用來處理需要根據(jù)條件是否成立有不同的流向的結(jié)構(gòu)常見的條件結(jié)構(gòu)的程序框圖有下面兩種形式： 3）循環(huán)結(jié)構(gòu)：從某處開始，按照一定的條件反復(fù)執(zhí)行某些步驟的情況，就是循環(huán)結(jié)構(gòu)，其中反復(fù)執(zhí)行的步驟稱為循環(huán)體常見的循環(huán)結(jié)構(gòu)的框圖對應(yīng)為：注意事項：1.在畫程序框圖時，從開始框沿箭頭必須能到達結(jié)束框，特別是條件分支結(jié)構(gòu)應(yīng)沿每條支路都能到達結(jié)束框，流程線必須加箭頭表示順序2.對于循環(huán)結(jié)構(gòu)有如下需要注意的情況：1）循

3、環(huán)結(jié)構(gòu)非常適合計算機處理，因為計算機的運算速度非常快，執(zhí)行成千上萬次的重復(fù)計算，只不過是一瞬間的事，且能保證每次的結(jié)果都正確；2）循環(huán)結(jié)構(gòu)要有中止循環(huán)體的條件，不能無休止的運算下去，循環(huán)結(jié)構(gòu)中一定包含條件結(jié)構(gòu)，如就是中止循環(huán)的條件；3）循環(huán)結(jié)構(gòu)的關(guān)鍵是，要理解“累加變量”和“用代替”，是一個累加變量， 是計數(shù)變量，每循環(huán)一次，和都要發(fā)生變化，這兩步要重復(fù)計算若干次；4）一種循環(huán)結(jié)構(gòu)是先判斷是否成立，若是，執(zhí)行循環(huán)體；若否，則中止循環(huán)，像這樣，每次執(zhí)行循環(huán)體前對控制循環(huán)條件進行判斷，條件滿足時執(zhí)行循環(huán)體，不滿足則停止，稱為當(dāng)型循環(huán)除了當(dāng)型循環(huán)外，常用的循環(huán)結(jié)構(gòu)還有直到型循環(huán)二、程序框圖程序框圖的

4、概念：用一些通用的圖形符號構(gòu)成的一張圖來表示算法，稱為程序框圖（簡稱框圖）常用圖形符號：圖形符號名稱符號表示的意義起、止框框圖的開始或結(jié)束輸入、輸出框數(shù)據(jù)的輸入或者結(jié)果的輸出處理框賦值、執(zhí)行計算語句、結(jié)果的傳送判斷框根據(jù)給定條件判斷流程線流程進行的方向連結(jié)點連結(jié)另一頁或另一部分的框圖注意事項：1） 畫程序框圖的規(guī)則：使用標(biāo)準(zhǔn)的框圖的符號；框圖一般按從上到下、從左到右的方向畫；除判斷框外，大多數(shù)框圖符號只有一個進入點和一個退出點判斷框是具有超過一個退出點的惟一符號；一種判斷框是“是”與“不是”兩分支的判斷，而且有且僅有兩個結(jié)果；另一種是多分支判斷，有幾種不同的結(jié)果；在圖形符號內(nèi)描述的語言要非常簡

5、練清楚2）畫程序框圖要注意的幾點：起、止框是任何流程不可少的，表示程序的開始和結(jié)束；輸入、輸出框可以用在算法中任何需要輸入、輸出的位置；算法中間要處理數(shù)據(jù)或計算，可分別寫在不同的處理框內(nèi)；當(dāng)算法要求你對兩個不同的結(jié)果進行判斷時，要寫在判斷框內(nèi)；一個算法步驟到另一個算法步驟用流程線連結(jié)；如果一個框圖需要分開來畫，要在斷開處畫上連結(jié)點，并標(biāo)出連結(jié)的號碼如：用海倫公式求任意三角形的面積的程序框圖，其中斷開處畫上連結(jié)點，并標(biāo)出連結(jié)的號碼三、算法語句1.程序語言的基本語句結(jié)構(gòu)：輸入語句、輸出語句、賦值語句、條件語句、循環(huán)語句2.賦值語句：表明賦給某一個變量一個具體的確定值的語句一般格式：變量名表達式；其

6、中“”叫做賦值號作用：先計算出賦值號右邊表達式的值，然后將它賦給左邊的變量，使該變量的值等于表達式的值3.輸入語句：在每次程序運行時，用于輸入相應(yīng)的初始數(shù)據(jù)的語句，我們主要介紹鍵盤輸入語句Scilab中的輸入語句常用的是：“input”；一般格式：變量名=input（“提示內(nèi)容”）例：a=input（“x1”）；b=input（“x2”）；aver=（a+b）/2表示輸入，的值，求它們的算術(shù)平均數(shù)，在Scilab界面內(nèi)運行結(jié)果如下：->a=input（"x1"）；b=input（"x2"）；aver=（a+b）/2x1->此時通過鍵盤輸入x1

7、的值，如，再按“Enter”鍵，界面出現(xiàn)：x2->輸入x2的值，如，再按“Enter”鍵，這時界面出現(xiàn)：aver = 54.輸出語句：以某種形式把求解結(jié)果輸出的語句Scilab中有：print，write，format，printf，disp等輸出語句，主要介紹print語句：一般格式：print（%io（2），表達式）；其中參數(shù)%io（2）表示在屏幕上輸出5.條件語句：處理條件分支結(jié)構(gòu)的算法語句Scilab程序語言中常用的條件語句為if語句一般格式：if 表達式語句序列1；else語句序列2；end最簡格式：if 表達式語句序列1；end6.循環(huán)語句：處理算法中的循環(huán)結(jié)構(gòu)的語句；Sci

8、lab有兩種循環(huán)語句：for循環(huán)和while循環(huán)for循環(huán)的格式：for 循環(huán)變量=初值：步長：終值循環(huán)體；endwhile語句的一般格式：while 表達式（即條件）循環(huán)體；end注意事項：1.計算機能夠直接或間接理解的程序語言有很多種，比如C語言，Basic語言，以及一些應(yīng)用數(shù)學(xué)軟件：Matlab，Mathsmatics，Scilab對應(yīng)的計算機語言這里的基本語句結(jié)構(gòu)在這些語言中都是存在的，但是對應(yīng)不同的程序語言，都會有自己的輸入指令與方法這里是以一種語言為例，讓大家理解程序語句的含義，為以后深入學(xué)習(xí)程序設(shè)計打下基礎(chǔ)2.賦值語句：1）賦值號左邊只能是變量名，而不是表達式；如是錯誤的；2）賦

9、值號左右不能對換，是將賦值號右邊的表達式的值賦給左邊的變量；如表示用的值替代變量原先的值，與不同；3）不能利用賦值語句進行代數(shù)式（或符號）的演算；如是不能實現(xiàn)的；并且在一個賦值語句中，只能給一個變量賦值；3）賦值號與數(shù)學(xué)中的等號的意義不同，執(zhí)行賦值語句后，右面表達式的值會賦給左邊，如果左邊變量原來有一個值，會自動被沖掉，如表示將的原值加再賦給，即的值加3.輸入語句：在某些算法中，變量的初值要根據(jù)情況經(jīng)常地改變，一般我們把程序與初始數(shù)據(jù)分開，每次算題時，即使初始數(shù)據(jù)改變，也不必改變程序部分，只要程序運行時，輸入相應(yīng)的數(shù)據(jù)即可，這個過程在程序語言中，用“輸入語句”來控制輸入語句中還有read輸入語

10、句等輸入語句要求輸入的一般都是具體的常數(shù)，也可輸入單個或多個字符，格式為：變量名=input（“提示內(nèi)容”，“string”），string表示輸入字符型變量4.循環(huán)語句：for語句：先把初值賦給循環(huán)變量，記下終值和步長，循環(huán)變量增值到超過終值時，執(zhí)行end后面的語句，不超過時，執(zhí)行for后面的語句；循環(huán)變量起計數(shù)作用，控制算法中循環(huán)次數(shù)，有初值與終值，步長是指循環(huán)變量每次增加的值，步長為時，可以省略；while語句：先判斷條件是否成立，并在符合條件時，執(zhí)行循環(huán)體；直到某次不符合時，跳到end后面的語句對應(yīng)的基本框圖是：5.在程序語言中，乘、除、乘方、求平方根、絕對值，分別用下列符號表示：*、

11、/、sqrt（）、abs（）程序語言中，一般“”為賦值號，“”表示等號、分別寫成：、在程序中，如果賦值語句后面用分號隔開，則被賦值的變量不會輸出，一般不隨便使用逗號或句號，而是直接使用回車或空格四、算法案例1.更相減損術(shù)：求兩個整數(shù)的最大公約數(shù)的算法更相減損術(shù)的步驟：以兩個數(shù)中較大的數(shù)減去較小的數(shù)，以差數(shù)和較小的數(shù)構(gòu)成一對新的數(shù)，對這一對數(shù)再用大數(shù)減小數(shù)，以同樣的操作一直做下去，直到產(chǎn)生一對相等的數(shù)，此數(shù)就是這兩個數(shù)的最大公約數(shù)等值算法：用“更相減損術(shù)”設(shè)計出來的算法求最大公約數(shù)的算法稱為“等值算法”，用等值算法可以求任意兩個正整數(shù)的最大公約數(shù)2.輾轉(zhuǎn)相除法：又稱歐幾里得算法，是由歐幾里得在公

12、元前300年左右首先提出來的求兩個數(shù)的最大公約數(shù)的算法。輾轉(zhuǎn)相除法的步驟：對于給定的兩個數(shù)，以其中較大的數(shù)除以較小的數(shù)得到一個余數(shù)，將較小的數(shù)與余數(shù)看成一對新的數(shù)，重復(fù)上面的步驟，直到余數(shù)為零為止，此時上一步中較小的數(shù)即為所求的最大公約數(shù)。以求和的最大公約數(shù)為例：,故即為所求。3.秦九韶算法：求多項式的值的算法具體如下：對任意一個元多項式，改寫成如下形式：，求多項式的值時，先計算最內(nèi)層括號內(nèi)的一次多項式的值，即，然后由內(nèi)向外逐層計算一次多項式的值，即，這樣，求一個次多項式的值，就轉(zhuǎn)化為求個一次多項式的值令，則遞推公式為，其中到目前為止，此算法仍然是世界上多項式求值的最先進的算法秦九韶算法與其它

13、算法在計算量上面的比較：，1）直接求和法：先計算各個單項式的值，再把它們相加，乘法次數(shù)為，加法次數(shù)；2）逐項求和法：先計算的各項冪的值，再分別相乘，計算冪值需要乘法次，將冪值與多項式系數(shù)相乘需要乘法次，故共需要乘法次，加法次此方法對直接求和法有所改進，但仍然比秦九韶算法計算量大很多3）秦九韶算法：計算量僅為乘法次，加法次經(jīng)典例題一選擇題（共16小題）1某程序框圖如圖所示，該程序運行后輸出K的值是（）A5B6C7D8【解答】解：當(dāng)S=0時，滿足執(zhí)行循環(huán)的條件，執(zhí)行循環(huán)體后S=1，K=2，當(dāng)S=1時，滿足執(zhí)行循環(huán)的條件，執(zhí)行循環(huán)體后S=5，K=3，當(dāng)S=5時，滿足執(zhí)行循環(huán)的條件，執(zhí)行循環(huán)體后S=1

14、3，K=4，當(dāng)S=13時，滿足執(zhí)行循環(huán)的條件，執(zhí)行循環(huán)體后S=29，K=5，當(dāng)S=29時，滿足執(zhí)行循環(huán)的條件，執(zhí)行循環(huán)體后S=61，K=6，當(dāng)S=61時，滿足執(zhí)行循環(huán)的條件，執(zhí)行循環(huán)體后S=125，K=7，當(dāng)S=125時，滿足執(zhí)行循環(huán)的條件，執(zhí)行循環(huán)體后S=253，K=8，當(dāng)S=253時，不滿足執(zhí)行循環(huán)的條件，故輸出的K值為8，故選：D2執(zhí)行如圖的程序框圖，若輸入a=5，b=2，則輸出的i=（）A3B4C5D6【解答】解：第一次執(zhí)行循環(huán)體后，a=152，b=4，滿足繼續(xù)循環(huán)的條件，i=1；第二次執(zhí)行循環(huán)體后，a=454，b=8，滿足繼續(xù)循環(huán)的條件，i=2；第三次執(zhí)行循環(huán)體后，a=1358，b=

15、16，滿足繼續(xù)循環(huán)的條件，i=3；第四次執(zhí)行循環(huán)體后，a=40516，b=32，不滿足繼續(xù)循環(huán)的條件，故輸出的i=3，故選：A3執(zhí)行如圖程序框圖，若輸入的n等于10，則輸出的結(jié)果是（）A2B3C-12D13【解答】解：若輸入的n等于10，則當(dāng)i=1時，滿足進行循環(huán)的條件，a=3，i=2；當(dāng)i=2時，滿足進行循環(huán)的條件，a=12，i=3；當(dāng)i=3時，滿足進行循環(huán)的條件，a=13，i=4；當(dāng)i=4時，滿足進行循環(huán)的條件，a=2，i=5；當(dāng)i=5時，滿足進行循環(huán)的條件，a=3，i=6；當(dāng)i=6時，滿足進行循環(huán)的條件，a=12，i=7；當(dāng)i=7時，滿足進行循環(huán)的條件，a=13，i=8；當(dāng)i=8時，滿足

16、進行循環(huán)的條件，a=2，i=9；當(dāng)i=9時，滿足進行循環(huán)的條件，a=3，i=10；當(dāng)i=10時，滿足進行循環(huán)的條件，a=12，i=11；當(dāng)i=11時，不滿足進行循環(huán)的條件，故輸出的a=12，故選：C4執(zhí)行如圖所示的程序框圖，則輸出的S的值為（）A91B91C21D21【解答】解：當(dāng)n=1時，f（x）=6exx，f（x）=6ex1，當(dāng)x（0，+）時，f（x）0恒成立，滿足f（x）在（0，+）為遞增函數(shù)，故S=1，n=2；當(dāng)n=2時，f（x）=6ex2x，f（x）=6ex2，當(dāng)x（0，+）時，f（x）0恒成立，滿足f（x）在（0，+）為遞增函數(shù)，故S=3，n=3；當(dāng)n=3時，f（x）=6ex3x，

17、f（x）=6ex3，當(dāng)x（0，+）時，f（x）0恒成立，滿足f（x）在（0，+）為遞增函數(shù)，故S=6，n=4；當(dāng)n=4時，f（x）=6ex4x，f（x）=6ex4，當(dāng)x（0，+）時，f（x）0恒成立，滿足f（x）在（0，+）為遞增函數(shù)，故S=10，n=5；當(dāng)n=5時，f（x）=6ex5x，f（x）=6ex5，當(dāng)x（0，+）時，f（x）0恒成立，滿足f（x）在（0，+）為遞增函數(shù)，故S=15，n=6；當(dāng)n=6時，f（x）=6ex6x，f（x）=6ex6，當(dāng)x（0，+）時，f（x）0恒成立，滿足f（x）在（0，+）為遞增函數(shù)，故S=21，n=7；當(dāng)n=7時，f（x）=6ex7x，f（x）=6ex7

18、，當(dāng)x（0，+）時，f（x）0不恒成立，不滿足f（x）在（0，+）為遞增函數(shù)，故輸出的S=21，故選：D5執(zhí)行如圖所示的程序框圖，若輸入t1，3，則輸出s的取值范圍是（）Ae2，1B1，eC0，1De2，e【解答】解：由已知可得：程序框圖的功能是計算并輸出s=&et-1，t-1，1)&log3t，t1，3的值域，當(dāng)t1，1）時，s=et1e2，1），當(dāng)t1，3時，s=log3t0，1，故輸出s的取值范圍是0，1，故選：C6執(zhí)行如圖所示的程序框圖，則輸出的n值為（）A3B4C5D6【解答】解：當(dāng)m=16時，不滿足cosm0，執(zhí)行循環(huán)體后，m=8，n=2；當(dāng)m=8時，不滿足cosm

19、0，執(zhí)行循環(huán)體后，m=4，n=3；當(dāng)m=4時，不滿足cosm0，執(zhí)行循環(huán)體后，m=2，n=4；當(dāng)m=2時，不滿足cosm0，執(zhí)行循環(huán)體后，m=1，n=5；當(dāng)m=1時，滿足cosm0，故輸出的n=5，故選：C7如圖所示的一個算法的程序框圖，則輸出d的最大值為（）A2B2C1+2D1+22【解答】解：模擬程序的運行，可得程序框圖的功能是求半圓y=1-x2上的點到直線xy2=0的距離的最大值，如圖：可得：d的最大值為OP+r=2+1故選：C8中國古代有計算多項式的秦九韶算法，如圖是實現(xiàn)該算法的程序框圖執(zhí)行該程序框圖，若輸入的x=2，n=2，依次輸入的a為2，3，7，則輸出的s等于（）A7B8C21D

20、49【解答】解：根據(jù)程序框圖的算法，執(zhí)行該程序框圖，若輸入的x=2，n=2，依次輸入的a為2，3，7，則輸出的s：根據(jù)判斷框：得s=21，故選：C9中國古代數(shù)學(xué)著作孫子算經(jīng)中有這樣一道算術(shù)題：“今有物不知其數(shù)，三三數(shù)之余二，五五數(shù)之余三，問物幾何？”人們把此類題目稱為“中國剩余定理”，若正整數(shù)N除以正整數(shù)m后的余數(shù)為n，則記為n=NMODm，例如2=11MOD3現(xiàn)將該問題以程序框圖的算法給出，執(zhí)行該程序框圖，則輸出的n等于（）A39B38C37D36【解答】解：由已知中的程序框圖可知：該程序的功能是利用循環(huán)結(jié)構(gòu)計算并輸出同時滿足條件：被3除余2，被5除余3，由已知中四個答案中的數(shù)據(jù)可得，故輸出

21、的n為38，故選：B10某校為了解高一年級300名學(xué)生對歷史、地理學(xué)科的選課情況，對學(xué)生進行編號，用1，2，300表示，并用（xi，yi）表示第i名學(xué)生的選課情況，其中根據(jù)如圖所示的程序框圖，下列說法錯誤的是xi=&0，第i名學(xué)生不選歷史&1，第i名學(xué)生選歷史yi=&0，第i名學(xué)生不選地理&1，第i名學(xué)生選地理（）Am為選擇歷史的學(xué)生人數(shù)Bn為選擇地理的學(xué)生人數(shù)CS為至少選擇歷史、地理一門學(xué)科的學(xué)生人數(shù)DS為選擇歷史的學(xué)生人數(shù)與選擇地理的學(xué)生人數(shù)之和【解答】解：由已知中的程序框圖可知：該程序的功能是利用循環(huán)結(jié)構(gòu)計算并輸出變量S，m，n的值，根據(jù)xi=1時，執(zhí)行m

22、=m+1，故m為選擇歷史的學(xué)生人數(shù)，故A正確；根據(jù)yi=1時，執(zhí)行n=n+1，故n為選擇地理的學(xué)生人數(shù)，故B正確；根據(jù)S=m+n，故S為選擇歷史的學(xué)生人數(shù)與選擇地理的學(xué)生人數(shù)之和，故D正確，C錯誤，故選：C11執(zhí)行如圖所示的程序框圖，則輸出d的最大值為（）A2-1B2C2D2+1【解答】解：模擬程序的運行，可得程序框圖的功能是求半圓y=1-x2上的點到直線xy2=0的距離的最大值，如圖：可得：d的最大值為OP+r=2+1故選：D12執(zhí)行如圖所示的程序框圖，如果輸入的a=1.8，則輸出的S=（）（其中a表示不超過a的最大整數(shù)，如0.3=0，2.3=3）A8B6C15D32【解答】解：如果輸入的a

23、=1.8，則S=0，i=1執(zhí)行第一次循環(huán)時：S=0+1=1，a=13.6=2.6，i=2，執(zhí)行第二次循環(huán)時：S=1+（2）=1，a=1+5.2=6.2，i=3，當(dāng)i=6時，輸出S=15故選：C13執(zhí)行如圖所示的程序框圖，如果輸入的是n=0，S=0，輸出的結(jié)果是7，則判斷框中“”應(yīng)填入（）AS56BS67CS78DS89【解答】解：輸入的是n=0，S=0，執(zhí)行循環(huán)體后，S=12，不滿足輸出的條件，故應(yīng)不滿足判斷框中的條件，故n=1，S=23，不滿足輸出的條件，故應(yīng)不滿足判斷框中的條件，故n=2，S=34，不滿足輸出的條件，故應(yīng)不滿足判斷框中的條件，故n=3，S=45，不滿足輸出的條件，故應(yīng)不滿足判斷框中的條件，故n=4，S=56，不滿足輸出的條件，故應(yīng)不滿足判斷框中的條件，故n=5，S=67，不滿足輸出的條件，故應(yīng)不滿足判斷框中的條