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

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

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

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

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

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

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

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

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

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

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

ifcond==3:

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

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

ifcond==3:#說真話是否是3人

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

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

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