資源簡介

(共25張PPT)
2.2 算法的概念及其描述
學習目標
描述算法的特征，理解算法在問題解決過程中的作用。
選用恰當的描述方法和控制結構表示簡單算法，增強用算法解決問題的意識。
情境描述
小明到北京旅游，他乘坐火車到達了北京站，然后準備乘坐地鐵去天安門參觀，地鐵線路圖如下圖所示，你能幫小明規劃好路線嗎？是否只有一條路線？請大家思考這個問題。
體驗探索
地鐵1號線
尋找路線的方法，可以稱之為算法。
解決同一個問題的算法可能有多種。
2.2.1認識算法
廣義上講，算法是解決一個特定問題而采取的確定的、有限的步驟。
在計算機領域，算法作為一個精心設計的運算序列，描述了計算機如何將輸入轉化為輸出的過程。
2.2.1認識算法
如何幫助牧羊人成功渡河？
算法是解決一個特定問題而采取的確定的、有限的步驟。
2.2.1認識算法
算法一般具有如下特征：
有輸入：一個算法一般要求有0個或多個輸入。
有輸出：一個算法可以有一個或多個輸出。
有窮性：算法必須能在執行有限個步驟之后終止，也就是算法的步驟不能是無限的。
可行性：算法中的每一步的操作都是可以執行的，或者都可以分解成計算機可執行的基本操作。
確定性：算法的每個步驟都具有確定的含義，沒有歧義。杜絕含糊不清、模棱兩可、二義性描述。
2.2.1認識算法
練一練：
1. 下面關于算法的描述，正確的是（ ）
A. 算法就是解決問題的方法和步驟。
B. 算法可以被無限制的執行。
C. 算法描述了計算機如何將輸入轉化為輸出的過程。
D. 算法可以有零個或多個輸入，但只能有一個輸出。
C
解析：
A:算法是解決一個特定問題而采取的確定的、有限的步驟。
B:有窮性：算法必須能在執行有限個步驟之后終止，也就是算法的步驟不能是無限的。
D: 算法一般要求有0個或多個輸入，1或多個輸出。
2.2.2 描述算法
小明在去往地鐵站時，在路口遇到了一個紅綠燈。小明發現該紅綠燈上配有一個倒計時器，倒計時15秒之后紅燈變成了綠燈，如何將“倒計時15秒”的算法描述出來？
描述“紅燈變綠燈”問題的算法
描述算法是將解決問題的步驟用一種可理解的方式表示出來。
①自然語言
②流程圖
③偽代碼
2.2.2 描述算法
描述“紅燈變綠燈”問題的算法
①自然語言
將計數器t（剩余秒數）設為15；
如果t大于等于1，執行步驟③，否則執行步驟⑤；
顯示t，并保持顯示1秒，然后清除顯示；
將t的值減1，跳轉至步驟②。
倒計時結束。
自然語言指人們日常所用的語言。
用自然語言描述算法就是用人們能夠讀懂的簡短語言對算法的步驟進行描述。
易于理解，但有時容易產生二義性，干擾后續編程實現。
2.2.21 認識算法
當你想要從北京去上海迪士尼旅游，你會如何規劃行程呢？
① 網上購買迪士尼門票；
② 根據日期，購買火車票或者飛機票；
③ 根據行程及日期安排，預訂住宿酒店；
④ 帶好各種票據，準備好行李，按時乘車；
⑤ 到達上海，乘坐出租車或公共交通車輛去往酒店入住，放行李；
⑥ 帶好門票，按時到迪士尼游玩。
①自然語言
2.2.2 描述算法
②流程圖
結束
t ← 15
t ≥ 1
輸出t
t ← t-1
True
False
保持顯示1秒
清除顯示
開始
自然語言
流程圖
2.2.2 描述算法
②流程圖
流程圖是用圖形表示算法的一種常用工具。
用流程圖描述的算法直觀易讀，問題解決的步驟清晰簡潔，算法結構表達明確。
開始/結束框
輸入/輸出框
處理框
判斷框
流程線
連接點
2.2.2 描述算法
②流程圖
流程圖符號 名稱 功能
開始/結束框 表示算法的開始或結束
輸入/輸出框 表示輸入或輸出數據
處理框 框中指出要處理的內容，此框有一個入口和一個出口
判斷框 用于表示條件判斷及產生分支的情況，判斷框有四個頂點，通常上面的頂點表示入口
流程線 用于控制流程方向
連接點 用于連接因頁面寫不下而斷開的流程線
2.2.2 描述算法
②流程圖
流程圖繪制軟件
在線繪制流程圖網站
操作時，我們可以在紙上手工繪制流程圖，也可以使用工具軟件或者到特定的網站進行繪制。
文稿處理軟件
2.2.2 描述算法
②流程圖
A
C
B
順序結構
算法有順序結構、選擇結構和循環結構三種基本的控制結構。
A
條件
False
True
循環結構
每個步驟按先后次序依次執行
按照條件的成立與否，選擇執行不同的分支
條件成立反復執行A,一旦不成立跳出循環
False
True
A
B
條件
選擇結構（分支結構）
2.2.2 描述算法
②流程圖
對比選擇結構與循環結構，你有什么發現？
A
條件
False
True
循環結構
False
True
A
B
條件
選擇結構（分支結構）
自上而下
2.2.2 描述算法
②流程圖
觀察描述“紅燈變綠燈”問題的算法，它包含了哪些基本控制結構？
結束
t ← 15
t ≥ 1
輸出t
t ← t-1
True
False
保持顯示1秒
清除顯示
開始
循環結構
順序結構
2.2.2 描述算法
②流程圖
某城市公交車票價2元，乘客可以刷卡乘車。刷卡時，若公交車余額不足2元，提示“請投幣”；若余額大于或等于2元但是小于10元，提示“余額即將不足”；若余額大于或等于10元，提示“歡迎乘車”；請你用流程圖描述該功能實現的算法。
輸入
獲取當前的公交卡余額M
輸出
輸出對應的提示語
主要結構
選擇結構
2.2.2 描述算法
②流程圖
某城市公交車票價2元，乘客可以刷卡乘車。刷卡時，若公交車余額不足2元，提示“請投幣”；若余額大于或等于2元但是小于10元，提示“余額即將不足”；若余額大于或等于10元，提示“歡迎乘車”；請你用流程圖描述該功能實現的算法。
2.2.2 描述算法
③偽代碼
偽代碼是采用一種類似程序設計語言的代碼來描述算法。
t ← 15
while t ≥ 1
output 1
sleep 1s
clear
t ← t-1
end while
結束
t ← 15
t ≥ 1
輸出t
t ← t-1
True
False
保持顯示1秒
清除顯示
開始
2.2.2 描述算法
練一練：
算法有（ ）結構、（ ）結構和循環結構三種基本的控制結構。
閱讀下面的流程圖，它主要包括（ ）結構，它的功能為（ ）。
順序
選擇/分支
求100以內能夠被3整除的數
選擇、循環
for i in range(1,101):
if i%3==0:
print(i)
算法效率
求100以內能夠被3整除的數
求100000以內能夠被3整除的數
算法輔助運算
在解決問題時，可根據問題規模，選擇合適算法
均體現了“算法效率”
圓周率的計算問題
在實際解決問題的過程中，應綜合考慮問題類型、問題規模、適用范圍等因素，選擇合適算法。
課堂總結
算法概念和描述
算法的概念
算法的特征
算法的效率
算法的描述方法
有輸入
有輸出
確定性
有窮性
可行性
一個算法通常要求有0個或多個輸入。
一個算法可以有一個或多個輸出。
算法必須能在有限個步驟之后終止。
算法中的每一步都是可以執行的。
算法的每個步驟都具有確定的含義。
自然語言
流程圖
偽代碼
用日常所用語言來描述算法的步驟。
流程圖是用圖形表示算法的一種常用工具。
采用一種類似程序設計語言的代碼來描述算法。
算法就是解決一個特定問題而采取的確定的，有限的步驟。
對于同一個問題，不同算法解決問題的效率不同。
課堂實踐練習
2. 某地有兩種不同類型的出租車，其計費標準分別為：甲車3千米起步，價格10元，3千米以上（含3千米）每千米為2元；乙車3千米起步，價格8元，3千米以上（含3千米）每千米2.2元。
設計算法，在不同里程時給出最優資費的用車選擇。選用一種描述方法對該算法進行描述，并解釋其中使用到的基本結構。
1.小明早上從起床到出門上學需要洗漱（5min）,燒水（10min）,準備早餐（10min）,聽新聞（10min）,請你為他設計一個合理的算法步驟。
課堂實踐練習
J←甲車的起步價
Y←乙車的起步價
x1←甲車起步里程后，每千米的費用
x2←乙車起步里程后，每千米的費用
n←計劃行使的里程數
J,Y,x1,x2,n
n ≥ 3
甲車省錢
J開始
J←J+x1×(n-3)
Y←Y+x2×(n-3)
True
True
False
J>Y
False
True
乙車省錢
兩車相同
False
結束
流程圖
2. 某地有兩種不同類型的出租車，其計費標準分別為：甲車3千米起步，價格10元，3千米以上（含3千米）每千米為2元；乙車3千米起步，價格8元，3千米以上（含3千米）每千米2.2元。

展開更多......

收起↑