資源簡介

中小學教育資源及組卷應用平臺
第2課《最短路徑的算法》教學設計
課題 最短路徑的算法 單元 第七單元 學科 信息科技 年級 五年級下
核心素養目標 信息意識：理解生活中常見問題如何通過算法解決，能把地圖轉成數據表，嘗試用數據去描述一個城市的道路網絡。計算思維：學習迪杰斯特拉算法，理解它的步驟，提升解決問題的能力，親自動手解決從一個地方到另一個地方的最短路徑問題。數字化學習與創新：編寫程序的過程中，提升數字化技能，探索算法應用的創新可能性，編程完成后，思考其他可以應用這個算法的領域。信息社會責任：學會在使用算法和處理數據時，考慮到社會責任和道德問題， 探討算法的社會影響，思考怎樣讓技術更好地服務于社會。
教學重點 1、學會用數據表格表示路線圖。2、了解迪杰斯特拉算法的實現過程。
教學難點 1、掌握迪杰斯特拉算法的程序實現。
教學過程
教學環節 教師活動 學生活動 設計意圖
導入新課 板書課題。活動背景在路線相對簡單的情況下，用窮舉法來尋找最短路徑是可行的方法。但如果要在復雜路線中尋找最短路徑，還需要更有效的方法和計算機的幫助。活動目標1、學會用數據表格表示路線圖。2、了解迪杰斯特拉算法的實現過程。3、體驗迪杰斯特拉算法的程序實現。觀看教學視頻《最短路徑查找—Dijkstra算法》。 學習新知引入，觀看教學視頻。 用提問的方式引入課題，增強課堂互動性。將學生的注意吸引到課堂。
講授新課 新知講解：一、用數據表格表示路線圖計算機無法像人一樣直接讀懂圖，為了處理圖的相關問題，需要先將圖轉化為數據表。如左圖所示的路線模型圖，可以轉換為如右圖所示的數據表。由于不考慮方向的因素，觀察表格中的數據可以發現，AB與BA之間路線的距離相同,以此類推。所以,表格中黃色部分的數據與藍色部分對稱。數據可以進一步簡化為。二、迪杰斯特拉算法要幫助快遞員尋找配送快遞的最短路徑，可以采用迪杰斯特拉算法(Diikstra)，計算從A點出發，到B、C、D、E各地點配送快遞的最短路徑，具體步驟描述如下。1、設置初始狀態。設計兩個方框，分別保存已找到的最短路徑和當前發現的路線。從起點A開始，將與起點A相關的路線放入橙框。2、尋找第一條最短路徑。（1）對橙框里的路線排序。（2）將最短的路線移入藍框。（3）找到第一條最短路徑。3、尋找第二條最短路徑步驟。步驟1：重新計算路徑長度。計算起點A通過已知最短路徑“AC=3”到達其他點的長度。步驟2：比較新路徑與原路徑，用更短的新路徑代替原路徑。步驟3：將橙框中的最短路徑移到藍框中。選出第二條最短路徑。步驟4：按照同樣的方法，繼續尋找其余最短路徑，直到橙框里的路徑為空。探究實踐從起點A到目的點D的最短路徑是A→C→E→D，長度為13。觀察并驗證這個結論。用迪杰斯特拉算法尋找最短路徑的過程可以概括為。探究實踐嘗試求解下圖中從A點到其余各點的最短路徑。三、迪杰斯特拉算法的程序實現人工推算最短路徑的方法效率低，易出錯。通過計算機編程實現算法可以快速運算出結果，極大地提高效率，解決更復雜的路徑查找問題。探究實踐使用計算軟件尋找最短路徑。步驟1：將路線圖用數據表格表示。步驟2：將數據輸入計算機，計算最短路徑。步驟3：在路線圖上驗證答案。四、課堂練習。完成PPT22頁到24頁練習題。五、拓展延伸1、常見最短路徑算法除了迪杰斯特拉算法之外，還有很多類似的最短路徑算法，如:弗洛伊德算法、貝爾曼-福特算法(Bellman-Ford)和 SPFA 算法等。這些算法各有特點，可滿足不同的需要。在現實生活中，最短路徑算法的應用非常廣泛，比如手機導航、城市道路規劃和網絡通信等。2、生活中的導航小助手手機地圖如何幫你找到最近的路？它其實用了類似迪杰斯特拉的算法，實時計算道路距離和擁堵情況，像一位隱形向導幫你規劃最優路線！3、迷宮游戲的秘密路徑玩迷宮時如何快速找到出口？試試“貼墻法”或“最短步數法”，這和計算機尋找最短路徑的思路很像，都是通過不斷嘗試和排除錯誤選項。4、快遞小哥的智慧派送快遞公司如何安排送貨順序？他們用算法計算最短路線，減少時間和油耗，下次收到快遞時，可以想想背后的“數學魔法”哦！5、算法背后的科學家故事迪杰斯特拉算法的發明者艾茲赫爾·戴克斯特拉（Edsger Dijkstra）是一位荷蘭計算機科學家，他最初設計這個算法是為了解決鐵路網絡的優化問題。 了解用數據表格表示路線圖。學習迪杰斯特拉算法。掌握迪杰斯特拉算法的程序實現的方法。完成課堂練習。進行課外知識拓展。 引導學生理解生活中常見問題如何通過算法解決，能把地圖轉成數據表。學習迪杰斯特拉算法，理解它的步驟，提升解決問題的能力。通過實踐操作，提升學生的數字化技能，探索算法應用的創新可能性。在課堂練習中強化所學知識內容。拓寬學生知識面。
課堂小結 最短路徑的算法1、進行新知引入2、用數據表格表示路線圖3、迪杰斯特拉算法4、迪杰斯特拉算法的程序實現5、進行知識拓展 總結回顧 對本節課內容進行總結概括。
課后作業 1、如果兩點間用一個很大的數來表示路線長度，說明表示道路封閉或不可通行。2、上網查找資料，了解用弗洛伊德算法(Floyd)求解最短路徑的基本過程。 布置作業 拓展學生的學習能力
課堂板書 觀看板書 強調教學重點內容。
21世紀教育網 www.21cnjy.com 精品試卷·第 2 頁 （共 2 頁）
HYPERLINK "http://www.21cnjy.com/" 21世紀教育網(www.21cnjy.com)

展開更多......

收起↑