22算法的概念及描述課件高一上學期高中信息技術必修1第2章人教中圖版

2.2算法的概念及描述年級：高一

學科：信息技術（人教/中圖）思考:1.列舉出由A站出發(fā)到達B站的所有換乘次數(shù)最少的乘車路線。2.如果小明同學希望盡快到達B站，試為他推薦一條最佳乘車路線，并說明理由。A-E-G-B或A-K-J-B或A-K-G-B體驗探索思考:1.列舉出由A站出發(fā)到達B站的所有換乘次數(shù)最少的乘車路線。2.如果小明同學希望盡快到達B站，試為他推薦一條最佳乘車路線，并說明理由。A-E-G-B或A-K-J-B或A-K-G-B體驗探索A-K-J-B或A-K-G-B

從廣義上講，算法是為解決一類特定問題而采取的確定的、有限的步驟。它描述出某類問題求解的方法和過程，在整個問題解決過程中起著重要的作用。算法的概念

“可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之?！薄毒耪滤阈g》更相減損術兩種情形步驟“不可半者”（如153和119）直接輾轉相減，直至減數(shù)和差相等：①153-119=34②119-34=85③85-34=51④51-34=17⑤34-17=17所以，153和119的最大公約數(shù)為17“可半者”（如24和16）第一步，現(xiàn)將24和16用2反復約簡，直至不都是偶數(shù)，約數(shù)最后為8（用2反復約簡了3次）第二步，分別將兩個約簡的數(shù)輾轉相減，直至減數(shù)和差相等：①3-2=1②2-1=1第三步，求差和約數(shù)的積：1×8=8所以，24和16的最大公約數(shù)為8更相減損術電梯運行鐵路訂票算法的應用共享單車外賣服務算法的應用

一個算法一般要求有0個或多個輸入,以描述運算對象的初始情況。

一個算法可以有一個或多個輸出,以反映對輸入數(shù)據(jù)加工后的結果。

算法的有窮性指算法必須能在執(zhí)行有限個步驟之后終止,也就是算法步驟不能是無限的。有窮性03有輸出02有輸入01算法的特征算法中的每一步操作都是可以執(zhí)行的,或者都可以分解成計算機可執(zhí)行的基本操作。算法的每個步驟都具有確定的含義,沒有歧義。模糊不清、模棱兩可或帶有二義性的描述都會影響算法的確定性?？尚行?4確定性05算法的特征描述算法就是將解決問題的步驟，用一種可理解的形式表示出來。常用的描述算法的方法有自然語言、流程圖和偽代碼等。算法的描述紅燈倒計時15s的描述用自然語言描述算法易于理解，它既可以描述生活中的算法，也可以描述在計算機中執(zhí)行的算法。但是,自然語言的描述方法存在容易產(chǎn)生二義性的缺點，有可能干擾后續(xù)的編程實現(xiàn)。步驟1：將計數(shù)器t設為15；步驟2：如果t大于或等于1，執(zhí)行步驟3，否則倒計時結束；步驟3：輸出t,并保持顯示1s，然后清除顯示；步驟4：將t的值減1，跳轉至步驟2。自然語言流程圖符號名稱功能

開始/結束框表示算法的開始或結束

輸入/輸出框表示輸入或輸出數(shù)據(jù)

處理框框中指出要處理的內容，此框有1個入口和1個出口流程圖流程圖符號名稱功能

判斷框用于表示條件判斷及產(chǎn)生分歧的情況，判斷框有4個頂點，通常上面的頂點表示入口，視需要用另外3個頂點來表示出口

流程線用于控制流程方向

連接點用于連接因頁面寫不下而斷開的流程線流程圖順序結構選擇結構循環(huán)結構123流程圖的三種結構

每一個步驟按先后次序被執(zhí)行，即執(zhí)行處理A，然后執(zhí)行處理B。

順序結構AB

又稱分支結構。根據(jù)條件的成立與否，選擇執(zhí)行不同的分支處理。當條件成立時(True)，執(zhí)行處理A；當條件不成立時(False)，執(zhí)行處理B。

AB條件TrueFalse選擇結構

當條件成立時，反復執(zhí)行處理A，一旦條件不成立就立即結束循環(huán)。

B條件TrueFalse循環(huán)結構倒計時15s流程圖t←15t≥1TrueFalse輸出t開始結束清除顯示保持顯示1st←t-1流程圖是一種常用的表示算法的圖形化工具。用流程圖描述的算法直觀易讀，問題解決的步驟清晰簡潔，算法結構表達明確，很適合初學算法的人員使用。

繪制流程圖的方法很多，可以手工繪制流程圖，也可以用軟件制作，如使用文本編輯軟件中的“流程圖”對象繪制，或使用專門的流程圖繪制軟件，還可以到在線繪制流程圖網(wǎng)站進行制作。流程圖用偽代碼描述算法就是采用一種類似于程序設計語言的代碼來表示算法。偽代碼沒有固定的、嚴格的語法規(guī)則，只要定義合理，沒有矛盾即可。

用偽代碼描述算法回避了程序設計語言嚴格的書寫格式，保持了語言敘述準確、無二義性的優(yōu)點，結構性強，比較容易書寫和理解。倒計時15s偽代碼t←15whilet≥1outputtsleep1scleart←t-1endwhile自然語言流程圖偽代碼優(yōu)點容易理解形象直觀容易理解簡潔易懂修改容易缺點書寫較煩、容易產(chǎn)生不確定性、歧義等。所占篇幅較大，過于靈活，不受約束修改困難等。不直觀、錯誤不容易排查三種描述方法的對比找出質量較輕的零件

已知有10個一模一樣的零件，其中9個零件的質量相同，只有1個質量略輕，不符合規(guī)格要求?，F(xiàn)在有一臺天平，請設計算法找出該零件。

1.如果采用一一比較的方法，逐一稱重對比，最多需要比較多少次才能找出這個質量較輕的零件？試著描述該算法，想一想還有哪些方法可以解決該問題？2.如果有n個零件（n>10），要找出其中質量較輕的一個，以上方法是否仍然可用？試分析n=10000時，這些算法在問題解決效率上的不同。實踐活動123456789101.兩兩比較，最多5次！實踐活動2.分成兩組，每組5個，較輕的一組拿出4個，分別放在天平兩端，較輕的一組最后比較一次