標題: 硬幣移動問題的計算複雜度
On the Complexity of the Linear Sliding-Coin Puzzle
作者: 林庭宇
Lin, Ting-Yu
蔡錫鈞
Tsai, Shi-Chun
資訊科學與工程研究所
關鍵字: 硬幣移動問題;Sliding-Coin Puzzle
公開日期: 2009
摘要: 硬幣移動問題的初始盤面是一列硬幣,有 n 個五分錢硬幣接連排著 n 個一分錢硬幣。玩家必須重新排序這列硬幣,讓五分錢的硬幣和一分錢的硬幣交錯排列。每一回合,玩家可以把 k 個相鄰的硬幣移動到新的位置。在移動過程中,這 k 個硬幣的相對順序不能調動。 我們證明至少需要 n 回合,才能解決此問題,更針對參數為 k=2 和 k=3 的問題,設計了能產生最佳移法的演算法。此外,我們提出一套建構最佳解答的辦法,並成功套用於參數為 k=4 和 k=5 的問題。
Consider a line of n nickels and n pennies with all nickels arranged to the left of all pennies, where n >= 3. The puzzle asks the player to rearrange the coins such that nickels and pennies alternate in the line. In each move, the player is allowed to slide k >= 2 adjacent coins to a new position without rotating. We prove that it takes at least n moves to solve the puzzle, and present algorithms to generate the optimal solutions for k = 2 and k = 3. We also propose a framework to extend solutions, and apply it successfully to construct optimal solutions for k = 4 and k = 5.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079755502
http://hdl.handle.net/11536/45849
顯示於類別:畢業論文


文件中的檔案:

  1. 550203.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。