錯解剖析得真知

錯解剖析得真知（三十八）

第十三章演算法初步

§13.1 流程圖

一、知識導學

1. 流程圖：是由一些圖框和帶箭頭的流線組成的，其中圖框表示各種操作的型別，圖框中的文字和符號表示操作的內容，帶箭頭的流線表示操作的先後次序.

2．演算法的三種基本的邏輯結構：順序結構、條件結構、迴圈結構.

3．根據對條件的不同處理，迴圈結構又分為兩種：

直到型(until型)迴圈：在執行了一次迴圈體之後，對控制迴圈條件進行判斷，當條件不滿足時執行迴圈體.滿足則停止.

如圖13-1-3，先執行a框，再判斷給定的條件是否為「假」，若為「假」，則再執行a，如此反覆，直到為「真」為止.

當型（while型）迴圈：在每次執行迴圈體前對控制迴圈條件進行判斷，當條件滿足時執行迴圈體，不滿足則停止.如圖13-1-4，當給定的條件成立（「真」）時，反覆執行a框操作，直到條件為「假」時才停止迴圈.

圖13-1-1 圖13-1-2

二、疑難知識導析

1.「演算法「沒有乙個精確化的定義，教科書只對它作了描述性說明，演算法具有如下特點：

（1）有限性：乙個演算法的步驟是有限的，必須在有限操作之後停止，不能是無限的.

（2）確定性：演算法的每一步驟和次序應當是確定的.

（3）有效性：演算法的每一步驟都必須是有效的.

2. 畫流程圖時必須注意以下幾方面：

（1）使用標準的圖形符號.（2）流程圖一般按從上到下、從左到右的方向畫.

（3）除判斷框外，大多數流程圖符號只有乙個進入點和乙個退出點.判斷框具有超過乙個退出點的唯一符號.

（4）判斷框分兩大類，一類判斷框「是」與「否」兩分支的判斷，而且有且僅有兩個結果；另一類是多分支判斷，有幾種不同的結果.

（5）在圖形符號內描述的語言要非常簡練清楚.

3. 演算法三種邏輯結構的幾點說明：

（1）順序結構是最簡單的演算法結構，語句與語句之間，框與框之間是按從上到下的順序進行的.在流程圖中的體現就是用流程線自上而下地連線起來，按順序執行演算法步驟.（2）乙個條件結構可以有多個判斷框.

（3）迴圈結構要在某個條件下終止迴圈，這就需要條件結構來判斷.在迴圈結構中都有乙個計數變數和累加變數.計數變數用於記錄迴圈次數，累加變數用語輸出結果，計數變數和累加變數一般是同步執行的，累加一次，計數一次.

三、經典例題導講

[例1] 已知三個單元存放了變數，，的值，試給出乙個演算法，順次交換，，的值（即取的值，取的值，取的值），並畫出流程圖.

錯解：第一步第二步第三步

流程圖為

圖13-1-3

錯因：未理解賦值的含義，由上面的演算法使得，均取的值.

舉一形象的例子：有藍和黑兩個墨水瓶，但現在卻把藍墨水裝在了黑墨水瓶中，黑墨水錯裝在了藍墨水瓶中，要求將其互換，請你設計演算法解決這一問題.對於這種非數值性問題的演算法設計問題，應當首先建立過程模型，根據過程設計步驟完成演算法.

我們不可將兩個墨水瓶中的墨水直接交換，因為兩個墨水瓶都裝有墨水，不可能進行直接交換.正確的解法應為：

s1 取乙隻空的墨水瓶，設其為白色； s2 將黑墨水瓶中的藍墨水裝入白瓶中；s3 將藍墨水瓶中的黑墨水裝入黑瓶中；s4 將白瓶中的藍墨水裝入藍瓶中； s5 交換結束.

正解：第一步｛先將的值賦給變數，這時存放的單元可作它用}

第二步｛再將的值賦給，這時存放的單元可作它用}

第三步｛同樣將的值賦給，這時存放的單元可作它用}

第四步｛最後將的值賦給，三個變數，，的值就完成了交換}

流程圖為

圖13-1-4

點評：在計算機中，每個變數都分配了乙個儲存單元，為了達到交換的目的，需要乙個單元存放中間變數.

[例2]已知三個數，，.試給出尋找這三個數中最大的乙個演算法，畫出該演算法的流程圖.

解：流程圖為

圖13-1-5

點評：條件結構可含有多個判斷框，判斷框內的內容要簡明、準確、清晰.此題也可將第乙個判斷框中的兩個條件分別用兩個判斷框表示，兩兩比較也很清晰.

若改為求100個數中的最大數或最小數的問題則選擇此法較繁瑣，可採用假設第一數最大（最小）將第乙個數與後面的數依依比較，若後面的數較大（較小），則進行交換，最終第乙個數即為最大（最小）值.

點評：求和時根據過程的類同性可用迴圈結構來實現，而不用順序結構.

[例3]畫出求的值的演算法流程圖.

解：這是乙個求和問題，可採用迴圈結構實現設計演算法，但要注意奇數項為正號，偶數項為負號.

思路一：採用-1的奇偶次方（利用迴圈變數）來解決正負符號問題；

圖13-1-6 圖13-1-7

思路二：採用選擇結構分奇偶項求和；

圖13-1-8

思路三：可先將化簡成，轉化為乙個等差數列求和問題，易利用迴圈結構求出結果.

[例4] 設計一演算法，求使成立的最小正整數的值.

解：流程圖為

圖13-1-9

點評：這道題仍然是考察求和的迴圈結構的運用問題，需要強調的是求和語句的表示方法.若將題改為求使成立的最大正整數的值時，則需注意的是輸出的值.

[例5]任意給定乙個大於1的整數n，試設計乙個程式或步驟對n是否為質數做出判斷.

解：演算法為：

s1 判斷n是否等於2，若n=2，則n是質數；若n>2，則執行s2

s2 依次從2～n-1檢驗是不是的因數，即整除n的數，若有這樣的數，則n不是質數；若沒有這樣的數，則n是質數.

點評：要驗證是否為質數首先必須對質數的本質含義作深入分析：

（1）質數是只能被1和自身整除的大於1的整數.

（2）要判斷乙個大於1的整數n是否為質數，只要根據定義，用比這個整數小的數去除n.如果它只能被1和本身整除，而不能被其它整數整除，則這個數便是質數.

圖13-1-10

四、典型習題導練

1．已知兩個單元分別存放了變數和的值，則可以實現變數交換的演算法是（）.

a．s1 b．s1 c．s1 d．s1

s2 s2 s2 s2

s3 s3

2.下面流程圖中的錯誤是（）

圖13-1-11

a．沒有賦值　b．迴圈結構有錯

c．s的計算不對 d．判斷條件不成立

3.將「打**」的過程描述成乙個演算法，這個演算法可表示為，由此說明演算法具有下列特性 .

4. 在表示求直線（，為常數，且，不同時為0）的斜率的演算法

的流程圖中，判斷框中應填入的內容是

5. 3個正實數，設計乙個演算法，判斷分別以這3個數為三邊邊長的三角形是否存在，畫

出這個演算法的流程圖.

6.一隊士兵來到一條有鱷魚的深河的左岸.只有一條小船和兩個小孩，這條船隻能承載兩個小孩或乙個士兵.試設計乙個演算法，將這隊士兵渡到對岸，並將這個演算法用流程圖表示.

錯解剖析得真知

錯解剖析得真知

錯解剖析得真知

錯解剖析得真知

相關推薦