高中數(shù)學(xué)算法初步典型例題分析

1、高中數(shù)學(xué)輔導(dǎo)網(wǎng) 高中數(shù)學(xué)典型例題分析第十三章 算法初步 §13.1 流程圖一、 知識(shí)導(dǎo)學(xué)1. 流程圖：是由一些圖框和帶箭頭的流線組成的，其中圖框表示各種操作的類型，圖框中的文字和符號(hào)表示操作的內(nèi)容，帶箭頭的流線表示操作的先后次序.2算法的三種基本的邏輯結(jié)構(gòu)：順序結(jié)構(gòu)、條件結(jié)構(gòu)、循環(huán)結(jié)構(gòu).3根據(jù)對(duì)條件的不同處理，循環(huán)結(jié)構(gòu)又分為兩種：直到型(until型)循環(huán)：在執(zhí)行了一次循環(huán)體之后，對(duì)控制循環(huán)條件進(jìn)行判斷，當(dāng)條件不滿足時(shí)執(zhí)行循環(huán)體.滿足則停止.如圖13-1-3，先執(zhí)行A框，再判斷給定的條件是否為“假”，若為“假”，則再執(zhí)行A，如此反復(fù)，直到為“真”為止. 當(dāng)型（while型）循環(huán)：在每

2、次執(zhí)行循環(huán)體前對(duì)控制循環(huán)條件進(jìn)行判斷，當(dāng)條件滿足時(shí)執(zhí)行循環(huán)體，不滿足則停止.如圖13-1-4，當(dāng)給定的條件成立（“真”）時(shí)，反復(fù)執(zhí)行A框操作，直到條件為“假”時(shí)才停止循環(huán). 圖13-1-1 圖13-1-2二、疑難知識(shí)導(dǎo)析1.“算法“沒有一個(gè)精確化的定義，教科書只對(duì)它作了描述性說明，算法具有如下特點(diǎn)：（1）有限性：一個(gè)算法的步驟是有限的，必須在有限操作之后停止，不能是無限的.（2）確定性：算法的每一步驟和次序應(yīng)當(dāng)是確定的.（3）有效性：算法的每一步驟都必須是有效的.2. 畫流程圖時(shí)必須注意以下幾方面： （1）使用標(biāo)準(zhǔn)的圖形符號(hào). （2）流程圖一般按從上到下、從左到右的方向畫. （3）除判斷框外，

3、大多數(shù)流程圖符號(hào)只有一個(gè)進(jìn)入點(diǎn)和一個(gè)退出點(diǎn).判斷框具有超過一個(gè)退出點(diǎn)的唯一符號(hào). （4）判斷框分兩大類，一類判斷框“是”與“否”兩分支的判斷，而且有且僅有兩個(gè)結(jié)果；另一類是多分支判斷，有幾種不同的結(jié)果. （5）在圖形符號(hào)內(nèi)描述的語言要非常簡練清楚.3. 算法三種邏輯結(jié)構(gòu)的幾點(diǎn)說明：（1）順序結(jié)構(gòu)是最簡單的算法結(jié)構(gòu)，語句與語句之間，框與框之間是按從上到下的順序進(jìn)行的.在流程圖中的體現(xiàn)就是用流程線自上而下地連接起來，按順序執(zhí)行算法步驟.（2）一個(gè)條件結(jié)構(gòu)可以有多個(gè)判斷框.（3）循環(huán)結(jié)構(gòu)要在某個(gè)條件下終止循環(huán)，這就需要條件結(jié)構(gòu)來判斷.在循環(huán)結(jié)構(gòu)中都有一個(gè)計(jì)數(shù)變量和累加變量.計(jì)數(shù)變量用于記錄循環(huán)次數(shù)，

