2.2算法的概念及其描述-2023年10月-學(xué)習(xí)目標(biāo)描述算法的特征，理解算法在問題解決過程中的作用。選用恰當(dāng)?shù)拿枋龇椒ê涂刂平Y(jié)構(gòu)表示簡單算法，增強(qiáng)用算法解決問題的意識。情境描述小明到北京旅游，他乘坐火車到達(dá)了北京站，然后準(zhǔn)備乘坐地鐵去天安門參觀，地鐵線路圖如下圖所示，你能幫小明規(guī)劃好路線嗎？是否只有一條路線？請大家思考這個問題。

體驗探索地鐵1號線尋找路線的方法，可以稱之為算法。解決同一個問題的算法可能有多種。2.2.1認(rèn)識算法廣義上講，算法是解決一個特定問題而采取的確定的、有限的步驟。在計算機(jī)領(lǐng)域，算法作為一個精心設(shè)計的運算序列，描述了計算機(jī)如何將輸入轉(zhuǎn)化為輸出的過程。2.2.1認(rèn)識算法如何幫助牧羊人成功渡河？算法是解決一個特定問題而采取的確定的、有限的步驟。2.2.1認(rèn)識算法算法一般具有如下特征：有輸入：一個算法一般要求有0個或多個輸入。有輸出：一個算法可以有一個或多個輸出。有窮性：算法必須能在執(zhí)行有限個步驟之后終止，也就是算法的步驟不能是無限的?？尚行裕核惴ㄖ械拿恳徊降牟僮鞫际强梢詧?zhí)行的，或者都可以分解成計算機(jī)可執(zhí)行的基本操作。確定性：算法的每個步驟都具有確定的含義，沒有歧義。杜絕含糊不清、模棱兩可、二義性描述。2.2.1認(rèn)識算法練一練：1.下面關(guān)于算法的描述，正確的是（）A.算法就是解決問題的方法和步驟。B.算法可以被無限制的執(zhí)行。C.算法描述了計算機(jī)如何將輸入轉(zhuǎn)化為輸出的過程。D.算法可以有零個或多個輸入，但只能有一個輸出。

C解析：A:算法是解決一個特定問題而采取的確定的、有限的步驟。B:有窮性：算法必須能在執(zhí)行有限個步驟之后終止，也就是算法的步驟不能是無限的。D:算法一般要求有0個或多個輸入，1或多個輸出。2.2.2描述算法小明在去往地鐵站時，在路口遇到了一個紅綠燈。小明發(fā)現(xiàn)該紅綠燈上配有一個倒計時器，倒計時15秒之后紅燈變成了綠燈，如何將“倒計時15秒”的算法描述出來？描述“紅燈變綠燈”問題的算法描述算法是將解決問題的步驟用一種可理解的方式表示出來。

①自然語言②流程圖③偽代碼2.2.2描述算法描述“紅燈變綠燈”問題的算法①自然語言將計數(shù)器t（剩余秒數(shù)）設(shè)為15；如果t大于等于1，執(zhí)行步驟③，否則執(zhí)行步驟⑤；顯示t，并保持顯示1秒，然后清除顯示；將t的值減1，跳轉(zhuǎn)至步驟②。倒計時結(jié)束。自然語言指人們?nèi)粘Ｋ玫恼Z言。用自然語言描述算法就是用人們能夠讀懂的簡短語言對算法的步驟進(jìn)行描述。易于理解，但有時容易產(chǎn)生二義性，干擾后續(xù)編程實現(xiàn)。2.2.21認(rèn)識算法當(dāng)你想要從北京去上海迪士尼旅游，你會如何規(guī)劃行程呢？①網(wǎng)上購買迪士尼門票；②根據(jù)日期，購買火車票或者飛機(jī)票；③根據(jù)行程及日期安排，預(yù)訂住宿酒店；④帶好各種票據(jù)，準(zhǔn)備好行李，按時乘車；⑤到達(dá)上海，乘坐出租車或公共交通車輛去往酒店入住，放行李；⑥帶好門票，按時到迪士尼游玩。①自然語言2.2.2描述算法②流程圖

結(jié)束t←15t≥1輸出tt←t-1TrueFalse保持顯示1秒清除顯示開始自然語言流程圖2.2.2描述算法②流程圖流程圖是用圖形表示算法的一種常用工具。用流程圖描述的算法直觀易讀，問題解決的步驟清晰簡潔，算法結(jié)構(gòu)表達(dá)明確。

開始/結(jié)束框輸入/輸出框處理框判斷框流程線連接點2.2.2描述算法②流程圖

流程圖符號名稱功能開始/結(jié)束框表示算法的開始或結(jié)束輸入/輸出框表示輸入或輸出數(shù)據(jù)處理框框中指出要處理的內(nèi)容，此框有一個入口和一個出口判斷框用于表示條件判斷及產(chǎn)生分支的情況，判斷框有四個頂點，通常上面的頂點表示入口流程線用于控制流程方向連接點用于連接因頁面寫不下而斷開的流程線2.2.2描述算法②流程圖

