河内配置在一定的举动

Question

我感兴趣的是在河内拼图塔的特定移动中找到每个挂钩上有多少个磁盘.例如,给定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.

如果你按照他们的例子并转换磁盘位置,它返回到我想要的,它给出4 0 4了n = 8磁盘和移动号码216.然而,使用经典算法,我得到了4 2 2.

还有一个用C语言实现的高效算法这里也给出4 2 2的答案,但它缺乏文档和我没有获得它是基于纸张.

上一个链接中的算法似乎是正确的,但有人可以解释它究竟是如何工作的吗？

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

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

Answer 1

1）如果你的算法说维基百科已损坏，我猜你是对的......

2）至于计算每个钉子中的磁盘数量，为其执行递归算法是否非常简单：

（未经测试、不优雅且可能充满 +-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 + 随意的变量。