資源簡介

(共21張PPT)
《算法的概念及描述》
體驗探索：規劃乘車路線
小明同學計劃從A站出發去B站附近的圖書館學習。假設地鐵各線路每兩站間行車用時相等。請你幫他完成以下路線規劃：
1、列舉出A站出發到達B站的所有乘車路線。
2、如果小明同學希望盡快到達B站，試為他推薦一條最佳乘車路線，并說明理由。
算法的定義
尋找路線的方法，我們可以稱之為算法。
路線①：
一號線從A站坐到E站換乘9號線坐到B,共6站
路線②：
2號線從A站坐到J站換乘4號線坐到B站，共5站
……
算法的定義
從廣義上講，算法是為解決一類特定問題而采取的確定的、有限的步驟。
“做菜的步驟”
“洗衣服的步驟”
算法的定義
計算機科學領域
算法指用計算機解決問題的步驟，是為了解決問題而需要讓計算機有序執行的，無歧義的、有限步驟的集合。
用計算機能理解的語言描述算法，并輸入到計算機中，這個過程就是計算機程序設計。
思考
算法 = 程序？
程序=數據結構+算法
算法的特征
算法作為解決問題的策略，具有五個特征：
有輸入
有輸出
有窮性
可行性
確定性
一個算法一般要求有0個或多個輸入，以描述運算對象的初始情況。
一個算法可以有一個或多個輸出，以反映對輸入數據加工后的結果。
指算法必須能在執行有限個步驟之后終止，也就是算法步驟不能是無限的。
算法的每一步操作都是可以執行的，或者都可以分解成計算機可執行的操作
算法的每個步驟都具有確定的含義，沒有歧義
描述算法
小明在去往地鐵站時，在路口遇到了一個紅綠燈，小明發現該紅綠燈上配有一個倒計時器，倒計時15秒后紅燈變成了綠燈，如何將“倒計時15秒”的算法描述出來？
步驟1：將計數器t設為15；
步驟2：如果t大于或等1，執行步驟3，否則倒計時結束；
步驟3：輸出t，并保持顯示1s，然后清除顯示；
步驟4：將t的值減1，跳轉至步驟2
自然語言
描述算法的常用方法
同樣的畫面，分辨率越大，圖像越清晰
用自然語言描述算法
自然語言指人們日常所用的語言，用自然語言描述算法就是使用人們能讀懂的簡短語句對算法的步驟進行描述。
優點：通俗易懂，容易被大眾理解。
缺點：容易產生二義性，干擾后續的編程實現。
描述算法的常用方法
用流程圖描述算法
流程圖是一種常用的表示算法的圖形化工具。常用的符號的符號如下：
開始/結束框
輸入/輸出框
處理框
判斷框
流程線
連接點
描述算法的常用方法
流程圖符號 名稱 功能
開始/結束框 表示算法的開始或結束
輸入/輸出框 表示輸入或輸出數據
處理框 框中指出要處理的內容，此框有一個入口和一個出口
判斷框 用于表示條件判斷及產生分支的情況，判斷框有四個頂點，通常上面的頂點來表示入口。
流程線 用于控制流程方向。
連接點 用于連接因頁面寫不下而斷開的流程線
描述算法的常用方法
活動：
思考如何將“倒計時15s”的流程圖繪制出來。
開始
t≥1
輸出t
保持顯示1秒
清除顯示
結束
t =15
t t-1
True
False
步驟1：將計數器t設為15；
步驟2：如果t大于或等于1，執行步驟3，否則倒計時結束；
步驟3：輸出t，并保持顯示1s，然后清除顯示；
步驟4：將t的值減1，跳轉至步驟2
描述算法的常用方法
對比自然語言描述法和流程圖法。你認為用流程圖法來描述算法有什么優缺點？
優點：形象直觀、清晰簡潔 ，算法結構表達明確
缺點：當控制結構和嵌套層次復雜時，對應流程圖所占篇幅會比較大，影響可讀性，也不易于修改。
用流程圖描述算法
描述算法的常用方法
用偽代碼描述算法就是采用一種類似于程序設計語言的代碼來表示算法。例如，“倒計時15s”的算法用偽代碼可以描述為：
用偽代碼描述算法
t<-15
while t≥1
output t
sleep 1s
clear
t<-t-1
end while
三種基本控制結構
S1
…
Sn
條件
S1
條件
S1
S2
True
False
True
False
順序結構
選擇結構
循環結構
三種基本控制結構
A
…
B
順序結構
順序結構表示程序中的各步操作按出現的先后順序執行。順序結構式最簡單的一種結構。
它的執行順序是自上而下，依次執行。
順序結構
三種基本控制結構
選擇結構又稱分支結構。根據條件的成立與否，選擇執行不同的分支。
當條件成立時，執行處理A；當條件不成立時，執行處理B。
選擇結構
條件
A
B
True
False
選擇結構
三種基本控制結構
當條件成立時，反復執行處理A,一旦條件不成立就立即結束。
循環結構
條件
A
True
False
循環結構
三種基本控制結構
開始
t≥1
輸出t
保持顯示1秒
清除顯示
結束
t =15
t t-1
True
False
活動：
分析“倒計時15s”算法中包含了哪幾種基本結構？
順序結構
循環結構
任何復雜的算法都可以用這三種基本控制結構組合表示。
實踐活動
已知有10個一模一樣的零件，其中9個零件的質量相同，只有1個質量略輕，不符合規格要求。現有一臺天平，請設計算法找出該零件。比較不同算法在效率上的不同
解決同一問題可能會有不同的算法，不同算法求解的過程可能有不同。在解決問題時，可以根據需要選擇合適的算法。
知識小結
算法及其描述
算法的定義
算法的特征
算法的描述
有窮性
確定性
1個或多個輸出
可行性
0個或多個輸入
描述算法的常用方法
三種基本控制結構
下節課見

展開更多......

收起↑