4

我的任务是编写一些代码，找到将给定起始堆栈带到给定目标堆栈的最短移动序列。我得到了一个原始的书籍列表，描述了堆栈是如何开始的，还有一个书籍的目标列表，显示了我需要它们的目标顺序。问题在于标准排序算法不起作用，因为书籍是基于一个人的偏好，而不是任何特定的逻辑。

问题要你使用的系统如下：从书架的任何地方拉出一本书，一次一本书，然后把它放在书架的顶部。所以如果你有书 X、Y 和 Z，你可以选择取出 Y，按 Y、X、Z 的顺序排列。

最初的：

'1984 - George Orwell'
'Moby Dick - Herman Melville'
'To Kill A Mockingbird - Harper Lee'
'Atlas Shrugged - Ayn Rand'
'The Black Cat - Edgar Allen Poe'

目标：

'Atlas Shrugged - Ayn Rand'
'To Kill A Mockingbird - Harper Lee'
'1984 - George Orwell'
'Moby Dick - Herman Melville'
'The Black Cat - Edgar Allen Poe'

这是家庭作业。但是，我并不是在寻找人为我做这件事，因为这会破坏任务的目的。我只是在寻找一些开始的想法或技巧，因为我不知道从哪里开始。

注意：我打算将此标记为作业，但标记明确表示不要，所以我没有。如果这是错误的，请纠正我。

4

2 回答 2

4

好的，主要问题是你只能放在上面，但你可以选择任何书。你想要的是提示，而不是方法，所以这里有一些：

  1. 因为你只能放在顶部，所以总是开始看底部，因为它最难到达
  2. 你显然永远不需要拉任何已经在正确位置的书
  3. 您需要以正确的顺序拉出现在位于书上方的书下的所有书
  4. 如果你把书堆在上面，你应该把它们按正确的顺序放在那里
  5. 要将 ABGFCED 转换为字母顺序，您最好拉 E，然后是 F，然后是 G，如果您总是附加到末尾。

我希望这能让你开始，我没有明确表示。

于 2012-11-09T02:17:32.157 回答
0

一个非常简单的算法是遍历堆栈，每次查找并取出属于底部的下一本书。对于小堆栈，线性搜索就足够了。

在您的示例中，您将退出'The Black Cat - Edgar Allen Poe'第一次迭代、'Moby Dick - Herman Melville'第二次、'1984 - George Orwell'第三次等。

这是一个 O(n^2) 算法。

于 2012-11-09T02:21:03.500 回答