資源簡介

(共49張PPT)
4.1算法及其特征
第2單元 編程計算
第1單元 初識數據與計算
第3單元 認識數據
第4單元 計算與問題解決
第5單元 數據分析與人工智能
信息技術
（必修1）
算法及其特征
學習目標
★ 了解算法的基本要素和重要特征。
★ 運用恰當的方式描述算法。
★ 運用Python語言實現簡單算法，解決問題。
溫故知新
1. 什么是算法？
2. 描述算法的方法有哪些？
算法是解決問題的方法和步驟。
自然語言
流程圖
偽代碼
程序代碼
PAD圖
01
知識回顧
流程圖大作戰
游戲規則
九宮格底下藏有流程圖圖例或基本結構的照片，小組搶答選擇卡片數字，老師點擊該卡片，卡片就會消失在熒幕上，猜出照片上的知識即可獲勝。回答錯誤，繼續搶答回答問題。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
軟件設計師是業務領域和技術領域的專家。面對客戶需求，軟件設計師要對問題進行整體分析以找到解決方案，通過洽當的方式與客戶溝通；面對技術問題，軟件設計師需要借助計算機編程解決實際問題。我們將通過“軟件開發社招新”項目討論計算機編程解決問題的過程。
情境：猜一猜
猜價格贏大禮
游戲規則：
1.商品的價格在100元以內（整數），參與的顧客要猜出這件商品的價格，即可獲得獎品。
2. 主持人會根據顧客給出的價格，提示“猜高了”或“猜低了”，直到你猜對價格。
3.時間限制：30s
猜價格贏大禮
情境：猜一猜
情境：猜一猜
設計：“猜價格”小游戲
由于顧客眾多，我們能不能設計一款線上的猜價格小游戲，讓更多的顧客參與到活動中。
算法
算法：解決問題的方法和步驟。
設計：“猜價格”小游戲——初級版
任務一：請你幫忙設計一個“猜價格”算法。
算法的表現形式
自然語言
流程圖
計算機語言
price=66
guess=int(input("輸入你猜的價格:"))
if guessprint("猜小了")
elif guess>price:
print("猜大了")
else:
print("恭喜你，猜中了！")
請你們幫忙測試一下程序，
提出你的建議和需要改進的地方！
設計：“猜價格”小游戲——初級版
任務二：請大家結合“自然語言”的描述，
完善流程圖和程序代碼。
設計：“猜價格”小游戲——改良版
第一步：設置商品價格
第二步：顧客輸入猜的價格
第三步：判斷顧客輸入的價格和商品價格
是否相同
第四步：如果相同，則輸出“猜對了！”，
游戲結束
第五步：如果不相同，判斷輸入的價格
是否猜低了
第六步：如果成立，則輸出“猜低了！”，
并返回第二步
第七步：如果不成立，則輸出“猜高了！”，
并返回第二步
自然語言
開始
結束
①
輸出“猜對了”
輸出“猜低了”
是
否
是
否
②
⑤
④
③
流程圖
設計：“猜價格”小游戲——改良版
自然語言
流程圖
開始
結束
設置商品價格
猜對了
猜低了
輸出“猜對了”
輸出“猜低了”
輸出“猜高了”
是
否
是
否
輸入猜的價格
第一步：設置商品價格
第二步：顧客輸入猜的價格
第三步：判斷顧客輸入的價格和商品價格
是否相同
第四步：如果相同，則輸出“猜對了！”，
游戲結束
第五步：如果不相同，判斷輸入的價格
是否猜低了
第六步：如果成立，則輸出“猜低了！”，
并返回第二步
第七步：如果不成立，則輸出“猜高了！”，
并返回第二步
設計：“猜價格”小游戲——改良版
price=66
while True:
guess=int(input("輸入你猜的價格："))
if guessprint("猜小了！")
elif guess>price:
print("猜大了！")
else:
print("恭喜你，猜中了！")
break
price=66
guess=int(input("輸入你猜的價格:"))
if guessprint("猜小了!")
elif guess>price:
print("猜大了!")
else:
print("恭喜你，猜中了！")
VS
改良版
初級版
設計：“猜價格”小游戲——改良版
任務三：根據商家需求，設計一個可以限制競猜次數的“猜價格”小游戲。
設計：“猜價格”小游戲——進階版
price=66
for i in range(1,6):
guess=int(input("輸入你猜的價格："))
if guessprint("猜小了！你還有",5-i,"次機會")
elif guess>price:
print("猜大了！你還有",5-i,"次機會")
else:
print("恭喜你，猜中了！")
break
設計：“猜價格”小游戲——進階版
商品價格 簡單猜
100以內 100次
1000以內 1000次
10000以內 10000次
… … …
7次
10次
14次
對半猜
設計：“猜價格”小游戲——進階版
算法——二分法
二分查找：也叫折半查找，該方法主要將數列有序排列，
采用跳躍式的方式查找數據。
二分法查找的前提條件是被查找的數據必須是有序的。
算法——二分法
算法——二分法
思考：對半猜的次數是如何計算的？
算法的評價
算法的評價：從時間復雜度和空間復雜度來考慮。
算法的特征
根據我們對已學算法的了解，結合程序的設計
你能歸納一下算法有哪些特征嗎？
算法的特征
price=66
while True:
guess=int(input("輸入你猜的價格："))
if guessprint("猜小了！")
elif guess>price:
print("猜大了！")
else:
print("恭喜你，猜中了！")
break
輸入項
輸出項
開始
結束
設置商品價格
猜對了
猜低了
輸出“猜對了”
輸出“猜低了”
輸出“猜高了”
是
否
是
否
輸入猜的價格
確切性、可行性、有窮性
算法的特征
輸入項：有0個或多個輸入。0個輸入是指算法本身給出了初始條件。
輸出項：算法一定要有輸出。有1個或多個輸出。
可行性：算法中執行的任何計算都可以在有限時間內完成。
有窮性：算法必須能在執行有限個步驟之后終止。
確切性：算法中的每一次運算都有明確的定義，具有無二義性，并且
可以通過計算得到唯一的結果。
1
2
3
4
5
算法的特征
輸出所有的正整數。
100/正整數
100/0
X
X
X
有窮性：一個算法必須保證他的執行步驟是有限的。
確定性：算法中的每個步驟必須有確切的含義。
可行性：算法中的每個步驟都是可行的，能在有限的時間內完成。
誰是競猜冠軍
任務四：根據“猜價格”小游戲后臺數據的統計，請你幫商家評出這次活動的競猜冠軍。
誰是競猜冠軍
這次競猜的冠軍在A、B、C、D四位顧客中。
A說：“不是我。”
B說：“是C。”
C說：“是D。”
D說：“C說的不對。”
已知四人中有一人說了假話。你能判斷出到底誰是冠軍嗎？
小提示：
逐一假設A、B、C、D是冠軍，判斷是否正確
誰是競猜冠軍
冠軍 A說：“不是我。” B說：“是C。” C說：“是D。” D說：“C說的不對。”
A
B
C
D
x
誰是競猜冠軍
√
√
√
x
x
x
√
x
x
x
√
√
√
√
x
冠軍 A說：“不是我。” B說：“是C。” C說：“是D。” D說：“C說的不對。”
A
B
C
D
x
√
x
x
x
x
x
x
x
√
√
√
√
√
√
√
競猜冠軍
誰是競猜冠軍
champion=['A','B','C','D']
for i in champion:
cond=(i!='A') +(i=='C') + (i=='D')+(i!='D')
if cond==3:
print("冠軍是:",i)
邏輯運算
誰是競猜冠軍
champion=['A','B','C','D'] #設置選手列表
for i in champion: #循環讀取選手編號
cond=(i!='A') +(i=='C') + (i=='D')+(i!='D') #查找符合條件的選手
if cond==3: #說真話是否是3人
print("冠軍是:",i) #輸出冠軍
邏輯運算
誰是競猜冠軍
算法——枚舉法
把所有可能的答案一一例舉，合適就保留，不合適就丟棄。
——枚舉法
枚舉法也稱作窮舉法。
算法——枚舉法
枚舉法解決問題的一般結構：循環+判斷
枚舉法解題的基本思路如下：
1.確定枚舉對象、枚舉范圍和判定條件；
2.一一列舉可能的解，驗證是否為問題的解。
算法——枚舉法
優點：直觀、易于理解。
正確性容易證明。
缺點：運算量較大，解題效率不高。
課堂鞏固
1.下列有關算法的描述正確的是（ ）
A.算法描述只有流程圖才能確保無二義性
B.算法必須在有限步驟執行后終止
C.算法描述中必須要有輸入項,否則無法進行運算
D.一種算法設計只對應一種計算機程序設計語言
2.使用枚舉法解決問題的優勢為（ ）
A.算法簡單、直接 B運算時間短
C.可以求解任何問題 D.算法靈活多樣
3.評價一個算法好的最主要標準是（ ）
A.運行速度快 B.運算準確度高
C.時間復雜度低 D.程序代碼短
B
A
C
知識小結
“算法”其實很接地氣，可以與我們的生活零距離靠近，讓生活變得更美好。

展開更多......

收起↑