資源簡介

(共32張PPT)
算法概念與描述
algorithm concepts and descriptions
信息技術(shù)
CONTENTS
目錄
認(rèn)識算法
總結(jié)
描述算法
1
2
3
情景描述
狼羊菜問題
一個農(nóng)夫帶著一條狼、一頭羊和一籃蔬菜要過河，但只有一條小船可用。乘船時，農(nóng)夫每趟只能帶一樣?xùn)|西。當(dāng)農(nóng)夫在場的時候，這三樣?xùn)|西相安無事。一旦農(nóng)夫不在，狼會吃羊，羊會吃菜。
請設(shè)計一個方案，使農(nóng)夫能安全地將這三樣?xùn)|西帶過河。
情景描述
方案一
情景描述
方案二
情景描述
01
02
04
03
農(nóng)夫帶羊過河
農(nóng)夫返回
農(nóng)夫帶狼過河
農(nóng)夫帶羊返回
農(nóng)夫帶菜過河
農(nóng)夫返回
農(nóng)夫帶羊過河
農(nóng)夫帶羊過河
農(nóng)夫返回
農(nóng)夫帶菜過河
農(nóng)夫帶羊返回
農(nóng)夫帶狼過河
農(nóng)夫返回
農(nóng)夫帶羊過河
解決農(nóng)夫帶狼羊菜過河的方法，可以稱之為算法
01
認(rèn)識算法
recognize algorithms
算法的概念
廣義上講，算法是解決一個特定問題而采取的確定的、有限的步驟。
清洗茶壺、茶杯、拿茶葉
燒水
泡茶
算法的概念
1
2
4
方案一：
方案二：
方案三：
以上方案中，哪一個可行且高效？
解決同一個問題的算法可能有多種。
算法的特征
《九章算術(shù)》“更相減損術(shù)”
算法的特征
在計算機(jī)領(lǐng)域，算法作為一個精心設(shè)計的運算序列，描述了計算機(jī)如何將輸入轉(zhuǎn)化為輸出的過程。算法一般具有如下特征：
算法的特征
有輸入
一個算法通常要求有0個或多個輸入。
有輸出
一個算法可以有一個或多個輸出。
有窮性
算法必須能在有限個步驟之后終止。
可行性
算法中的每一步都是可以執(zhí)行的。
確定性
算法的每個步驟都具有確定的含義，沒有歧義。
更相減損數(shù)中輸入153和119，print(“Hello,World!”)
02
描述算法
describe the algorithm
算法的描述方法
自然語言
小明在去往地鐵站時，在路口遇到了一個紅綠燈。小明發(fā)現(xiàn)該紅綠燈上配有一個倒計時器，倒計時15秒之后紅燈變成了綠燈，如何將“倒計時15秒”的算法描述出來？
算法的描述方法
自然語言
將計數(shù)器t（剩余秒數(shù)）設(shè)為15；
如果t大于等于1，執(zhí)行步驟③，否則執(zhí)行步驟⑤；
顯示t，并保持顯示1秒，然后清除顯示；
將t的值減1，跳轉(zhuǎn)至步驟②。
倒計時結(jié)束。
倒計時15秒？
算法的描述方法
優(yōu)勢
不足
簡單直接，比較容易掌握。
算法中含有多分支或循環(huán)操作較多時難以清晰表示；
自然語言的歧義性易導(dǎo)致算法執(zhí)行的不確定性。
小明請小李和他的朋友去看電影。
算法的描述方法
流程圖是用圖形表示算法的一種常用工具。用流程圖描述的算法直觀易讀，問題解決的步驟清晰簡潔，算法結(jié)構(gòu)表達(dá)明確。
流程圖
流程圖符號 名稱 功能
開始/結(jié)束框 表示算法的開始或結(jié)束
輸入/輸出框 表示輸入或輸出數(shù)據(jù)
處理框 框中指出要處理的內(nèi)容，此框有一個入口和一個出口
判斷框 用于表示條件判斷及產(chǎn)生分支的情況，判斷框有四個頂點，通常上面的頂點表示入口
流程線 用于控制流程方向
算法的描述方法
結(jié)束
t ← 15
t ≥ 1
輸出t
t ← t-1
True
False
保持顯示1秒
清除顯示
倒計時15秒？
將計數(shù)器t設(shè)為15；
如果t大于等于1，執(zhí)行步驟③，否則執(zhí)行步驟⑤；
顯示t，并保持顯示1秒，然后清除顯示；
將t的值減1，跳轉(zhuǎn)至步驟②。
倒計時結(jié)束。
開始
流程圖
算法的描述方法
循環(huán)結(jié)構(gòu)
順序結(jié)構(gòu)
選擇結(jié)構(gòu)
三種基本結(jié)構(gòu)
結(jié)束
t ← 15
t ≥ 1
輸出t
t ← t-1
True
False
保持顯示1秒
清除顯示
開始
算法的描述方法
S1
Sn
…
順序結(jié)構(gòu)
三種基本結(jié)構(gòu)--順序結(jié)構(gòu)
算法的描述方法
False
True
S1
S2
條件
選擇結(jié)構(gòu)
三種基本結(jié)構(gòu)--選擇結(jié)構(gòu)（分支結(jié)構(gòu)）
算法的描述方法
三種基本結(jié)構(gòu)
S1
條件
False
True
循環(huán)結(jié)構(gòu)
食堂阿姨打菜：接過顧客的餐盤→詢問菜品→打菜→遞回餐盤，重復(fù)以上過程，直到所有顧客的菜都打完為止。
公交司機(jī)：駕駛到一個站點→停車→開前后門→等乘客上下車→關(guān)門→繼續(xù)行駛，重復(fù)以上過程，直到交接班時間為止。
循環(huán)體
算法的描述方法
注意區(qū)分
選擇和循環(huán)
三種基本結(jié)構(gòu)
False
True
S1
S2
條件
選擇結(jié)構(gòu)
S1
條件
False
True
循環(huán)結(jié)構(gòu)
算法的描述方法
操作時，我們可以在紙上手工繪制流程圖，也可以使用工具軟件或者到特定的網(wǎng)站進(jìn)行繪制。
算法的描述方法
輾轉(zhuǎn)相除法
輸入m,n
R=0
m=n
循環(huán)結(jié)構(gòu)
算法的描述方法
偽代碼
t ← 15
while t ≥ 1
output 1
sleep 1s
clear
t ← t-1
end while
倒計時15秒？
三種描述方法的比較
算法描述的方法 優(yōu)勢 不足
自然語言 簡單直接易掌握 難以清晰表示
不確定性
流程圖 清晰簡潔 易于表達(dá)選擇結(jié)構(gòu) 利于不同環(huán)境的程序設(shè)計 形勢復(fù)雜
偽代碼 書寫方便易于理解 便于向計算機(jī)程序設(shè)計語言過渡 需懂專業(yè)技能才能編寫
不直觀
錯誤不容易排查
03
總結(jié)
summary
算法概念和描述
算法的概念
算法的特征
算法的描述方法
有輸入
有輸出
確定性
有窮性
可行性
一個算法通常要求有0個或多個輸入。
一個算法可以有一個或多個輸出。
算法必須能在有限個步驟之后終止。
算法中的每一步都是可以執(zhí)行的。
算法的每個步驟都具有確定的含義。
有輸入
有輸出
有窮性
可行性
自然語言
流程圖
偽代碼
用日常所用語言來描述算法的步驟。
流程圖是用圖形表示算法的一種常用工具。
采用一種類似程序設(shè)計語言的代碼來描述算法。
算法就是解決一個特定問題而采取的確定的，有限的步驟。
實踐練習(xí)
閱讀流程圖說出它的功能。
輸出0~100可以被3整除的所有整數(shù)
實踐練習(xí)
某城市公交車票價 2 元，乘客可以刷卡乘車。刷卡時，若公交卡余額不足 2 元，提示“請投幣”；若余額大于等于 2 元但小于 10 元，提示“余額即將不足”；若余額大于等于 10 元，提示“歡迎乘車”。請用流程圖描述該功能。
實踐練習(xí)
感謝聆聽
thanks for listening
信息技術(shù)

展開更多......

收起↑