資源簡介

(共19張PPT)
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1 算法及其特征
四、計算與問題解決
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
軟件開發(fā)社團要招募新成員，報名的同學(xué)要經(jīng)過面試才能加入，面試測試有四個關(guān)卡，一起來闖關(guān)吧！！
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4
3
2
6
1
5
起止框
表示一個算法的開始與結(jié)束
輸入/輸出框
表示從外部輸入數(shù)據(jù)到計算機內(nèi)部或者從計算機內(nèi)部輸出數(shù)據(jù)到計算機.
處理框
表示操作的內(nèi)容.
判斷框
表示判斷的條件。滿足條件，執(zhí)行標(biāo)識為是的路徑，反之，執(zhí)行標(biāo)識為否的路徑.
流程線
連接符
表示流程圖的接續(xù)。在相互關(guān)系的流程圖內(nèi)，流程線將在具有相同字?jǐn)?shù)或字母的另一連接符處繼續(xù)下去.
60秒準(zhǔn)備
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1算法及其特征
第一關(guān)：“尋找開關(guān)對應(yīng)關(guān)系”
一個房間有三盞燈，房間外有三個開關(guān)分別控制這三盞燈，在只允許進房間一次的情況下，如何判斷哪個開關(guān)控制哪盞燈？
思考：如何能使3盞燈處于不同的狀態(tài)？
燈亮
燈滅
發(fā)熱
不發(fā)熱
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
①
②
③
思考：如何能使3盞燈處于不同的狀態(tài)？
4.1算法及其特征
第一關(guān)：“尋找開關(guān)對應(yīng)關(guān)系”
請完善以下“開關(guān)對應(yīng)關(guān)系”流程圖（P98圖4.1.2)
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1算法及其特征
開始
為開關(guān)和燈分別編碼
開1號、2號開關(guān)，等待片刻
進房間
結(jié)束
是
是
否
否
關(guān)1號開關(guān)
該燈由2號開關(guān)控制
該燈由1號開關(guān)控制
該燈由3號開關(guān)控制
燈是否亮
燈是否發(fā)熱
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
▼算法：
算法可能是一個計算公式，可能是一個贏得游戲的策略，也可能是一個解決綜合問題的復(fù)雜方案。可以用自然語言、流程圖、程序代碼來描述。
4.1算法及其特征
1、“開關(guān)對應(yīng)關(guān)系” 算法中有（ ）個輸出項？
2、“開關(guān)對應(yīng)關(guān)系”算法的執(zhí)行結(jié)果是（ ）。
3、“開關(guān)對應(yīng)關(guān)系”算法的執(zhí)行步驟是（ ）。
A.0個
B.1個
C.多個
A.確定的
B.不確定
C.都可以
A.有限的
B.無限的
C.都可以
C
A
A
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
算法一定要有輸出，任何算法都不能無功而返。
4、輸出性
5、可行性
算法必須能在執(zhí)行有限個步驟之后終止。
1、有窮性
算法中的每一次運算都有明確的定義，具有無二義性，并且也可以通過計算得到唯一的結(jié)果。
2、確切性
一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身給出了初始條件。
3、輸入性
算法中執(zhí)行的任何計算都可在有限時間內(nèi)完成，也稱為有效性算法中的運算都必須是可以實現(xiàn)的。
算法
4.1算法及其特征
解決問題的方法和步驟；
描述算法的方法：自然語言和流程圖
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1算法及其特征
第二關(guān)：尋找“被污染藥丸”
有四個裝了藥丸的罐子，每個藥丸都有一定的重量，其中有一個藥罐被污染了。每片被污染的藥丸比污染前增重 1 克。只允許稱量一次，判斷出哪個罐子的藥被污染了。
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
如果從每個藥瓶中取出一顆藥丸分別進行稱重，可以不可以判斷出哪顆藥丸被污染了 這樣做符合條件嗎？
注意：
討論時間為3分鐘，題目條件是“只能稱量一次”。
①
②
③
④
4.1算法及其特征
第二關(guān)：尋找“被污染藥丸”
定量分析
考慮1顆藥丸的重量變化，如果藥丸被污染，則增重 g，否則增重 g。
從某一個藥瓶中取出n顆藥丸，如果被污染，則增重 g，否則增重 g。
1
0
n
0
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
定量分析
如果我們從不同的藥瓶中取出不同顆數(shù)的藥丸：
如果增重 3g，則 號藥瓶中的藥丸被污染。
如果增重 g， 則 號藥瓶中的藥丸被污染。
n
n
①
②
③
④
4.1算法及其特征
第二關(guān)：尋找“被污染藥丸”
取1顆 取2顆 取3顆 取4顆 ，共10顆藥丸。
3
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1算法及其特征
加時賽
回顧算法的特點，思考一下，在這個問題中，哪些信息屬于輸入、哪些信息屬于輸出呢？
請設(shè)計程序并運行，使輸入10顆藥丸的總重量及4種藥丸的單顆準(zhǔn)質(zhì)量就可以看到結(jié)果，找到被污染的藥丸。
d=int(input('請輸入每顆藥丸的標(biāo)準(zhǔn)重量：'))
w=int(input('請輸入藥丸稱得的重量：'))
x=w-10*d
print('被污染的藥瓶序號是：',x)
input("運行完畢，請按回車鍵退出...")
現(xiàn)象（可多選） 算法的特征
輸入項： □0個輸入 □1個輸入 □多個輸入
輸出項： □0個輸出 □1個輸出 □多個輸出
執(zhí)行的結(jié)果：□確定的 □不確定的 □都可以
執(zhí)行的步驟：□有限 □無限 □都可以
執(zhí)行的時間：□有限 □無限 □都可以
0個或多個
輸入
一定有輸出
確切性
有窮性
可行性
√
√
√
√
√
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1算法及其特征
第三關(guān) 運用巧算，尋找“誤刪的ID號”
學(xué)校歷屆校友的數(shù)據(jù)存儲在學(xué)校網(wǎng)絡(luò)中心服務(wù)器中（共10000條，無重復(fù)數(shù)據(jù)），某管理員由于誤操作刪除了一位校友的ID號（8位整數(shù)）。恰好在備份文件中保存了所有人員的ID號（無重復(fù)數(shù)據(jù)，無序）。
怎樣快速找出被誤刪的ID號以便恢復(fù)數(shù)據(jù)？
歸納ID號的特征
數(shù)據(jù)類型及大小范圍：
數(shù)據(jù)在兩個文件中出現(xiàn)的次數(shù)：
備份文件中ID號總和與故障文件中的ID號總和的差值為：
通過分析，發(fā)現(xiàn)計算備份文件中ID號總和與故障文件中的ID號總和的差值就是：
整型（int）
2次
被刪除的ID
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1算法及其特征
第三關(guān) 運用巧算，尋找“誤刪的ID號”
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1算法及其特征
第四關(guān) 求解“誰是冠軍 ”
不是我
是C
是D
C說的不對
A
B
C
D
有一人說了假話。你能判斷出到底誰是冠軍嗎？
枚舉(窮舉)法
把所有可能的答案一一列舉，合適就保留，不合適就丟棄。
# 遍歷champion列表
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
第四關(guān) 求解“誰是冠軍 ”
4.1算法及其特征
1、枚舉法：稱為窮舉法，是利用計算機運算速度快、精確度高的特點，把所有可能的答案一一列舉，合適就保留,不合適就丟棄。
2.枚舉法解決問題的一般結(jié)構(gòu):循環(huán)+判斷。（確定窮舉范圍+確定驗證條件）
3.枚舉法需要逐一驗證所有的可能情況，運算量比較大，解決問題的效率不夠高。因此，使用枚舉法解決問題時，需要考慮優(yōu)化算法，選擇恰當(dāng)?shù)拿杜e對象，盡量分析出問題中的隱含條件,縮小枚舉范圍，以提高解決問題的效率。
# 遍歷champion列表
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
1、歷經(jīng)中外科學(xué)家姜長英、藤村幸三郎、清水達雄、馬丁加達納等幾十年的努力，游戲解法已由六十多年前的87步減少至81步。
2、美國一個律師托馬斯.萊曼(Thomas B.Lenann)發(fā)現(xiàn)一個新的解法，由加德納公布在1964年3月《科學(xué)美國人》上，有81步，稱加德納解法。
3、華容道的最快走法在中國是100步，在日本是82步。后來美國人用計算機，使用窮舉法找出了最終解法，不可能有再快的解法了，81步。美國人在用計算機找到最終解法后，跟中國人開玩笑說美國一位著名的博士找到了最終解法，這位博士名叫computer。
華容道
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
小結(jié)：算法的特征
有窮性
確切性
輸出項
可行性
輸入項
算法必須能在執(zhí)行有限個步驟之后終止。
算法中的每一次運算都有明確的定義，具有無二義性，并且可以通過計算得到唯一的結(jié)果。
算法一定要有輸出。任何算法都不能 “無功而返＂ 。
輸入項。一個算法有0個或多個輸入，以刻畫運算對象的初始悄況，所謂0個輸入是指算法本身給出了初始條件。
算法中執(zhí)行的任何計算都可以在有限時間內(nèi)完成（也稱為 有效性）。
驚艷你的
世界
The future is coming and The future is coming
THANKS
THANKS
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276

展開更多......

收起↑