全國中小學科展

大馬小馬走天下

科展類別

全國中小學科展作品

屆次

第63屆--民國112年

科別

數學科

得獎情形

第三名

學校名稱

桃園市立青埔國民中學

指導老師

汪政緯

作者

紀言蓁;陳法敦;陳秉政

關鍵字

騎士巡邏、馬步、漢米爾頓

摘要或動機

有個經典的騎士巡邏問題 : 騎士用馬步移動,每個格子至多走一次,試圖找出最多步。我們定義2x3的矩形方格圖中走對角線為大馬步,2x2的方格中走對角線為小馬步。依照大馬步、小馬步輪流交錯走,我們發現 : 若指定特殊起始點,在(偶數m) x (偶數n)的矩形中可以走完所有的格子。若騎士能將格子走完,本質上非常類似漢米爾頓路徑。其它無交錯的走法(如連續大馬步或連續小馬步),我們也找出最多步的一般式。本作品的價值在於擴充馬步為大馬步與小馬步,推廣正方形為任意比例的矩形,並用深度優先搜索(Depth First Search,以下簡稱DFS)驗証結果。關鍵論証在於著色法與DFS ,若騎士無法走完,著色法能証明步數的最大值,DFS能讀完圖中所有資訊。結論的一般式紀錄於後。

030407.pdf

Adobe Reader(Pdf)檔案