算法及其特征-教案

4.1算法及其特征【學習目標】1.通過解決藥丸問題，嘗試運用恰當?shù)姆椒枋鏊惴ā?.能夠?qū)⒉糠趾唵嗡惴ㄞD(zhuǎn)換為程序，并調(diào)試運行得出結(jié)果?！窘虒W重點】能夠分析問題，設計解決問題的算法，并用恰當?shù)姆椒枋鏊惴?；了解枚舉法的含義，并能使用枚舉法解決相關(guān)問題?！窘虒W難點】能夠設計出解決問題的算法。【教學過程】第一課時一、引入師：葉達報名參加學校軟件開發(fā)社團時。面試中有一道IQ題：有四個裝了藥丸的罐子，每個藥丸都有一定的重量，其中有一個藥罐被污染了。每片被污染的藥丸比污染前增重1克。只允許稱量一次，判斷出哪個罐子的藥被污染了。（同座位討論該問題的解決步驟）生：用自然語言描述問題解決的步驟。第一步：第二步：師：在生活中很多類似的問題，在解決問題過程中都需要有一定方法。這種問題解決的方法實際就是算法。二、算法及其表示方法師：算法的定義在2.1節(jié)已經(jīng)學過了，請大家再回顧一下，算法的表示方法有幾種。生：自然語言、流程圖、程序。師：來看下面這個問題的解決。學校歷屆校友的海量數(shù)據(jù)存儲在校網(wǎng)絡中心服務器中（共10000條，無重復數(shù)據(jù)），某管理員因為誤操作刪除了一位校友的ID號（8位整數(shù)）信息，恰好在備份數(shù)據(jù)庫中保存了一份所有人員ID號的文件（無重復數(shù)據(jù)，無序）。怎樣快速找出被誤刪的ID號以便恢復數(shù)據(jù)？例如：網(wǎng)絡中心服務器ID列表備份服務器ID列表19750001197602301999000219990003……1999000319750001197602302001043219990002……請同座位討論，用自然語言描述問題求解的算法。生：取出網(wǎng)絡中心服務器ID列表中第一條數(shù)據(jù)；和備份服務器中的ID列表逐條進行對比，如果能夠找到相同的ID號，則完成目標，否則取出網(wǎng)絡中心服務器ID列表中下一條數(shù)據(jù)繼續(xù)比對。師：最差情況下，按照該算法解決問題需要進行多少次比較？生：10000*10000，1億次。師：還有沒有其他方法？（提示：可以利用異或運算）異或應用于邏輯運算，其運算法則為：0^0=0，1^0=1，0^1=1，1^1=0。由于兩個相同數(shù)異或結(jié)果為0，而任何數(shù)異或0的結(jié)果等于數(shù)據(jù)本身。因此，可以把兩文件中所有ID號直接進行異或，只出現(xiàn)一次的數(shù)據(jù)就能被找出，并且最后出現(xiàn)的異或結(jié)果就是這個數(shù)。（學生可能會提出將中心服務器的ID號全部加起來，然后減去備份服務器的ID號，得到的數(shù)就是被刪除的ID號，可以讓學生比較它和異或的方法）請重新思考該問題解決的算法，并用流程圖表示出來。（可以用^表示異或）生：圖1師：請思考下面的問題。1.計算備份庫ID號異或結(jié)果的循環(huán)結(jié)構(gòu)和計算中心庫ID號異或結(jié)果的循環(huán)結(jié)構(gòu)能不能交換順序？2.如何存放兩個數(shù)據(jù)庫中ID號？生：1.可以交換；2.列表、文件、數(shù)據(jù)庫。師：已知備份數(shù)據(jù)庫文件存放在“copy.txt”中，中心服務器文件存放在“trouble.txt”中，用程序?qū)崿F(xiàn)該問題的解決。提示：文件的一般使用方法f1=open(r"copy.txt")#打開文件list1=f1.readlines()#讀取每行數(shù)據(jù)，list1是一個記錄了問題所有元素的列表……f1.close#關(guān)閉文件生：target=0#設置初始值f1=open(r"copy.txt")#打開備份文件list1=f1.readlines()#讀取每行數(shù)據(jù)forlineinlist1:#依次處理列表list1中的數(shù)據(jù)target=target^int(line)#將讀取的數(shù)據(jù)做異或運算f1.close#關(guān)閉備份文件f2=open(r"trouble.txt")#打開故障文件list2=f2.readlines()#按行讀取故障文件forlineinlist2:#依次處理列表list2中的數(shù)據(jù)target=target^int(line)#將讀取的數(shù)據(jù)做異或運算f2.close#關(guān)閉備份文件print("被刪除的ID號是:",target)#輸出被刪除的ID號三、算法的特征師：思考解決“被刪除的ID號”算法中的一些規(guī)律，思考算法應該具有哪些特征。填寫下表?，F(xiàn)象（可多選）算法的特征輸入項：□0個輸入□1個輸入□多個輸入輸出項：□0個輸出□1個輸出□多個輸出執(zhí)行的結(jié)果：□確定的□不確定的□都可以執(zhí)行的步驟：□有限□無限□都可