4、累加變量用語輸出結(jié)果，計(jì)數(shù)變量和累加變量一般是同步執(zhí)行的，累加一次，計(jì)數(shù)一次.三、經(jīng)典例題導(dǎo)講例1 已知三個(gè)單元存放了變量，的值，試給出一個(gè)算法，順次交換， 的值（即取的值，取的值，取的值），并畫出流程圖.錯(cuò)解：第一步 第二步 第三步 流程圖為 圖13-1-3 錯(cuò)因：未理解賦值的含義，由上面的算法使得，均取的值.舉一形象的例子：有藍(lán)和黑兩個(gè)墨水瓶，但現(xiàn)在卻把藍(lán)墨水裝在了黑墨水瓶中，黑墨水錯(cuò)裝在了藍(lán)墨水瓶中，要求將其互換，請你設(shè)計(jì)算法解決這一問題.對(duì)于這種非數(shù)值性問題的算法設(shè)計(jì)問題，應(yīng)當(dāng)首先建立過程模型，根據(jù)過程設(shè)計(jì)步驟完成算法. 我們不可將兩個(gè)墨水瓶中的墨水直接交換，因?yàn)閮蓚€(gè)墨水瓶都裝有墨水，

5、不可能進(jìn)行直接交換.正確的解法應(yīng)為：S1 取一只空的墨水瓶，設(shè)其為白色； S2 將黑墨水瓶中的藍(lán)墨水裝入白瓶中； S3 將藍(lán)墨水瓶中的黑墨水裝入黑瓶中； S4 將白瓶中的藍(lán)墨水裝入藍(lán)瓶中； S5 交換結(jié)束.正解：第一步 先將的值賦給變量，這時(shí)存放的單元可作它用 第二步 再將的值賦給，這時(shí)存放的單元可作它用 第三步 同樣將的值賦給，這時(shí)存放的單元可作它用 第四步 最后將的值賦給，三個(gè)變量，的值就完成了交換流程圖為 圖13-1-4點(diǎn)評(píng)：在計(jì)算機(jī)中，每個(gè)變量都分配了一個(gè)存儲(chǔ)單元，為了達(dá)到交換的目的，需要一個(gè)單元存放中間變量.例2已知三個(gè)數(shù)，.試給出尋找這三個(gè)數(shù)中最大的一個(gè)算法，畫出該算法的流程圖.

6、解：流程圖為圖13-1-5點(diǎn)評(píng)：條件結(jié)構(gòu)可含有多個(gè)判斷框，判斷框內(nèi)的內(nèi)容要簡明、準(zhǔn)確、清晰.此題也可將第一個(gè)判斷框中的兩個(gè)條件分別用兩個(gè)判斷框表示，兩兩比較也很清晰.若改為求100個(gè)數(shù)中的最大數(shù)或最小數(shù)的問題則選擇此法較繁瑣，可采用假設(shè)第一數(shù)最大（最?。⒌谝粋€(gè)數(shù)與后面的數(shù)依依比較，若后面的數(shù)較大（較?。瑒t進(jìn)行交換，最終第一個(gè)數(shù)即為最大（最?。┲?點(diǎn)評(píng)：求和時(shí)根據(jù)過程的類同性可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)，而不用順序結(jié)構(gòu).例3畫出求的值的算法流程圖.解：這是一個(gè)求和問題，可采用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)設(shè)計(jì)算法，但要注意奇數(shù)項(xiàng)為正號(hào)，偶數(shù)項(xiàng)為負(fù)號(hào). 思路一：采用-1的奇偶次方（利用循環(huán)變量）來解決正負(fù)符號(hào)問題； 圖1

