高一【信息技術(shù)(人教中圖版)】算法概念與描述（第八課時）-課件

算法概念與描述（第八課時）

年級：高一學(xué)科：信息技術(shù)（人教/中圖版）主講人：

學(xué)校：地鐵1號線情境描述小明到北京旅游，他乘坐火車到達(dá)了北京站，然后準(zhǔn)備乘坐地鐵去天安門參觀，地鐵線路圖如下圖所示，你能幫小明規(guī)劃好路線嗎？是否只有一條路線？請大家思考這個問題。路線1：乘坐地鐵2號線，從北京站到建國門站，在建國門站換乘1號線，在天安門東站下車。

地鐵1號線路線1：共乘坐4站，換乘1次。情境描述路線2：乘坐地鐵2號線，從北京站到崇文門站，在崇文門站換乘5號線，到東單站，在東單站換乘1號線，在天安門東站下車。

地鐵1號線路線2：共乘坐4站，換乘2次。情境描述地鐵1號線地鐵1號線情境描述尋找路線的方法，可以稱之為算法當(dāng)你想要從北京去上海迪士尼旅游，你會如何規(guī)劃行程呢？算法的概念廣義上講，算法是解決一個特定問題而采取的確定的、有限的步驟。

①網(wǎng)上購買迪士尼門票；②根據(jù)日期，購買火車票或者飛機(jī)票；③根據(jù)行程及日期安排，預(yù)訂住宿酒店；④帶好各種票據(jù)，準(zhǔn)備好行李，按時乘車；⑤到達(dá)上海，乘坐出租車或公共交通車輛去往酒店入住，放行李；⑥帶好門票，按時到迪士尼游玩。解決同一個問題的算法可能有多種。算法就是在解決特定問題時，采取的確定的、有限的步驟。算法的概念其他方案

分析解決以下三個問題的算法，歸納算法的特征。算法的特征

分析項目①拋物線執(zhí)行的步驟個數(shù)每一步是否明確可執(zhí)行是否有輸入是否有輸出4

是否是算法的特征分析項目①拋物線②分段函數(shù)③絕對值執(zhí)行的步驟個數(shù)4每一步是否明確可執(zhí)行是是否有輸入無是否有輸出有算法的特征分析項目①拋物線②分段函數(shù)③絕對值執(zhí)行的步驟個數(shù)454每一步是否明確可執(zhí)行是是是是否有輸入無有有是否有輸出有有有算法的特征在計算機(jī)領(lǐng)域，算法作為一個精心設(shè)計的運(yùn)算序列，描述了計算機(jī)如何將輸入轉(zhuǎn)化為輸出的過程。算法一般具有如下特征：算法的特征算法的特征有輸入一個算法通常要求有0個或多個輸入。有輸出一個算法可以有一個或多個輸出。有窮性算法必須能在有限個步驟之后終止?？尚行运惴ㄖ械拿恳徊蕉际强梢詧?zhí)行的。確定性算法的每個步驟都具有確定的含義，沒有歧義。算法已經(jīng)廣泛應(yīng)用于各領(lǐng)域中，不只是解決數(shù)學(xué)問題。例如，如何在圖書管理系統(tǒng)中查找需要的書籍？解決該問題的過程也是算法嗎？符合算法的五個特征嗎？算法的特征自然語言小明在去往地鐵站時，在路口遇到了一個紅綠燈。小明發(fā)現(xiàn)該紅綠燈上配有一個倒計時器，倒計時15秒之后紅燈變成了綠燈，如何將“倒計時15秒”的算法描述出來？算法的描述方法自然語言將計數(shù)器t（剩余秒數(shù)）設(shè)為15；如果t大于等于1，執(zhí)行步驟③，否則執(zhí)行步驟⑤；顯示t，并保持顯示1秒，然后清除顯示；將t的值減1，跳轉(zhuǎn)至步驟②。倒計時結(jié)束。倒計時15秒？自然語言歧義易于理解流程圖是用圖形表示算法的一種常用工具。用流程圖描述的算法直觀易讀，問題解決的步驟清晰簡潔，算法結(jié)構(gòu)表達(dá)明確。開始/結(jié)束框輸入/輸出框處理框判斷框流程線流程圖流程圖符號名稱功能開始/結(jié)束框表示算法的開始或結(jié)束輸入/輸出框表示輸入或輸出數(shù)據(jù)處理框框中指出要處理的內(nèi)容，此框有一個入口和一個出口判斷框用于表示條件判斷及產(chǎn)生分支的情況，判斷框有四個頂點(diǎn)，通常上面的頂點(diǎn)表示入口流程線用于控制流程方向流程圖操作時，我們可以在紙上手工繪制流程圖，也可以使用工具軟件或者到特定的網(wǎng)站進(jìn)行繪制。文稿處理軟件流程圖繪制軟件在線繪制流程圖網(wǎng)站流程圖結(jié)束t←15t≥1輸出tt←t-1TrueFalse保持顯示1秒清除顯示倒計時15秒？將計數(shù)器t設(shè)為15；如果t大于等于1，執(zhí)行步驟③，否則執(zhí)行步驟⑤；顯示t，并保持顯示1秒，然后清除顯示；將t的值減1，跳轉(zhuǎn)至步驟②。倒計時結(jié)束。流程圖開始循環(huán)結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)三種基本結(jié)構(gòu)結(jié)束t←15t≥1輸出tt←t-1TrueFalse保持顯示1秒清除顯示開始S1Sn…順序結(jié)構(gòu)FalseTrue

