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

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

面試第一題：“一個(gè)房間里有3盞燈，房間外有3個(gè)開關(guān)分別控制這3盞燈，在只允許進(jìn)房間一次的情況下，如何判斷哪個(gè)開關(guān)控制那盞燈？任務(wù)一活動(dòng)1尋找“開關(guān)對(duì)應(yīng)關(guān)系”(P86-P87)圖4.1.1開關(guān)對(duì)應(yīng)關(guān)系第一步：第二步：第三步：第四步：第五步：小組討論后，寫出步驟：第一步：打開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)對(duì)應(yīng)關(guān)系”流程圖關(guān)1號(hào)開關(guān)燈亮？燈熱？該燈由2號(hào)開關(guān)控制該燈由1號(hào)開關(guān)控制該燈由3號(hào)開關(guān)控制1.有窮性算法必須能在執(zhí)行有限個(gè)步驟后終止。2.確切性算法中的每次運(yùn)算都有明確的定義，具有無二義性，并且可以通過計(jì)算得到唯一的結(jié)果。3.輸入項(xiàng)一個(gè)算法有0個(gè)或多個(gè)輸入，所謂0個(gè)輸入是指算法本身給出了初始條件。4.輸出項(xiàng)算法一定要有輸出。至少產(chǎn)生一個(gè)輸出。5.可行性算法中執(zhí)行的任何計(jì)算都可以在有限時(shí)間內(nèi)完成（有效性），算法中的運(yùn)算都必須是可以實(shí)現(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個(gè)分別裝了4種藥丸的藥瓶，每顆藥丸都有單顆標(biāo)準(zhǔn)質(zhì)量，其中有一個(gè)藥瓶中的所有藥丸都被污染了。每顆被污染的藥丸比正常藥丸增重1克。只允許稱量一次，請判斷出哪個(gè)藥瓶中的藥被污染了。互相討論該問題的解決步驟，試將P89橫線補(bǔ)充完整。任務(wù)一活動(dòng)2尋找“被污染的藥丸”(P88-P89)任務(wù)一活動(dòng)3尋找“誤刪的ID號(hào)”(P89-P90)

面試第三題：學(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ù)?誤刪的號(hào)的流程圖IDtarget=0#設(shè)置初始值f1=open(r"copy.txt")#打開備份文件list1=f1.readlines()#讀取每行數(shù)據(jù)forlineinlist1:#依次處理列表list1中的數(shù)據(jù)target=target^int(line)#將讀取的數(shù)據(jù)做異或運(yùn)算f1.close#關(guān)閉備份文件f2=open(r"trouble.txt")#打開故障文件list2=f2.readlines()#按行讀取故障文件forlineinlist2:#依次處理列表list2中的數(shù)據(jù)target=target^int(line)#將讀取的數(shù)據(jù)做異或運(yùn)算f2.close#關(guān)閉備份文件print("被刪除的ID號(hào)是:",target)#輸出被刪除的ID號(hào)根據(jù)流程圖及提示信息補(bǔ)充P90代碼，結(jié)果如下:

這次面試的冠軍在A、B、C、D四位同學(xué)中。A說：“不是我?！盉說：“是C。”C說：“是D。”D說：“C說的不對(duì)。”已知四人中有一人說了假話。你能判斷到底誰是冠軍嗎？任務(wù)二求解“誰是冠軍”枚舉

解析：利用枚舉法，逐一假設(shè)A、B、C、D是冠軍，判斷是否正確。冠軍A說：“不是我。”B說：“是C。”C說：“是D。”D說：“C說的不對(duì)。”A×××√B√××√C√√×√D√×√×枚舉

用程序求誰是冠軍時(shí)，我們需要把每個(gè)人說的話轉(zhuǎn)化成計(jì)算機(jī)能夠執(zhí)行的表達(dá)式。如A說：“不是我。”可以表示為“i!='A'”，其中i為枚舉的冠軍選手編號(hào)。枚舉

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

請?jiān)赑ython中輸入代碼并運(yùn)行程序，看看誰是冠軍。答案

冠軍是:

C枚舉

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

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