資源簡介

(共25張PPT)
算法的概念及描述
1. 認 識 算 法
2. 描 述 算 法
認識算法--問題探究
【案例1】有一個牧羊人，帶著一頭羊、一只狼和一顆大白菜準備乘船過河，但是船很小，每次只能帶一樣東西過去，可是如果狼和羊單獨在一起，羊就會被狼吃掉，羊和白菜單獨在一起，白菜就會被羊吃掉，那牧羊人怎樣才能將三者都順利的帶過河呢？
以小組為單位，討論幫助牧羊人帶著狼、羊、白菜順利過河的方案。
有一個牧羊人，帶著一頭羊、一只狼和一顆大白菜準備乘船過河，但是船很小，每次只能帶一樣東西過去，可是如果狼和羊單獨在一起，羊就會被狼吃掉，羊和白菜單獨在一起，白菜就會被羊吃掉，那牧羊人怎樣才能將三者都順利的帶過河呢？
思考以下問題：
（1）小組得出的方案共有多少步？
（2）這些步驟的順序是固定不變的嗎？
認識算法
參考方案：
（1）人和羊過河，人返回，留下羊。
認識算法
參考方案：
（1）人和羊過河，人返回，留下羊。
（2）人和狼過河，人和羊返回，留下狼。
認識算法
參考方案：
（1）人和羊過河，人返回，留下羊。
（2）人和狼過河，人和羊返回，留下狼。
（3）人和菜過河，人返回，留下菜。
認識算法
參考方案：
（1）人和羊過河，人返回，留下羊。
（2）人和狼過河，人和羊返回，留下狼。
（3）人和菜過河，人返回，留下菜。
（4）人和羊過河。
認識算法
算法的概念
為解決一類特定問題而采取的
確定的、有限的步驟。
認識算法
參考方案2：
（1）人和羊過河，人返回，留下羊。
（2）人和菜過河，人和羊返回，留下菜。
（3）人和狼過河，人返回，留下狼。
（4）人和羊過河。
參考方案1：
（1）人和羊過河，人返回，留下羊。
（2）人和狼過河，人和羊返回，留下狼。
（3）人和菜過河，人返回，留下菜。
（4）人和羊過河。
認識算法

認識算法
算法的概念
為解決一類特定問題而采取的
確定的、有限的步驟。
有些步驟可以顛倒，不影響最終結果。
有些步驟不能顛倒，一旦顛倒，最終的結果就完全不一樣。
注意
認識算法
有輸入
算法的每個步驟都具有確定的含義（沒有歧義）
算法的每一步操作都是可執行的
算法必須能在執行有限個步驟之后終止
（算法步驟不能是無限的）
有輸出
一個算法要求有0個或1個輸入
一個算法要求有1個或多個輸入
有窮性
確定性
可行性
算法特性
認識算法
參考方案：
（1）人和羊過河，人返回，留下羊。
（2）人和狼過河，人和羊返回，留下狼。
（3）人和菜過河，人返回，留下菜。
（4）人和羊過河。
自然語言
描述算法
自然語言
流程圖
偽代碼
描述算法
描述算法的方法
用自然語言描述算法
描述算法
自然語言：人們日常所用的語言。
用自然語言描述算法：使用人們能讀懂的簡短語句
對算法的步驟進行描述。
缺點：容易產生二義性
用流程圖描述算法
描述算法
流程圖：一種常用的表示算法的圖形化工具。
順序結構
選擇結構
循環結構
描述算法
三種基本控制結構
描述算法
1.順序結構
每一個步驟按先后次序被執行，即執行處理A,然后執行處理B，如圖所示。
描述算法
2.選擇結構
又稱分支結構。
根據條件的成立與否，選擇執行不同的分支處理，如圖所示。當條件成立時(用True表示),執行處理A;當條件不成立時(用False表示)，執行處理B。
描述算法
3.循環結構
當條件成立時，反復執行處理A，一旦條件不成立就立即結束循環，如圖所示。
問題探究
【案例2】中國古代的第一部數學專著《九章算術》中記載了“更相減損術”的方法：“可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。”
翻譯：任意給出兩個正數；判斷它們是否都是偶數。若是，用2約簡;若不是則用較大的數減去較小的數,接著把較小的數與所得的差比較,并以大數減小數。繼續這個操作,直到所得的數相等為止，則這個數(等數)就是所求的最大公約數。
小組討論用流程圖實現“利用輾轉相除法求a和b的最大公約數”的算法。
描述算法
參考方案
優點：克服了自然語言二義性的缺點。直觀易讀，問題解決的步驟清晰簡潔，算法結構表達明確。
a=r
輸入a,b
a不等于b
r=a-b
ra=b
b=r
輸出b
結束
開始
否
否
是
是
用偽代碼描述算法
描述算法
偽代碼描述算法：采用一種類似于程序設計語言的代碼來表示算法。
偽代碼沒有固定的、嚴格的語法規則，只要定義合理、沒有矛盾即可。回避了程序設計語言嚴格的書寫格式，保持了語言敘述準確、無二義性的優點，結構性強，比較容易書寫和理解。
課堂小結
算法的概念：
為解決一類特定問題而采取的確定的、有限的步驟。
算法的特征：
（1）有輸入
（2）有輸出
（3）有窮性
（4）可行性
（5）確定性
課堂小結
算法描述方法 優勢 不足
自然語言 通俗易懂 二義性，語句太長，循環和分支難以表達
流程圖 清晰簡潔，不依賴計算機 難度大
偽代碼 書寫方便，格式緊湊，便于翻譯 語言種類多，不容易規范化
算法描述方法 優勢 不足
自然語言
流程圖
偽代碼