7、3-1-6 圖13-1-7 思路二：采用選擇結(jié)構(gòu)分奇偶項(xiàng)求和； 圖13-1-8 思路三：可先將化簡成，轉(zhuǎn)化為一個(gè)等差數(shù)列求和問題，易利用循環(huán)結(jié)構(gòu)求出結(jié)果. 例4 設(shè)計(jì)一算法，求使成立的最小正整數(shù)的值.解： 流程圖為 圖13-1-9 點(diǎn)評(píng)：這道題仍然是考察求和的循環(huán)結(jié)構(gòu)的運(yùn)用問題，需要強(qiáng)調(diào)的是求和語句的表示方法.若將題改為求使成立的最大正整數(shù)的值時(shí)，則需注意的是輸出的值.例5任意給定一個(gè)大于1的整數(shù)n，試設(shè)計(jì)一個(gè)程序或步驟對(duì)n是否為質(zhì)數(shù)做出判斷. 解：算法為：S1 判斷n是否等于2，若n=2，則n是質(zhì)數(shù)；若n>2，則執(zhí)行S2S2 依次從2n-1檢驗(yàn)是不是的因數(shù)，即整除n的數(shù)，若有這樣的數(shù)，

8、則n不是質(zhì)數(shù)；若沒有這樣的數(shù)，則n是質(zhì)數(shù).點(diǎn)評(píng)：要驗(yàn)證是否為質(zhì)數(shù)首先必須對(duì)質(zhì)數(shù)的本質(zhì)含義作深入分析：（1）質(zhì)數(shù)是只能被1和自身整除的大于1的整數(shù). （2）要判斷一個(gè)大于1的整數(shù)n是否為質(zhì)數(shù)，只要根據(jù)定義，用比這個(gè)整數(shù)小的數(shù)去除n.如果它只能被1和本身整除，而不能被其它整數(shù)整除，則這個(gè)數(shù)便是質(zhì)數(shù). 圖13-1-10 例6設(shè)計(jì)一個(gè)求無理數(shù)的近似值的算法.分析：無理數(shù)的近似值可看作是方程的正的近似根，因此該算法的實(shí)質(zhì)是設(shè)計(jì)一個(gè)求方程的近似根的算法.其基本方法即運(yùn)用二分法求解方程的近似解.解：設(shè)所求近似根與精確解的差的絕對(duì)值不超過0.005,算法:S1 令.因?yàn)?所以設(shè)S2 令,判斷是否為0,若是,則

9、m為所求;若否,則繼續(xù)判斷大于0還是小于0.S3 若>0,則;否則,令.S4 判斷是否成立，若是，則之間的任意值均為滿足條件的近似根；若否，則返回第二步.點(diǎn)評(píng)：二分法求方程近似解的算法是一個(gè)重要的算法案例，將在第三節(jié)中詳細(xì)闡述.四、典型習(xí)題導(dǎo)練1已知兩個(gè)單元分別存放了變量和的值，則可以實(shí)現(xiàn)變量交換的算法是（ ）. AS1 BS1 CS1 DS1 S2 S2 S2 S2 S3 S3 1 下面流程圖中的錯(cuò)誤是（ ） 圖13-1-11 A沒有賦值 B循環(huán)結(jié)構(gòu)有錯(cuò) CS的計(jì)算不對(duì) D判斷條件不成立3.將“打電話”的過程描述成一個(gè)算法，這個(gè)算法可表示為 ，由此說明算法具有下列特性 . 4. 在表示

10、求直線（，為常數(shù)，且，不同時(shí)為0）的斜率的算法的流程圖中，判斷框中應(yīng)填入的內(nèi)容是 5. 3個(gè)正實(shí)數(shù)，設(shè)計(jì)一個(gè)算法，判斷分別以這3個(gè)數(shù)為三邊邊長的三角形是否存在，畫出這個(gè)算法的流程圖.6.一隊(duì)士兵來到一條有鱷魚的深河的左岸.只有一條小船和兩個(gè)小孩，這條船只能承載兩個(gè)小孩或一個(gè)士兵.試設(shè)計(jì)一個(gè)算法，將這隊(duì)士兵渡到對(duì)岸，并將這個(gè)算法用流程圖表示.§13.2基本算法語句一、知識(shí)導(dǎo)學(xué)1 賦值語句用符號(hào)“”表示，“”表示將 的值賦給，其中是一個(gè)變量，是一個(gè)與同類型的變量或表達(dá)式.2 條件語句主要有兩種形式：“行If 語句”和“塊If語句”. “行If 語句”的一般形式為：If A Then B

