臺灣國際科展

旋轉方塊路橋問題之探討

科展類別
臺灣國際科展作品
屆次
2019年
科別
數學
得獎情形
四等獎
學校名稱
臺北市立第一女子高級中學
指導老師
廖培凱
作者
蔣馨慧
關鍵字
卡特蘭數,遞迴關係,生成函數

摘要或動機

本研究為一迷宮遊戲和旋轉方塊所組合成的問題。在給定行列數的可旋轉方塊上,置入「路」和「橋」,指定起點,並透過方塊的旋轉改變路徑,探討所有可能到達的終點以及抵達各終點的最短路線數。 此研究中,首先透過問題簡化和圖形討論,發現旋轉方塊以迴圈和無法繞行的路線(構造S)交錯形成,得到所有可能的終點位置。接著,整理所有簡化圖形的規律,利用加法原理推算出最短路線數。透過找出圖形對稱特性,得到不同終點之最短路徑數的關係。而後將不同規格的旋轉方塊的最短路線數關係,以遞迴關係式表示,並且找出其生成函數,希望透過生成函數得到最短路徑數的一般式。研究時,我們不僅發現不同規格之最短路線數生成函數的關係,從而能探討每一規格的最短路線數。更進一步發現無論方塊行數取至極限時或方塊行列數相同時,其最短路徑數的數列與卡特蘭數列(the Catalan numbers)有關。


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

檔案名稱 檔案大小 格式
旋轉方塊路橋問題之探討 1 MB Adobe Reader(Pdf)檔案