教科版高中信息技術必修一（新教材）課件：4.1算法及其特征

4.1算法及其特征第4單元計算與問題解決學習目標3.運用恰當?shù)姆绞矫枋鏊惴ā?.了解算法的基本要素和重要特征。1.熟悉將解決問題的方法歸結為一系列清晰、準確的步驟的過程。4.運用Python語言實現(xiàn)簡單算法，解決問題，了解算法的基本要素和重要特征。（重點）運用Python語言實現(xiàn)簡單算法，解決問題，（難點）

面試第一題：“一個房間里有3盞燈，房間外有3個開關分別控制這3盞燈，在只允許進房間一次的情況下，如何判斷哪個開關控制那盞燈？任務一活動1尋找“開關對應關系”(P86-P87)圖4.1.1開關對應關系第一步：第二步：第三步：第四步：第五步：小組討論后，寫出步驟：第一步：打開1、2兩個開關第二步：過2分鐘后關閉1號開關第三步：進房間，亮著的燈是由2號開關控制第四步：摸一下另外兩盞不亮的燈，發(fā)熱的燈泡是由1號開關控制第五步：不亮又不熱的燈是由3號開關控制步驟如下：完善“開關對應關系”流程圖關1號開關燈亮？燈熱？該燈由2號開關控制該燈由1號開關控制該燈由3號開關控制1.有窮性算法必須能在執(zhí)行有限個步驟后終止。2.確切性算法中的每次運算都有明確的定義，具有無二義性，并且可以通過計算得到唯一的結果。3.輸入項一個算法有0個或多個輸入，所謂0個輸入是指算法本身給出了初始條件。4.輸出項算法一定要有輸出。至少產生一個輸出。5.可行性算法中執(zhí)行的任何計算都可以在有限時間內完成（有效性），算法中的運算都必須是可以實現(xiàn)的。算法的特征算法描述：3種用自然語言描述算法用流程圖描述算法代碼描述算法ForI=1toNifn能被3、5、7整除余數(shù)為2、3、2

then

輸出nexitforendifnextForI=1toNifn能被3、5、7整除余數(shù)為2、3、2

then

輸出nexitforendifnext

面試第二題：有4個分別裝了4種藥丸的藥瓶，每顆藥丸都有單顆標準質量，其中有一個藥瓶中的所有藥丸都被污染了。每顆被污染的藥丸比正常藥丸增重1克。只允許稱量一次，請判斷出哪個藥瓶中的藥被污染了。互相討論該問題的解決步驟，試將P89橫線補充完整。任務一活動2尋找“被污染的藥丸”(P88-P89)任務一活動3尋找“誤刪的ID號”(P89-P90)

面試第三題：學校歷屆校友的數(shù)據(jù)存儲在學校網(wǎng)絡中心服務器中(共10000條，無重復數(shù)據(jù))，某管理員由于誤操作刪除了一位校友的ID號(8位整數(shù))。恰好在備份文件中保存了所有人員的ID號(無重復數(shù)據(jù)，無序)。怎樣快速找出被誤刪的ID號以便恢復數(shù)據(jù)?誤刪的號的流程圖IDtarget=0#設置初始值f1=open(r"copy.txt")#打開備份文件list1=f1.readlines()#讀取每行數(shù)據(jù)forlineinlist1:#依次處理列表list1中的數(shù)據(jù)target=target^int(line)#將讀取的數(shù)據(jù)做異或運算f1.close#關閉備份文件f2=open(r"trouble.txt")#打開故障文件list2=f2.readlines()#按行讀取故障文件forlineinlist2:#依次處理列表list2中的數(shù)據(jù)target=target^int(line)#將讀取的數(shù)據(jù)做異或運算f2.close#關閉備份文件print("被刪除的ID號是:",target)#輸出被刪除的ID號根據(jù)流程圖及提示信息補充P90代碼，結果如下:

這次面試的冠軍在A、B、C、D四位同學中。A說：“不是我?！盉說：“是C?！盋說：“是D?！盌說：“C說的不對?！币阎娜酥杏幸蝗苏f了假話。你能判斷到底誰是冠軍嗎？任務二求解“誰是冠軍”枚舉

解析：利用枚舉法，逐一假設A、B、C、D是冠軍，判斷是否正確。冠軍A說：“不是我?！盉說：“是C?！盋說：“是D?！盌說：“C說的不對?！盇×××√B√××√C√√×√D√×√×枚舉

用程序求誰是冠軍時，我們需要把每個人說的話轉化成計算機能夠執(zhí)行的表達式。如A說：“不是我?！笨梢员硎緸椤癷!='A'”，其中i為枚舉的冠軍選手編號。枚舉

分析以下代碼的含義，理解解題思路，并在橫線上填寫語句的功能。champion=['A','B','C','D']#設置選手列表foriinchampion:#______________________________cond=(i!='A')+(i=='C')+(i=='D')+(i!='D')#___________________ifcond==3:print("冠軍是:",i)枚舉

請在Python中輸入代碼并運行程序，看看誰是冠軍。答案

冠軍是:

C枚舉

有一種算法是把所有可能的答案一一列舉，合適就保留，不合適就丟棄。這種方法稱作“枚舉”或“窮舉”。枚舉法解決問題的一般結構：循環(huán)+判斷。

優(yōu)勢：易證明正確性枚舉1.找出三位正整數(shù)中能被7整除的整數(shù)。參考答案：foriinrange(100,1000):ifi%7==0:print(i)鞏固提升2.在一千多年前的《孫子算經(jīng)》中，有這樣一道算術題：“今