4.1算法及其特征課件教科版高中信息技術(shù)必修1-1

4.1算法及其特征第2單元編程計(jì)算第1單元初識(shí)數(shù)據(jù)與計(jì)算第3單元認(rèn)識(shí)數(shù)據(jù)第4單元計(jì)算與問(wèn)題解決第5單元數(shù)據(jù)分析與人工智能信息技術(shù)（必修1）算法及其特征學(xué)習(xí)目標(biāo)★了解算法的基本要素和重要特征?！镞\(yùn)用恰當(dāng)?shù)姆绞矫枋鏊惴?。★運(yùn)用Python語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單算法，解決問(wèn)題。溫故知新1.什么是算法？2.描述算法的方法有哪些？算法是解決問(wèn)題的方法和步驟。自然語(yǔ)言流程圖偽代碼程序代碼PAD圖01知識(shí)回顧流程圖大作戰(zhàn)游戲規(guī)則九宮格底下藏有流程圖圖例或基本結(jié)構(gòu)的照片，小組搶答選擇卡片數(shù)字，老師點(diǎn)擊該卡片，卡片就會(huì)消失在熒幕上，猜出照片上的知識(shí)即可獲勝?；卮疱e(cuò)誤，繼續(xù)搶答回答問(wèn)題。123456789101112131415161718123456789101112131415161718123456789101112131415161718123456789101112131415161718123456789101112131415161718123456789101112131415161718軟件設(shè)計(jì)師是業(yè)務(wù)領(lǐng)域和技術(shù)領(lǐng)域的專(zhuān)家。面對(duì)客戶(hù)需求，軟件設(shè)計(jì)師要對(duì)問(wèn)題進(jìn)行整體分析以找到解決方案，通過(guò)洽當(dāng)?shù)姆绞脚c客戶(hù)溝通；面對(duì)技術(shù)問(wèn)題，軟件設(shè)計(jì)師需要借助計(jì)算機(jī)編程解決實(shí)際問(wèn)題。我們將通過(guò)“軟件開(kāi)發(fā)社招新”項(xiàng)目討論計(jì)算機(jī)編程解決問(wèn)題的過(guò)程。情境：猜一猜猜價(jià)格贏大禮游戲規(guī)則：1.商品的價(jià)格在100元以?xún)?nèi)（整數(shù)），參與的顧客要猜出這件商品的價(jià)格，即可獲得獎(jiǎng)品。2.主持人會(huì)根據(jù)顧客給出的價(jià)格，提示“猜高了”或“猜低了”，直到你猜對(duì)價(jià)格。3.時(shí)間限制：30s猜價(jià)格贏大禮情境：猜一猜情境：猜一猜設(shè)計(jì)：“猜價(jià)格”小游戲由于顧客眾多，我們能不能設(shè)計(jì)一款線(xiàn)上的猜價(jià)格小游戲，讓更多的顧客參與到活動(dòng)中。算法算法：解決問(wèn)題的方法和步驟。算法設(shè)計(jì)：“猜價(jià)格”小游戲——初級(jí)版任務(wù)一：請(qǐng)你幫忙設(shè)計(jì)一個(gè)“猜價(jià)格”算法。算法的表現(xiàn)形式自然語(yǔ)言流程圖計(jì)算機(jī)語(yǔ)言price=66guess=int(input("輸入你猜的價(jià)格:"))ifguess<price:print("猜小了")elifguess>price:print("猜大了")else:print("恭喜你，猜中了！")請(qǐng)你們幫忙測(cè)試一下程序，提出你的建議和需要改進(jìn)的地方！設(shè)計(jì)：“猜價(jià)格”小游戲——初級(jí)版任務(wù)二：請(qǐng)大家結(jié)合“自然語(yǔ)言”的描述，

完善流程圖和程序代碼。設(shè)計(jì)：“猜價(jià)格”小游戲——改良版第一步：設(shè)置商品價(jià)格第二步：顧客輸入猜的價(jià)格第三步：判斷顧客輸入的價(jià)格和商品價(jià)格

