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

2.2算法的概念及描述年級(jí)：高一

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

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

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

一個(gè)算法一般要求有0個(gè)或多個(gè)輸入,以描述運(yùn)算對(duì)象的初始情況。

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

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

開始/結(jié)束框表示算法的開始或結(jié)束

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

處理框框中指出要處理的內(nèi)容，此框有1個(gè)入口和1個(gè)出口流程圖流程圖符號(hào)名稱功能

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

流程線用于控制流程方向

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

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

順序結(jié)構(gòu)AB

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

AB條件TrueFalse選擇結(jié)構(gòu)

當(dāng)條件成立時(shí)，反復(fù)執(zhí)行處理A，一旦條件不成立就立即結(jié)束循環(huán)。

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

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

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

已知有10個(gè)一模一樣的零件，其中9個(gè)零件的質(zhì)量相同，只有1個(gè)質(zhì)量略輕，不符合規(guī)格要求?，F(xiàn)在有一臺(tái)天平，請(qǐng)?jiān)O(shè)計(jì)算法找出該零件。

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