algorithm - 河内配置在一定的举动

Question

我想知道在 towers of Hanoi 中的给定移动中每个 Hook 上有多少个圆盘谜。例如，给定 n = 3 磁盘，我们有这个配置序列来优化解决这个难题:

   0 1 2
0. 3 0 0
1. 2 0 1 (move 0 -> 2)
2. 1 1 1 (move 0 -> 1)
3. 1 2 0 (move 2 -> 1)
4. 0 2 1 (move 0 -> 2)
5. 1 1 1 (move 1 -> 0)
6. 1 0 2 (move 1 -> 2)
7. 0 0 3 (move 0 -> 2)

给定第 5 步，我想返回 1 1 1，给定第 6 步，我想要 1 0 2 等

这可以通过使用经典算法并在一定数量的移动后停止它来轻松完成，但我想要更高效的东西。我上面链接的维基百科页面在 Binary solutions 部分给出了一个算法。然而我认为这是错误的。我也不明白他们是如何计算n的。

如果您按照他们的示例并将其返回的磁盘位置转换为我想要的，它会为 n = 8 磁盘和移动编号 提供 4 0 4 216。然而，使用经典算法，我得到 4 2 2。

还有一个用C语言实现的高效算法here这也给出了 4 2 2 作为答案，但它缺少文档而且我无法访问它所基于的论文。

上一个链接中的算法似乎是正确的，但谁能解释一下它究竟是如何工作的？

一些我也感兴趣的相关问题:

1. 是维基百科算法真的错了，还是我遗漏了什么？他们如何计算 n？
2. 我只想知道在某个移动中每个挂钉上有多少个圆盘，而不是每个圆盘在哪个挂钉上，这似乎是文献更关心的。有没有更简单的方法来解决我的问题？

Answer 1

1) 如果您的算法说 Wikipedia 已损坏，我猜您是对的...

2)至于计算每个 Hook 中的磁盘数量，对其进行递归算法是否非常简单:

(未经测试、不优雅且可能充满 +-1 错误的代码如下:)

function hanoi(n, nsteps, begin, middle, end, nb, nm, ne)
    // n = number of disks to mive from begin to end
    // nsteps = number of steps to move
    // begin, middle, end = index of the pegs
    // nb, nm, ne = number of disks currently in each of the pegs

    if(nsteps = 0) return (begin, middle, end, nb, nm, ne)

    //else:

    //hanoi goes like
    // a) h(n-1, begin, end, middle) | 2^(n-1) steps
    // b) move 1 from begin -> end   | 1 step
    // c) h(n-1, middle, begin, end) | 2^(n-1) steps
    // Since we know how the pile will look like after a), b) and c)
    // we can skip those steps if nsteps is large...

    if(nsteps <= 2^(n-1)){
        return hanoi(n-1, nsteps, begin, end, middle, nb, ne, nm):
    }
    nb -= n;
    nm += (n-1);
    ne += 1;
    nsteps -= (2^(n-1) + 1);
    //we are now between b) and c)

    return hanoi((n-1), nsteps, middle, begin, end, nm, nb, ne);

function(h, n, nsteps)
    return hanoi(n, nsteps, 1, 2, 3, n, 0, 0)

如果你想要效率，它应该尝试将其转换为迭代形式(应该不难 - 你不需要维护堆栈)并找到一种更好地表示程序状态的方法，而不是随意使用 6 个以上的变量。