臺灣國際科展

替機器人安排作業程序

科展類別
臺灣國際科展
屆次
2007年
科別
數學科
學校名稱
臺北市立建國高級中學
指導老師
黃大原、陳嘯虎
作者
洪錫成、李重毅
關鍵字
機器人 作業程序

摘要或動機

編號1~mn 的mn 個物件已隨機置入m× n 階的矩陣中,另外有一行m 個空格的暫存區供物件暫存用。我們探討將這mn 個物件移至目標區並按照1,2,…, mn 的次序排列,所需的移動步數;每一步的移動中,只能移動每一行最頂層的物件到其他行(含暫存區)的最頂層或目標區。在這篇報告中,我們給出了一個適用於n ? m ?1時的移動方法,此方法在一般的情形下,所需的移動次數未必是最少;但是在最不利於移動的情形下,我們證明此方法所需的移動步數為最少。There are mn objects, numbered from 1 to mn, put on an m× n matrix randomly, and there is another column with m blank spaces for temporary storage purpose during moving. In each step of moving, we can only move the top object from one column to the top of another column or to the target pile. The total steps needed to move these mn objects to the target pile in increasing order from the bottom to the top is studied in this article. A general method for solving this problem when n ? m ?1 is given, and we prove that it provides an optimal solution in the worst cases. However, it may not always provide the minimal steps in all cases.


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

檔案名稱 檔案大小 格式
替機器人安排作業程序 326 KB Adobe Reader(Pdf)檔案