資源簡介

(共15張PPT)
算法的設計
浙教版五年級上冊
第13課 算法的設計
學習內容
1. 簡易最短路徑算法的設計。
2. 了解算法設計的一般過程。
研討
在對問題進行分解、抽象、建模后，可以設計出問題的具體解決方法，并以此形成算法。學校新到一批教材，需要從倉庫運送到信息科技教室，準備讓送貨機器人來幫忙完成送貨。為了提高運送效率，需要設計機器人送貨最短路徑的算法，你會怎樣設計呢？
研討
一、問題描述與分解
問題描述：從所有可能的路線中，找出一條把教材從倉庫運送到信息科技教室總長度最短的路徑。
規模分解：把全路程規劃分解成，從起點倉庫到必經點風雨連廊，再到到信息科技教室兩段路線各自最短路徑的規劃，最后可以合并兩條最短路徑。
步驟分解：第一步找出從倉庫到風雨連廊共有幾條路徑，第二步計算出每條路徑的路程長度，第三步比較每條路徑的長度，第四步選擇最短的路徑。
二、抽象與建模
抽象：
（1）把每一個經過點抽象成地圖上的一個個節點。
（2）把節點之間彎曲的路抽象成線段。
（3）把節點之間的路程抽象成具體數據。
二、抽象與建模
建模：
對分解后的兩段路徑分別求解，每種路徑的長度為各段分路程之和。數學關系模型為：總路程 = 各段分路程之和。
例如，從倉庫到風雨連廊有 2 種路徑，分別是 S1=L1+L3，S2=L2+L4。
想一想
利用這個數學關系模型分別計算，從倉庫到風雨連廊，再到信息科技教室這兩段所有路徑的長度。
二、算法設計和描述
自動送貨機器人最短路徑算法描述：先考慮規模分解后的從倉庫到風雨連廊之間的路徑，找出所有可能的路徑，計算它們的長度，比較后找出長度最短的路徑，按最短路徑執行操作。
步驟 1：找出第一條路徑 S1。
步驟 2：找出第二條路徑 S2。
步驟 3：計算 S1 的總長度。
步驟 4：計算 S2 的總長度。
步驟 5：比較兩條路徑的長度，選擇長度較短的那條路徑。
輸入：L1，L2，L3，L4。 輸出：最短路徑。
二、算法設計和描述
練一練
根據抽象后的圖例數據，你能找出從倉庫到信息科技教室的最短路徑嗎？
謝謝聆聽！
INTERNET OF THINGS
謝謝
21世紀教育網（www.21cnjy.com)
中小學教育資源網站
兼職招聘：
https://www.21cnjy.com/recruitment/home/admin

展開更多......

收起↑