S1S2C選擇結(jié)構(gòu)三種基本結(jié)構(gòu)S1CFalseTrue

循環(huán)結(jié)構(gòu)注意區(qū)分選擇和循環(huán)三種基本結(jié)構(gòu)FalseTrue

S1S2C選擇結(jié)構(gòu)S1CFalseTrue

循環(huán)結(jié)構(gòu)偽代碼t←15whilet≥1output1sleep1scleart←t-1endwhile規(guī)避了程序設(shè)計語言嚴(yán)格的書寫格式，無歧義，結(jié)構(gòu)性強(qiáng)。不太適合完全沒有程序設(shè)計基礎(chǔ)的初學(xué)者。倒計時15秒？偽代碼算法的描述方法算法的描述方法自然語言偽代碼流程圖自然語言就是使用日常所用的語言描述算法的步驟。優(yōu)點(diǎn)：使用簡單，易于理解。缺點(diǎn)：容易產(chǎn)生二義性。流程圖是用圖形表示算法的一種常用工具。優(yōu)點(diǎn)：步驟清晰簡潔，算法結(jié)構(gòu)表達(dá)明確，適合初學(xué)者使用。缺點(diǎn)：繪制過程繁瑣，對于復(fù)雜問題，結(jié)構(gòu)過于復(fù)雜，不易理解。偽代碼是采用一種類似程序設(shè)計語言的代碼來描述算法。優(yōu)點(diǎn)：回避了程序設(shè)計語言嚴(yán)格的書寫格式，敘述準(zhǔn)確，無二義性，結(jié)構(gòu)性強(qiáng)。缺點(diǎn)：需要具備一定的程序設(shè)計語言基礎(chǔ)，不利于初學(xué)者使用。某地有兩種不同類型的出租車，其計費(fèi)標(biāo)準(zhǔn)分別為：甲車3千米起步，價格10元，3千米以上（含3千米）每千米為2元；乙車3千米起步，價格8元，3千米以上（含3千米）每千米2.2元。設(shè)計算法，在不同里程時給出最優(yōu)資費(fèi)的用車選擇。選用一種描述方法對該算法進(jìn)行描述，并解釋其中使用到的基本結(jié)構(gòu)。實(shí)踐練習(xí)結(jié)構(gòu)？實(shí)踐練習(xí)p1←甲車的起步價p2←乙車的起步價x1←甲車起步里程后，每千米的費(fèi)用x2←乙車起步里程后，每千米的費(fèi)用n←計劃行使的里程數(shù)p1,p2,x1,x2,nn≥3甲車省錢p1<p2開始p1←p1+x1×(n-3+1)p2←p2+x2×(n-3+1)TrueTrueFalsep1>p2FalseTrue乙車省錢兩車相同F(xiàn)alse結(jié)束算法的描述方法順序結(jié)構(gòu)選擇結(jié)構(gòu)p1,p2,x1,x2,nn≥3甲車省錢p1<p2開始p1←p1+x1×(n-3+1)p2←p2+x2×(n-3+1)TrueTrueFalsep1>p2FalseTrue乙車省錢兩車相同F(xiàn)alse結(jié)束在實(shí)際問題解決中，經(jīng)常會將三種控制結(jié)構(gòu)綜合使用。已知有10個一模一樣的零件，其中9個零件的質(zhì)量相同，只有一個質(zhì)量略輕，不符合規(guī)格要求?，F(xiàn)在有一臺天平，請設(shè)計算法找出該零件。算法效率一一比較？次數(shù)？其他方法？1~5次二分法2~3次如果有n個零件（n＞10），要找出其中質(zhì)量較輕的一個零件，以上方法是否仍然可用？試分析n=10000時，這些算法在問題解決效率上的不同。算法效率一一比較二分法1~5000次5~13次效率更高在解決問題時，可根據(jù)問題規(guī)模，選擇合適算法地鐵1號線乘坐地鐵問題迪士尼旅游問題零件問題在實(shí)際解決問題的過程中，應(yīng)綜合考慮問題類型、問題規(guī)模、適用范圍等因素，選擇合適算法。算法效率小結(jié)算法概念和描述算法的概念算法的特征算法的效率算法的描述方法有輸入有輸出確定性有窮性可行性一個算法通常要求有0個或多個輸入。一個算法可以有一個或多個輸出。算法必須能在有限個步驟之后終止。算法中的每一步都是可以執(zhí)行的。算法的每個步驟都具有確定的含義。自然語言流程圖偽代碼用日常所用語言來描述算法的步驟。流程圖是用圖形表示算法的一種常用工具。采用一種類似程序設(shè)計語言的代碼來描述算法。算法就是解決一個特定問題而采取的確定的，有限的步驟。對于同一個問題，不同算法解決問題的效率不同。小結(jié)算法概念和描述算法的概念算法的特征算法的效率算法的描述方法有輸入有輸出確定性有窮性可行性一個算法通常要求有0個或多個輸入。一個算法可以有一個或多個輸出。算法必須能在有限個步驟之后終止。算法中的每一步都是可以執(zhí)行的。算法的每個步驟都具有確定的含義。自然語言流程圖偽代碼用日常所用語言來描述算法的步驟。流程圖