11、Else C .一個(gè)行If 語句必須在一行中寫完，其中方括號(hào)中的Else部分可以缺省.“塊If 語句”的一般格式為: If A Then B Else C End if Then 部分和 Else 部分是可選的，但塊If語句的出口“End if”不能省.3 循環(huán)語句主要有兩種類型：For語句和While語句.當(dāng)循環(huán)的次數(shù)已經(jīng)確定，可用“For”語句表示.“For”語句的一般形式為：For I from“初值” to step“步長” End for 上面“For”和“End for”之間縮進(jìn)的步驟稱為循環(huán)體.當(dāng)循環(huán)次數(shù)不能確定是，可用“While”語句來實(shí)現(xiàn)循環(huán).“While”語句的一般形式為

12、：While AEnd while其中A表示判斷執(zhí)行循環(huán)的條件.上面“While”和“End While”之間縮進(jìn)的步驟稱為循環(huán)體.二、疑難知識(shí)導(dǎo)析1. 有的條件語句可以不帶“Else”分支，即滿足條件時(shí)執(zhí)行B，否則不執(zhí)行任何操作.條件語句也可以進(jìn)行嵌套，在進(jìn)行條件語句的嵌套時(shí)，書寫要有層次.例如：If A Then BElse if C Then DElse EEnd if2.“For”語句是在執(zhí)行過程中先操作，后判斷.而“While”語句的特點(diǎn)是“前測試”，即先判斷，后執(zhí)行.若初始條件不成立，則一次也不執(zhí)行循環(huán)體中的內(nèi)容.任何一種需要重復(fù)處理的問題都可以用這種前測試循環(huán)來實(shí)現(xiàn).三、經(jīng)典例題

13、導(dǎo)講例1 下列程序的運(yùn)行結(jié)果是 .If >5 Then If >4 Then If >3 Then Print 錯(cuò)解：8+7=15錯(cuò)因：誤認(rèn)為在一個(gè)程序中只執(zhí)行一個(gè)條件語句，與在一個(gè)條件語句中只選擇其中一個(gè)分支相混淆.If A Then B Else C 若滿足條件A 則執(zhí)行B，否則是執(zhí)行C，B和C是這個(gè)條件語句的分支，而這個(gè)程序省略了Else部分.正解：這里是有三個(gè)條件語句，各個(gè)條件語句是獨(dú)立的，三個(gè)條件均成立，所以按順序依次執(zhí)行，結(jié)果為8+7+6+6=27.例2 下面的偽代碼的效果是 While <10End WhileEnd錯(cuò)解：執(zhí)行10次循環(huán)錯(cuò)因：將For語句和

14、While語句混淆. For語句中有步長使循環(huán)變量不斷變化，而While語句則無.正解：無限循環(huán)下去，這是因?yàn)檫@里始終為0，總能滿足條件“”，故是一個(gè)“死循環(huán)”.點(diǎn)評(píng)：“死循環(huán)”是設(shè)計(jì)循環(huán)結(jié)構(gòu)的大忌，此題可改變的初始值或每一次循環(huán)都增加一個(gè)值. 例3下面的程序運(yùn)行時(shí)輸出的結(jié)果是（ ）While End while Print SEnd 錯(cuò)解：第一次循環(huán)時(shí)，I被賦予2，S被賦予4；第二次循環(huán)時(shí)，I被賦予3，S被賦予4+=13；第三次循環(huán)時(shí)，I被賦予4，S被賦予13+=29；第四次循環(huán)時(shí)，I被賦予5，S被賦予.由于此時(shí)，故循環(huán)終止，輸出S為54.正解：由于在循環(huán)內(nèi)，每經(jīng)過一次循環(huán)后S都被賦值0，因