是否相同第四步：如果相同，則輸出“猜對(duì)了！”，

游戲結(jié)束第五步：如果不相同，判斷輸入的價(jià)格

是否猜低了第六步：如果成立，則輸出“猜低了！”，并返回第二步第七步：如果不成立，則輸出“猜高了！”，并返回第二步自然語(yǔ)言開(kāi)始結(jié)束①輸出“猜對(duì)了”輸出“猜低了”是否是否②⑤④③流程圖設(shè)計(jì)：“猜價(jià)格”小游戲——改良版自然語(yǔ)言流程圖開(kāi)始結(jié)束設(shè)置商品價(jià)格猜對(duì)了猜低了輸出“猜對(duì)了”輸出“猜低了”輸出“猜高了”是否是否輸入猜的價(jià)格第一步：設(shè)置商品價(jià)格第二步：顧客輸入猜的價(jià)格第三步：判斷顧客輸入的價(jià)格和商品價(jià)格

是否相同第四步：如果相同，則輸出“猜對(duì)了！”，

游戲結(jié)束第五步：如果不相同，判斷輸入的價(jià)格

是否猜低了第六步：如果成立，則輸出“猜低了！”，并返回第二步第七步：如果不成立，則輸出“猜高了！”，并返回第二步設(shè)計(jì)：“猜價(jià)格”小游戲——改良版price=66whileTrue:guess=int(input("輸入你猜的價(jià)格："))ifguess<price:print("猜小了！")elifguess>price:print("猜大了！")else:print("恭喜你，猜中了！")breakprice=66guess=int(input("輸入你猜的價(jià)格:"))ifguess<price:print("猜小了!")elifguess>price:print("猜大了!")else:print("恭喜你，猜中了！")VS改良版初級(jí)版設(shè)計(jì)：“猜價(jià)格”小游戲——改良版任務(wù)三：根據(jù)商家需求，設(shè)計(jì)一個(gè)可以限制競(jìng)猜次數(shù)的“猜價(jià)格”小游戲。設(shè)計(jì)：“猜價(jià)格”小游戲——進(jìn)階版price=66foriinrange(1,6):guess=int(input("輸入你猜的價(jià)格："))ifguess<price:print("猜小了！你還有",5-i,"次機(jī)會(huì)")elifguess>price:print("猜大了！你還有",5-i,"次機(jī)會(huì)")else:print("恭喜你，猜中了！")break設(shè)計(jì)：“猜價(jià)格”小游戲——進(jìn)階版商品價(jià)格簡(jiǎn)單猜100以?xún)?nèi)100次1000以?xún)?nèi)1000次10000以?xún)?nèi)10000次………7次10次14次對(duì)半猜設(shè)計(jì)：“猜價(jià)格”小游戲——進(jìn)階版算法——二分法二分查找：也叫折半查找，該方法主要將數(shù)列有序排列，采用跳躍式的方式查找數(shù)據(jù)。二分法查找的前提條件是被查找的數(shù)據(jù)必須是有序的。算法——二分法算法——二分法思考：對(duì)半猜的次數(shù)是如何計(jì)算的？算法的評(píng)價(jià)算法的評(píng)價(jià)：從時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)考慮。算法的特征根據(jù)我們對(duì)已學(xué)算法的了解，結(jié)合程序的設(shè)計(jì)你能歸納一下算法有哪些特征嗎？算法的特征price=66whileTrue:guess=int(input("輸入你猜的價(jià)格："))ifguess<price:print("猜小了！")elifguess>price:print("猜大了！")else:print("恭喜你，猜中了！")break輸入項(xiàng)輸出項(xiàng)開(kāi)始結(jié)束設(shè)置商品價(jià)格猜對(duì)了猜低了輸出“猜對(duì)了”輸出“猜低了”輸出“猜高了”是否是否輸入猜的價(jià)格確切性、可行性、有窮性算法的特征輸入項(xiàng)：有0個(gè)或多個(gè)輸入。0個(gè)輸入是指算法本身給出了初始條件。輸出項(xiàng)：算法一定要有輸出。有1個(gè)或多個(gè)輸出?？尚行裕核惴ㄖ袌?zhí)行的任何計(jì)算都可以在有限時(shí)間內(nèi)完成。有窮性：算法必須能在執(zhí)行有限個(gè)步驟之后終止。確切性：算法中的每一次運(yùn)算都有明確的定義，具有無(wú)二義性，并且

