資源簡介

(共36張PPT)
第4單元 計(jì)算與問題解決
信息技術(shù)
（必修1）
算法及其特征
學(xué)習(xí)目標(biāo)
★ 了解算法的基本要素和重要特征。
★ 運(yùn)用恰當(dāng)?shù)姆绞矫枋鏊惴ā?br/>★ 運(yùn)用Python語言實(shí)現(xiàn)簡單算法，解決問題。
溫故知新
1. 什么是算法？
2. 描述算法的方法有哪些？
算法是解決問題的方法和步驟。
自然語言
流程圖
偽代碼
程序代碼
PAD圖
01
知識(shí)回顧
流程圖大作戰(zhàn)
游戲規(guī)則
九宮格底下藏有流程圖圖例或基本結(jié)構(gòu)的照片，小組搶答選擇卡片數(shù)字，老師點(diǎn)擊該卡片，卡片就會(huì)消失在熒幕上，猜出照片上的知識(shí)即可獲勝。回答錯(cuò)誤，繼續(xù)搶答回答問題。
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
軟件設(shè)計(jì)師是業(yè)務(wù)領(lǐng)域和技術(shù)領(lǐng)域的專家。面對客戶需求，軟件設(shè)計(jì)師要對問題進(jìn)行整體分析以找到解決方案，通過洽當(dāng)?shù)姆绞脚c客戶溝通；面對技術(shù)問題，軟件設(shè)計(jì)師需要借助計(jì)算機(jī)編程解決實(shí)際問題。我們將通過“軟件開發(fā)社招新”項(xiàng)目討論計(jì)算機(jī)編程解決問題的過程。
※ 活動(dòng)1 尋找“開關(guān)對應(yīng)關(guān)系”
軟件開發(fā)社團(tuán)要招募新成員，報(bào)名的同學(xué)要經(jīng)過面試才能加入。第一關(guān)面試題是：“一個(gè)房間有3盞燈，房間外有3個(gè)開關(guān)分別控制這3盞燈在只允許進(jìn)房間一次的情況下， 如何判斷哪個(gè)開關(guān)控制哪盞燈？”
設(shè)計(jì)算法是解決問題的核心，它的基本任務(wù)是對問題進(jìn)行定性分析和定量分析，遵循算法的特征和約定，尋求計(jì)算的方法和規(guī)則，明確解決問題的途徑。
任務(wù)一 探討面試題的解決方案
分析問題—燈的狀態(tài)和特性
燈只有亮、滅兩種狀態(tài)，但是燈又具有一種特殊性，即開燈的同時(shí)會(huì)伴隨發(fā)光發(fā)熱，因此燈被觸摸時(shí)還有冷、熱兩種狀態(tài)。綜上所述，一盞燈可能有4種不同的狀態(tài)。
燈亮
燈滅
發(fā)熱
不發(fā)熱
怎么樣保證每盞燈的狀態(tài)都是唯一的？題目中并沒有限制開關(guān)按動(dòng)次數(shù)，所以3個(gè)開關(guān)的閉合狀態(tài)是可以隨意改變的。
單分支流程圖
也稱為程序框圖，它是描述問題解決的一種圖形化表示方法。與使用自然語言描述相比，用流程圖描述形象、直觀、更容易理解。
三種基本結(jié)構(gòu)
想一想，劃一劃
第一步：打開1、2兩個(gè)開關(guān)
第二步：過2分鐘后關(guān)閉1號(hào)開關(guān)
第三步：進(jìn)房間，亮著的燈是由2號(hào)開關(guān)控制
第四步：摸一下另外兩盞不亮的燈，發(fā)熱的燈泡是由1號(hào)開關(guān)控制
第五步：不亮又不熱的燈是由3號(hào)開關(guān)控制
自然語言
流程圖
關(guān)1號(hào)開關(guān)
燈亮？
燈熱？
該燈由2號(hào)開關(guān)控制
該燈由1號(hào)開關(guān)控制
該燈由3號(hào)開關(guān)控制
解決問題的方法及步驟
算法
設(shè)計(jì)算法
計(jì)算a,b兩數(shù)和與差
第一步：輸入兩個(gè)數(shù)a,b
第二步：計(jì)算兩數(shù)和s1=a+b
第三步：計(jì)算兩數(shù)差s2=a-b
第四步：輸出s1,s2
輸入兩個(gè)數(shù)a,b
計(jì)算s1=a+b,s2=a-b
Print s1,s2
輸入a,b
S1=a+b
S2=a-b
輸出s1,s2
輸入a,b
S1=a+b,s2=a-b
輸出s1,s2
算法的描述
自然語言
流程圖
偽代碼
N-S框圖
PAD圖
程序代碼
算法的特征
price=66
while True:
guess=int(input("輸入你猜的價(jià)格："))
if guessprint("猜小了！")
elif guess>price:
print("猜大了！")
else:
print("恭喜你，猜中了！")
break
輸入項(xiàng)
輸出項(xiàng)
開始
結(jié)束
設(shè)置商品價(jià)格
猜對了
猜低了
輸出“猜對了”
輸出“猜低了”
輸出“猜高了”
是
否
是
否
輸入猜的價(jià)格
確切性、可行性、有窮性
算法的特征
輸出所有的正整數(shù)。
100/正整數(shù)
100/0
X
X
X
有窮性：一個(gè)算法必須保證他的執(zhí)行步驟是有限的。
確定性：算法中的每個(gè)步驟必須有確切的含義。
可行性：算法中的每個(gè)步驟都是可行的，能在有限的時(shí)間內(nèi)完成。
算法的特征
有窮性
確切性
輸出項(xiàng)
可行性
輸入項(xiàng)
算法必須能在執(zhí)行有限個(gè)步驟之后終止。
算法中的每一次運(yùn)算都有明確的定義，具有無二義性，并且可以通過計(jì)算得到唯一的結(jié)果。
算法一定要有輸出。任何算法都不能 “無功而返＂ 。
輸入項(xiàng)。一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對象的初始悄況，所謂0個(gè)輸入是指算法本身給出了初始條件。
算法中執(zhí)行的任何計(jì)算都可以在有限時(shí)間內(nèi)完成（也稱為有效性）。
有4個(gè)分別裝了4種藥丸的藥瓶，里面每顆藥丸都有單顆標(biāo)準(zhǔn)質(zhì)量，其中有一個(gè)藥瓶中的所有藥丸都被污染了。 每顆被污染的藥丸比正常藥丸增重1克。請?jiān)谥辉试S稱量一次的情況下，判斷出哪個(gè)藥瓶中的藥丸被污染了。
活動(dòng)2 定量分析， 尋找”被污染的藥丸”
如果從每個(gè)藥瓶中取出1顆藥丸分別進(jìn)行稱重，肯定可以判斷出哪顆藥丸被污染了，但是這種做法顯然不符合 ”只能稱量一次＂ 的要求。 你能改進(jìn)判斷方法嗎？
考慮1顆藥丸的重量變化，如果藥丸被污染，則增重_____克，否則增重________克。
改進(jìn)算法
從某一個(gè)藥瓶中取出n顆藥丸，如果被污染，則增重_____克，否則增重________克。
如果我們從不同的藥瓶中取出不同顆數(shù)的藥丸，你能根據(jù)增重情 況找出被污染的藥丸嗎？
第1個(gè)藥瓶取1顆，第2個(gè)藥瓶取2顆，第3個(gè)藥瓶取3顆，笫4個(gè)藥瓶取4顆，共10顆藥丸。
如果增重______克，則_______號(hào)藥瓶中的藥丸被污染。
4.1 算法及其特征
分析問題：如果從每個(gè)藥瓶中取出1顆藥丸分別進(jìn)行稱重，肯定可以判斷哪顆藥丸被污染了，但這不符合題目要求。如何改進(jìn)判斷方法呢？考慮：1顆藥丸被污染，則增重1克；n顆藥丸被污染，則增重n克；如果我們從不同的瓶子中取出不同顆數(shù)的藥丸，則可以判斷是哪個(gè)瓶子被污染了。
解決問題的步驟（自然語言描述）
1.從第1個(gè)瓶子取出1顆藥丸；
2.從第2個(gè)瓶子取出2顆藥丸；
3.從第3個(gè)瓶子取出3顆藥丸；
4.從第4個(gè)瓶子取出4顆藥丸；
以上共10顆藥丸，進(jìn)行稱重，結(jié)果如下：
1.如果增重1克，則為1號(hào)瓶子污染；
2.如果增重2克，則為2號(hào)瓶子污染
……
請根據(jù)算法設(shè)計(jì)程序，輸入單顆藥丸重量及10顆藥丸的總重量，判斷輸出是哪個(gè)瓶子被污染。
活動(dòng)2 定量分析，解決問題
請?jiān)O(shè)計(jì)程序并運(yùn)行，使輸入10顆藥丸的總重量及4種藥丸的單顆準(zhǔn)質(zhì)量就可以看到結(jié)果，找到被污染的藥丸。
d=int(input('請輸入每顆藥丸的標(biāo)準(zhǔn)重量：'))
w=int(input('請輸入藥丸稱得的重量：'))
x=w-10*d
print('被污染的藥瓶序號(hào)是：',x)
input("運(yùn)行完畢，請按回車鍵退出...")
活動(dòng)3 巧用運(yùn)算， 尋找＂誤刪的ID號(hào)”
學(xué)校歷屆校友的數(shù)據(jù)存儲(chǔ)在學(xué)校網(wǎng)絡(luò)中心服務(wù)器中（共10000條，無重復(fù)數(shù)據(jù)），某管理員由于誤操作刪除了一位校友的ID號(hào)(8位整數(shù)）。恰好在備份文件中保存了所有人員的ID號(hào)（無重復(fù)數(shù)據(jù)，無序）。怎樣快速找出被誤刪的ID號(hào)以便恢復(fù)數(shù)據(jù)？
ID號(hào)的特征
1.ID數(shù)據(jù)類型：____________
2.數(shù)據(jù)在兩個(gè)文件中出現(xiàn)的次數(shù)：________
3.備份文件中1D號(hào)總和與故障文件中的ID號(hào)總和的差值為：__________
整型（int）
2次
被刪除的ID
自然語言描述算法
第一步：打開備份數(shù)據(jù)f1與故障數(shù)據(jù)f2
第二步：讀取備份數(shù)據(jù)list1，并數(shù)據(jù)求和target
第三步：讀取故障文件list2，并用備份數(shù)據(jù)和target減去故障數(shù)據(jù)和
第四步：輸出差值，即為誤刪ID號(hào)
備份ID號(hào)
故障ID號(hào)
設(shè)計(jì)算法——找出被刪除的ID
通過分析，我們發(fā)現(xiàn)計(jì)算備份文件ID號(hào)總和與故障文件ID號(hào)總和的差值就是誤刪的ID號(hào)。
target=________
f1=open('copy.txt', 'r’)
listl=fl.readlines()
for line in _____ :
target= target+int(line)
fl.____________
f2=open('trouble.txt', 'r’)
list2= _________
for ___________ :
target= __________
_________________
print(被誤刪的ID號(hào)是：，_______)
#設(shè)置初始值
＃打開備份文件
＃按行讀取備份文件
＃依次處理列表listl中的數(shù)據(jù)
＃將讀取的數(shù)據(jù)做加運(yùn)算
＃關(guān)閉備份文件
＃打開故障文件
＃按行讀取故障文件
＃依次處理列表list2中的數(shù)據(jù)
＃將讀取的數(shù)據(jù)做減運(yùn)算
＃關(guān)閉故障文件
#輸出被誤刪的ID號(hào)
0
list1
Close()
f2.readlines()
line in list2
target – int(line)
F2.close()
target
代碼解析
f1=open(‘copy.txt’, ‘r’) #open()函數(shù)打開外部存儲(chǔ)器中的文件，并賦值給內(nèi)存中的f1變量；
listl=fl.readlines() #按行讀取txt文件中的數(shù)據(jù)，并賦值到list1列表中；
f1.close() #close()函數(shù)關(guān)閉正在打開的文件
這次面試的冠軍在A 、 B 、 C 、 D四位同學(xué)中。 A說：“不是我。” B說：“是C”。“C說： “是D。”D說：“C說的不對。”已知四人中有一人說了假話。 你能判斷出到底誰是冠軍嗎？說出你的結(jié)論和判斷過程。
※ 活動(dòng) 嘗試枚舉
不是我
是C
是D
C說的不對
A
B
C
D
任務(wù)二 求解“誰是冠軍”
枚舉
有一種算法是把所有可能的答案一一列舉，合適就保留，不合適就丟棄。這種方法稱作“枚舉”或“窮舉”。
枚舉法解決問題的一般結(jié)構(gòu)：循環(huán)+判斷。
優(yōu)勢：易證明正確性
在不知道誰說真話、誰說假話的情況下，最簡單的方法就是把所有可能都枚舉出來。因?yàn)橹挥幸晃还谲姡钥梢悦杜e選手的編號(hào)，并對A、B、C、D四個(gè)人的話進(jìn)行判斷。
解析：利用枚舉法，逐一假設(shè)A、B、C、D是冠軍，判斷是否正確。
冠 軍 A說：“不是我。” B說：“是C。” C說：“是D。” D說：“C說的不對。”
A × × × √
B √ × × √
C √ √ × √
D √ × √ ×
用程序求誰是冠軍時(shí)，我們需要把每個(gè)人說的話轉(zhuǎn)化成計(jì)算機(jī)能夠執(zhí)行的表達(dá)式。如A說：“不是我。”可以表示為“i!='A'”，其中i為枚舉的冠軍選手編號(hào)。
champion= ['A','B','C','D'] ＃設(shè)置選手列表
for i in champion: # 遍歷champion列表
cond=(i! ='A')+(i=='C')+(i=='D')+(i! ='D')
if cond==3:
print(“冠軍是”,i)
設(shè)計(jì)算法
答案 冠軍是: C
在《孫子算經(jīng)》中，有這樣一道算術(shù)題：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？”。（即一個(gè)數(shù)除以3余2，除以5余3，除以7余2，求這個(gè)數(shù)。）
參考答案：
i=0
while (i%3!=2 or i%5!=3 or i%7!=2):
i=i+1
print(i)
鞏固提升
知識(shí)小結(jié)
課堂小結(jié)
算法：解決問題的方法和步驟；
算法的描述：
算法的特征：
有窮性：算法步驟有限；
確切行：每一次運(yùn)算的含義明確；
輸入項(xiàng)：一個(gè)算法有0個(gè)或多個(gè)輸入；
輸出項(xiàng)：算法一定要有輸出；
可行性：在有限時(shí)間內(nèi)完成；
計(jì)算機(jī)解決問題的一般過程：
自然語言
流程圖
偽代碼
N-S框圖
PAD圖
程序代碼
具體問題
分析問題
問題解決
設(shè)計(jì)算法
編寫程序
調(diào)試運(yùn)行

展開更多......

收起↑