15、此，只要求滿足條件的最后一次循環(huán)S的值，即當(dāng)時(shí)，.例4用語句描述求使成立的最大正整數(shù)的算法過程.解： While End while Print 點(diǎn)評(píng)：此題易錯(cuò)的是輸出值，根據(jù)While循環(huán)語句的特征當(dāng)時(shí)跳出循環(huán)體，此時(shí)的值是時(shí)的最小的整數(shù)，則使的最大整數(shù)應(yīng)為的前一個(gè)奇數(shù)即.例5已知當(dāng)時(shí)，當(dāng)時(shí)，當(dāng)時(shí)，設(shè)計(jì)一算法求的值.解： Read xIf then Else if Then Else End if End 點(diǎn)評(píng)：嵌套If語句可用如上的緊湊形式書寫，要注意的是如不是采取緊湊形式，則需注意一個(gè)塊If語句對(duì)應(yīng)一個(gè)End If，不可省略或缺少. 例6設(shè)計(jì)一個(gè)算法，使得輸入一個(gè)正整數(shù)，輸出1！+2！+

16、3！+！的值.寫出偽代碼.解：思路一：利用單循環(huán)，循環(huán)體中必須包括一個(gè)求各項(xiàng)階乘的語句以及一個(gè)求和語句. Read n For I from 1 to n End For Print S 思路二：運(yùn)用內(nèi)外雙重循環(huán)，但尤其注意的是每一次外循環(huán)T的值都要從1開始. Read n For I from 1 to n For J from 1 to I End For End For Print S四 、典型習(xí)題導(dǎo)練1 下列的循環(huán)語句循環(huán)的次數(shù)為（ ）For I from 1 to 7 For J from 1 to 9 Pint I+J End for End forEndA.7次 B.9次 C.6

17、3次 D.16次2運(yùn)行下面的程序后輸出的結(jié)果是 ，若將程序中的A語句與B語句的位置互換，再次執(zhí)行程序后輸出的結(jié)果為 .While A語句 B語句End WhilePrint x,yEnd3.偽代碼描述的求T的代數(shù)式是 ,求的代數(shù)式是 . Read n For I from 1 to n End forPrint T,S4.運(yùn)行下面程序后輸出的結(jié)果為 For I from 10 to 1 step -2 Print I End forEnd 5. 將100名學(xué)生的一門功課的成績依次輸入并計(jì)算輸出平均成績. § 133 算法案例一、知識(shí)導(dǎo)學(xué)1算法設(shè)計(jì)思想：（1）“韓信點(diǎn)兵孫子問題”對(duì)正整

18、數(shù)m從2開始逐一檢驗(yàn)條件，若三個(gè)條件中有任何一個(gè)不滿足，則m遞增1，一直到m同時(shí)滿足三個(gè)條件為止(循環(huán)過程用Goto語句實(shí)現(xiàn))（2）用輾轉(zhuǎn)相除法找出的最大公約數(shù)的步驟是：計(jì)算出的余數(shù)，若，則為的最大公約數(shù)；若，則把前面的除數(shù)作為新的被除數(shù)，繼續(xù)運(yùn)算，直到余數(shù)為0，此時(shí)的除數(shù)即為正整數(shù)的最大公約數(shù).2.更相減損術(shù)的步驟：（1）任意給出兩個(gè)正數(shù)，判斷它們是否都是偶數(shù).若是，用2約簡；若不是，執(zhí)行第二步.（2）以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù).繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)（等數(shù)）就是所求的最大公約數(shù).（3）二分法求方程在區(qū)間內(nèi)的一個(gè)近似解的解題步驟

19、可表示為S1 取的中點(diǎn)，將區(qū)間 一分為二；S2 若，則就是方程的根；否則判別根在的左側(cè)還是右側(cè)：若，以代替；若，則，以代替；S3 若，計(jì)算終止，此時(shí)，否則轉(zhuǎn)S1.二、疑難知識(shí)導(dǎo)析 1表示不超過的整數(shù)部分，如，但當(dāng)是負(fù)數(shù)時(shí)極易出錯(cuò)，如就是錯(cuò)誤的，應(yīng)為-2.2表示除以所得的余數(shù)，也可用 表示.3輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的聯(lián)系與區(qū)別：（1）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯.（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差

