透過您的圖書館登入
IP:18.217.12.218
  • 學位論文

硬幣移動問題的計算複雜度

On the Complexity of the Linear Sliding-Coin Puzzle

指導教授 : 蔡錫鈞

摘要


硬幣移動問題的初始盤面是一列硬幣,有 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.

並列關鍵字

Sliding-Coin Puzzle

參考文獻


Dover Publications, 1954.
[4] Erik D. Demaine, Martin L. Demaine, and Helena A. Verrill, “Coin-Moving Puzzles,”
[5] C.-C. Chu, M.-Y. Lee, and C.-S. Tsai, “Sliding-Coin Puzzle,” Unpublished manuscript
[6] Erik D. Demaine, and Martin L. Demaine, “Puzzles, Art, and Magic with Algorithms,”
“Moving Coins”, Computational Geometry, volume 34, issue 1, pages 35–48, 2006.

延伸閱讀