"Hanoi特定问题"

Question

假设有2*n个盘子，如果奇数号盘子在A柱上，偶数号盘子在B柱上，如何解决汉诺塔问题？ 如果需要更多信息，请告诉我。 谢谢。

- Hosi

---

实际上...我们想用这些磁盘做什么？根据这个讨论：http://cboard.cprogramming.com/cplusplus-programming/127768-towers-hanoi-variation.html，它们可能正在被交换？ - MK.

我们正在尝试将位于柱子"C"上的所有盘子移动，而这些盘子被分成了两部分，即"奇数"和"偶数"。奇数在柱子"A"上，偶数在"B"上。假设编号为"1"的盘子是最大的，其后的"2"是次大的，以此类推。 - Hosi

好的，那么我的理解是正确的，你的问题与我上面链接的那个不同。 - MK.

Answer 1

将磁盘1移动到磁盘2上，然后使用经典算法将结果为“正确”的汉诺塔1,2移动到磁盘3上。接着将1,2,3号“正确”的汉诺塔一直移动到4号磁盘上，直到完整的正常汉诺塔形成，然后再使用经典算法移动到目标位置。

编辑1：

示例（不完整）

1   2
3   4
5   6   
.   .   .

    1
    2
3   4
5   6   
.   .   .

    1
    2
    4
5   6   3
.   .   .

    2
1   4   
5   6   3
.   .   .

1   4   2   
5   6   3
.   .   .

        1
    4   2   
5   6   3
.   .   .

        1
4       2   
5   6   3
.   .   .

这很奇怪，因为最后一步有点优化；我描述的会尝试构建1-2-3-4-6，但我们直接跳到构建1-2-3-4-5。这可能意味着什么。

- MK.

---

你介意给一个有6个磁盘的例子吗？1、2、3在“A”上，2、4、6在“B”上。经典算法是O(2^n)，那么这个算法呢？ - Hosi

@IVlad，@Hosi请看我的编辑。复杂度仍应为2^n（不能更糟）。 - MK.

@MK - 你有递归公式吗？你的例子似乎与你所描述的不同。你所描述的应该执行(2^2 - 1) + (2^3 - 1) + (2^4 - 1) + ... + (2^(2n) - 1)步骤。然而在你的例子中，你从未将1 2移动到目标柱和将1 2 3移动到4上，这确实会减少步数，但我不确定你如何递归地形成它。 - IVlad

我的意思是它的确切顺序是什么。正如您所知，经典汉诺塔问题的时间复杂度为：T(n)=2T(n-1)+O(n)，这导致了O(2^n)的时间复杂度。那么对于这个版本的问题呢？！ - Hosi

@HosiпЉМжИСиЃ§дЄЇдљ†е∞ЖдЉЪзІїеК®2^2 + 2^3 + ...+ 2^(n-1) + 2^nпЉМињЩдїНзДґжШѓO(2^n)пЉМеЫ†дЄЇеЃГеП™жШѓ2^(n+1) - 1гАВ - MK.

@IVlad 你说得对。我试图进行优化，却忘记了算法 :) 必须考虑正式化优化。 - MK.