可以通過(guò)計(jì)算得到唯一的結(jié)果。12345算法的特征輸出所有的正整數(shù)。100/正整數(shù)100/0XXX有窮性：一個(gè)算法必須保證他的執(zhí)行步驟是有限的。確定性：算法中的每個(gè)步驟必須有確切的含義?？尚行裕核惴ㄖ械拿總€(gè)步驟都是可行的，能在有限的時(shí)間內(nèi)完成。誰(shuí)是競(jìng)猜冠軍任務(wù)四：根據(jù)“猜價(jià)格”小游戲后臺(tái)數(shù)據(jù)的統(tǒng)計(jì)，請(qǐng)你幫商家評(píng)出這次活動(dòng)的競(jìng)猜冠軍。誰(shuí)是競(jìng)猜冠軍這次競(jìng)猜的冠軍在A、B、C、D四位顧客中。A說(shuō)：“不是我。”B說(shuō)：“是C?！盋說(shuō)：“是D。”D說(shuō)：“C說(shuō)的不對(duì)。”已知四人中有一人說(shuō)了假話(huà)。你能判斷出到底誰(shuí)是冠軍嗎？小提示：逐一假設(shè)A、B、C、D是冠軍，判斷是否正確誰(shuí)是競(jìng)猜冠軍冠軍A說(shuō)：“不是我?！盉說(shuō)：“是C。”C說(shuō)：“是D?！盌說(shuō)：“C說(shuō)的不對(duì)?！盇BCDx誰(shuí)是競(jìng)猜冠軍√√√xxx√xxx√√√√x冠軍A說(shuō)：“不是我?！盉說(shuō)：“是C?！盋說(shuō)：“是D。”D說(shuō)：“C說(shuō)的不對(duì)?！盇BCDx√xxxxxxx√√√√√√√競(jìng)猜冠軍誰(shuí)是競(jìng)猜冠軍champion=['A','B','C','D']foriinchampion:

cond=(i!='A')+(i=='C')+(i=='D')+(i!='D')

ifcond==3:

print("冠軍是:",i)邏輯運(yùn)算誰(shuí)是競(jìng)猜冠軍champion=['A','B','C','D']#設(shè)置選手列表foriinchampion:#循環(huán)讀取選手編號(hào)

cond=(i!='A')+(i=='C')+(i=='D')+(i!='D')#查找符合條件的選手

ifcond==3:#說(shuō)真話(huà)是否是3人

print("冠軍是:",i)#輸出冠軍邏輯運(yùn)算誰(shuí)是競(jìng)猜冠軍算法——枚舉法把所有可能的答案一一例舉，合適就保留，不合適就丟棄。

——枚舉法枚舉法也稱(chēng)作窮舉法。算法——枚舉法枚舉法解決問(wèn)題的一般結(jié)構(gòu)：循環(huán)+判斷枚舉法解題的基本思路如下：1.確定枚舉對(duì)象、枚舉范圍和判定條件；2.一一列舉可能的解，驗(yàn)證是否為問(wèn)題的解。算法——枚舉法優(yōu)點(diǎn)：直觀、易于理解。

正確性容易證明。缺點(diǎn)：運(yùn)算量較大，解題效率不高。課堂鞏固1.下列有關(guān)算法的描述正確的是（）A.算法描述只有流程圖才能確保無(wú)二義性B.算法必須在有限步驟執(zhí)行后終止C.算法描述中必須要有輸入項(xiàng),否則無(wú)法進(jìn)行運(yùn)算D.一種算法設(shè)計(jì)只對(duì)應(yīng)一種計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言2.使用枚舉法解決問(wèn)題