全國中小學科展

棋盤上的飛舞機器人

科展類別
全國中小學科展作品
屆次
第57屆--民國106年
科別
數學科
學校名稱
新北市立中和高級中學
指導老師
劉鴻儒;王晞安
作者
高辰維;凌中謙;魏家豪
關鍵字
圖論,矩陣,時間複雜度

摘要或動機

本研究從圖論的角度探討桌遊「Micro Robots」所引出的相關問題。 第一部分,提出並證明同心圓法、鄰接矩陣元素的加法、鄰接矩陣的乘法,可以計算遊戲地圖中任兩點的最短距離、最短路徑與最短路徑數,分別將三個演算法撰寫Python程式,並比較其功能與時間複雜度。 第二部分,探討遊戲地圖上的參數:兩點平均距離的極值,並引出遊戲地圖設計的問題。 第三部分,探討鄰接矩陣、卡牌矩陣、位置矩陣與地圖的關係,進而提出一套演算法,以處理滿足給定條件地圖之存在性與設計方法,並將演算法撰寫Python程式。


「為配合國家發展委員會「推動ODF-CNS15251為政府為文件標準格式實施計畫」,以及 提供使用者有文書軟體選擇的權利,本館檔案下載部分文件將公布ODF開放文件格式, 免費開源軟體可至LibreOffice 下載安裝使用,或依貴慣用的軟體開啟文件。」

檔案名稱 檔案大小 格式
棋盤上的飛舞機器人 2 MB Adobe Reader(Pdf)檔案