流程圖繪制軟件在線繪制流程圖網(wǎng)站操作時，我們可以在紙上手工繪制流程圖，也可以使用工具軟件或者到特定的網(wǎng)站進(jìn)行繪制。文稿處理軟件2.2.2描述算法②流程圖

ACB順序結(jié)構(gòu)算法有順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)三種基本的控制結(jié)構(gòu)。A條件FalseTrue

循環(huán)結(jié)構(gòu)每個步驟按先后次序依次執(zhí)行按照條件的成立與否，選擇執(zhí)行不同的分支條件成立反復(fù)執(zhí)行A,一旦不成立跳出循環(huán)FalseTrue

AB條件選擇結(jié)構(gòu)（分支結(jié)構(gòu)）2.2.2描述算法②流程圖

對比選擇結(jié)構(gòu)與循環(huán)結(jié)構(gòu)，你有什么發(fā)現(xiàn)？A條件FalseTrue

循環(huán)結(jié)構(gòu)FalseTrue

AB條件選擇結(jié)構(gòu)（分支結(jié)構(gòu)）自上而下2.2.2描述算法②流程圖

觀察描述“紅燈變綠燈”問題的算法，它包含了哪些基本控制結(jié)構(gòu)？結(jié)束t←15t≥1輸出tt←t-1TrueFalse保持顯示1秒清除顯示開始循環(huán)結(jié)構(gòu)順序結(jié)構(gòu)2.2.2描述算法②流程圖

某城市公交車票價2元，乘客可以刷卡乘車。刷卡時，若公交車余額不足2元，提示“請投幣”；若余額大于或等于2元但是小于10元，提示“余額即將不足”；若余額大于或等于10元，提示“歡迎乘車”；請你用流程圖描述該功能實現(xiàn)的算法。輸入獲取當(dāng)前的公交卡余額M輸出輸出對應(yīng)的提示語主要結(jié)構(gòu)選擇結(jié)構(gòu)2.2.2描述算法②流程圖

某城市公交車票價2元，乘客可以刷卡乘車。刷卡時，若公交車余額不足2元，提示“請投幣”；若余額大于或等于2元但是小于10元，提示“余額即將不足”；若余額大于或等于10元，提示“歡迎乘車”；請你用流程圖描述該功能實現(xiàn)的算法。2.2.2描述算法③偽代碼

偽代碼是采用一種類似程序設(shè)計語言的代碼來描述算法。t←15whilet≥1output1sleep1scleart←t-1endwhile結(jié)束t←15t≥1輸出tt←t-1TrueFalse保持顯示1秒清除顯示開始2.2.2描述算法練一練：

算法有（

）結(jié)構(gòu)、（

）結(jié)構(gòu)和循環(huán)結(jié)構(gòu)三種基本的控制結(jié)構(gòu)。閱讀下面的流程圖，它主要包括（

）結(jié)構(gòu)，它的功能為（

）。順序選擇/分支求100以內(nèi)能夠被3整除的數(shù)選擇、循環(huán)foriinrange(1,101):ifi%3==0:print(i)算法效率求100以內(nèi)能夠被3整除的數(shù)求100000以內(nèi)能夠被3整除的數(shù)算法輔助運算在解決問題時，可根據(jù)問題規(guī)模，選擇合適算法均體現(xiàn)了“算法效率”圓周率的計算問題在實際解決問題的過程中，應(yīng)綜合考慮問題類型、問題規(guī)模、適用范圍等因素，選擇合適算法。課堂總結(jié)算法概念和描述算法的概念算法的特征算法的效率算法的描述方法有輸入有輸出確定性有窮性可行性一個算法通常要求有0個或多個輸入。一個算法可以有一個或多個輸出。算法必須能在有限個步驟之后終止。算法中的每一步都是可以執(zhí)行的。算法的每個步驟都具有確定的含義。自然語言流程圖偽代碼用日常所用語言來描述算法的步驟。流程圖是用圖形表示算法的一種常用工具。采用一種類似程序設(shè)計語言的代碼來描述算法。算法就是解決一個特定問題而采取的確定的，有限的步驟。對于同一個問題，不同算法解決問題的效率不同。課堂實踐練習(xí)

2.某地有兩種不同類型的出租車，其計費標(biāo)準(zhǔn)分別為：甲車3千米起步，價格10元，3千米以上（含3千米）每千米為2元；乙車3千米起步，價格8元，3千米以上（含3千米）每千米2.2元。設(shè)計算法，在不同里程時給出最優(yōu)資費的用車選擇。選用一種描述方法對該算法進(jìn)行描述，并解釋其中使用到的基本結(jié)構(gòu)。1.小明早上從起床到出門上學(xué)需要洗漱（5min）,燒水（10min）,準(zhǔn)備早餐（10min）,聽新聞（10min）,請你為他設(shè)計一個合理的算法步驟。課堂實踐練習(xí)

J←甲車的起步價Y←乙車的起步價x1←甲車起步里程后，每千米的費用x2←乙車起步里程后，每千米的費用n←計劃行使的里程數(shù)J,Y,x1,x2,nn≥3甲車省錢J<Y開始J←J+x1×(n-3)Y←Y+x2×(n-