algorithm - 将 1 块插入不完美的河内塔的算法

Question

我正在为我的机器人手臂做一个程序来建造河内塔。我让算法在一个站立的塔上工作（仅使用 3 个位置将塔更换到不同的地方）。

位置： A、B、C
件数： 5

我想逐步建立塔（我将在位置 C 上放置一块，手臂将一块放在位置 A 上/进入塔中）。如果当前部分位于顶部，则代码正在工作。

问题：是否有（递归）算法仅使用 3 个位置（A 是当前的塔，C 是新的棋子，B 是空的）将棋子放入塔中？

编辑：我不是想在不同的地方建造塔楼。我要求一种算法，可以将 C 上的一块放入 A 上的塔中（假设塔是 5-3-2-1，我将最后的“4”块放在 C 上。算法应该将它放入使其成为 5-4-3-2-1 的正确位置）。

标签： algorithmlogictowers-of-hanoi

Answer 1

您已经“......让算法在站立的塔上工作（仅使用 3 个位置将塔更换到不同的地方）......”，因此请执行以下操作：

1. 确定堆栈 A 中有多少块小于堆栈 C 中的块。将此数字称为k。它可能是零，在这种情况下，您可以通过一次操作将块从堆栈 C 移动到堆栈 A。如果不：

2. 完全忽略堆栈 A 中位于顶部k件以下的件。执行此步骤和以下步骤，就好像它们不存在一样。现在使用您现有的算法（将堆栈完全移动到另一个位置），将顶部k元素从堆栈 A 移动到位置 B。我们忽略的部分不参与此移动。

3. 然后将棋子从堆栈 C 移到堆栈 A。现在在下一步中也忽略此棋子。所以我们现在可以假设堆栈 A 是空的。

4. 再次使用您的算法将堆栈 B 移动到位置 A。同样，我们忽略已经在位置 A 的部分：它们在此步骤中不会移动。