浙教版（2023）五上第13課 算法的設(shè)計(jì) 課件

第13課算法的設(shè)計(jì)學(xué)習(xí)內(nèi)容1.簡(jiǎn)易最短路徑算法的設(shè)計(jì)。2.了解算法設(shè)計(jì)的一般過程。研討在對(duì)問題進(jìn)行分解、抽象、建模后，可以設(shè)計(jì)出問題的具體解決方法，并以此形成算法。學(xué)校新到一批教材，需要從倉(cāng)庫(kù)運(yùn)送到信息科技教室，準(zhǔn)備讓送貨機(jī)器人來幫忙完成送貨。為了提高運(yùn)送效率，需要設(shè)計(jì)機(jī)器人送貨最短路徑的算法，你會(huì)怎樣設(shè)計(jì)呢？研討一、問題描述與分解問題描述：從所有可能的路線中，找出一條把教材從倉(cāng)庫(kù)運(yùn)送到信息科技教室總長(zhǎng)度最短的路徑。規(guī)模分解：把全路程規(guī)劃分解成，從起點(diǎn)倉(cāng)庫(kù)到必經(jīng)點(diǎn)風(fēng)雨連廊，再到到信息科技教室兩段路線各自最短路徑的規(guī)劃，最后可以合并兩條最短路徑。步驟分解：第一步找出從倉(cāng)庫(kù)到風(fēng)雨連廊共有幾條路徑，第二步計(jì)算出每條路徑的路程長(zhǎng)度，第三步比較每條路徑的長(zhǎng)度，第四步選擇最短的路徑。二、抽象與建模抽象：（1）把每一個(gè)經(jīng)過點(diǎn)抽象成地圖上的一個(gè)個(gè)節(jié)點(diǎn)。（2）把節(jié)點(diǎn)之間彎曲的路抽象成線段。（3）把節(jié)點(diǎn)之間的路程抽象成具體數(shù)據(jù)。二、抽象與建模建模：對(duì)分解后的兩段路徑分別求解，每種路徑的長(zhǎng)度為各段分路程之和。數(shù)學(xué)關(guān)系模型為：總路程=各段分路程之和。例如，從倉(cāng)庫(kù)到風(fēng)雨連廊有2種路徑，分別是S1=L1+L3，S2=L2+L4。想一想利用這個(gè)數(shù)學(xué)關(guān)系模型分別計(jì)算，從倉(cāng)庫(kù)到風(fēng)雨連廊，再到信息科技教室這兩段所有路徑的長(zhǎng)度。二、算法設(shè)計(jì)和描述自動(dòng)送貨機(jī)器人最短路徑算法描述：先考慮規(guī)模分解后的從倉(cāng)庫(kù)到風(fēng)雨連廊之間的路徑，找出所有可能的路徑，計(jì)算它們的長(zhǎng)度，比較后找出長(zhǎng)度最短的路徑，按最短路徑執(zhí)行操作。步驟1：找出第一條路徑S1。步驟2：找出第二條路徑S2。步驟3：計(jì)算S1的總長(zhǎng)度。步驟4：計(jì)算S2的總長(zhǎng)度。步驟5：比較兩條路徑的長(zhǎng)度，選擇長(zhǎng)度較短的那條路徑。輸入：L1，L2，L3，L4。

輸出：最短路徑。二、算法設(shè)計(jì)和描述練一練根據(jù)抽象后的圖例數(shù)據(jù)，你能找出