高中數學算法初步典型例題分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、3！+！的值.寫出偽代碼.解：思路一：利用單循環(huán)，循環(huán)體中必須包括一個求各項階乘的語句以及一個求和語句. Read n For I from 1 to n End For Print S 思路二：運用內外雙重循環(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四 、典型習題導練1 下列的循環(huán)語句循環(huán)的次數為（ ）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運行下面的程序后輸出的結果是 ，若將程序中的A語句與B語句的位置互換，再次執(zhí)行程序后輸出的結果為 .While A語句 B語句End WhilePrint x,yEnd3.偽代碼描述的求T的代數式是 ,求的代數式是 . Read n For I from 1 to n End forPrint T,S4.運行下面程序后輸出的結果為 For I from 10 to 1 step -2 Print I End forEnd 5. 將100名學生的一門功課的成績依次輸入并計算輸出平均成績. § 133 算法案例一、知識導學1算法設計思想：（1）“韓信點兵孫子問題”對正整

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

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

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

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

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

23、9 故3 是192與81的最大公約數.點評：輾轉相除法以除法為主，更相減損術以減法為主，計算次數上輾轉相除法計算次數相對較少.輾轉相除法是當大數被小數整除時停止除法運算，此時的小數就是兩者的最大公約數，更相減損術是當大數減去小數的差等于小數時減法停止，較小的數就是最大公約數. 例5為了設計用區(qū)間二分法求方程在0，1上的一個近似解（誤差不超過0.001）的算法,流程圖的各個框圖如下所示,請重新排列各框圖,并用帶箭頭的流線和判斷符號“Y”、“N”組成正確的算法流程圖,并寫出其偽代碼.(其中分別表示區(qū)間的左右端點) 圖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 點評：二分法的基