20、相等而得到.4用二分法求方程近似解，必須先判斷方程在給定區(qū)間上是否有解,即連續(xù)且滿足.并在二分搜索過程中需對(duì)中點(diǎn)處函數(shù)值的符號(hào)進(jìn)行多次循環(huán)判定，故需要選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，即可用Goto 語句和條件語句實(shí)現(xiàn)算法.三、經(jīng)典例題導(dǎo)講例1 ， ， ， 7= .A16，-1，4，3 B.15，0，4，3 C.15,-1,3,4 D.15,-1,4,3錯(cuò)解：根據(jù)表示不超過的整數(shù)部分, 表示除以所得的余數(shù),選擇B.錯(cuò)因:對(duì)表示的含義理解不透徹,將不超過-0.05的整數(shù)錯(cuò)認(rèn)為是0,將負(fù)數(shù)的大小比較與正數(shù)的大小比較相混淆.正解：不超過-0.05的整數(shù)是-1,所以答案為D.例2 所謂同構(gòu)數(shù)是指此數(shù)的平方數(shù)的最后幾

21、位與該數(shù)相等.請?jiān)O(shè)計(jì)一算法判斷一個(gè)大于0且小于1000的整數(shù)是否為同構(gòu)數(shù).錯(cuò)解： 算法思想：求出輸入數(shù)的平方，考慮其個(gè)位或最后兩位或最后三位與輸入數(shù)是否相等，若相等，則為同構(gòu)數(shù). Read x If or or Then Print x End if End 錯(cuò)因：在表示個(gè)位或最后兩位或最后三位出現(xiàn)錯(cuò)誤，“/”僅表示除，y/10,y/100,y/1000都僅僅表示商.正解：可用來表示個(gè)位，最后兩位以及最后三位.Read x If or or Then Print x End if End 例3孫子算經(jīng)中的“物不知數(shù)”問題：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？”

22、可以用下面的算法解決：先在紙上寫上2，每次加3，加成5除余3的時(shí)候停下來，再在這個(gè)數(shù)上每次加15，到得出7除2的時(shí)候，就是答數(shù).試用流程圖和偽代碼表示這一算法.解：流程圖為： 偽代碼為：10 20 30 If Then Goto 2040 If Then Print Goto 8050 End if60 70 Goto 4080 End 點(diǎn)評(píng)：這是孫子思想的體現(xiàn)，主要是依次滿足三個(gè)整除條件.例4分別用輾轉(zhuǎn)相除法、更相減損法求192與81的最大公約數(shù).解：輾轉(zhuǎn)相除法： S1 S2 S3 S4 S5 故3是192 與81 的最大公約數(shù).更相減損法：S1 S2 S3 S4 S5 S6 S7 S8 S

23、9 故3 是192與81的最大公約數(shù).點(diǎn)評(píng)：輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少.輾轉(zhuǎn)相除法是當(dāng)大數(shù)被小數(shù)整除時(shí)停止除法運(yùn)算，此時(shí)的小數(shù)就是兩者的最大公約數(shù)，更相減損術(shù)是當(dāng)大數(shù)減去小數(shù)的差等于小數(shù)時(shí)減法停止，較小的數(shù)就是最大公約數(shù). 例5為了設(shè)計(jì)用區(qū)間二分法求方程在0，1上的一個(gè)近似解（誤差不超過0.001）的算法,流程圖的各個(gè)框圖如下所示,請重新排列各框圖,并用帶箭頭的流線和判斷符號(hào)“Y”、“N”組成正確的算法流程圖,并寫出其偽代碼.(其中分別表示區(qū)間的左右端點(diǎn)) 圖13-3-2流程圖為 圖13-3-3偽代碼為10 Read 20 30 40 50 If Then Goto 12060 If Then70 100 End if80 Else90 100 End if110 If Then Goto 20120 Print 130 End 點(diǎn)評(píng)：二分法的基