algorithm - 这是如何运作的？河内奇怪的塔解决方案

当我发现this到河内塔楼的一种不同寻常的迭代解决方案时，我迷失在互联网上: for (int x = 1; x < (1 << nDisks); x++){ FromPole = (x & x-1) % 3; ToPole = ((x | x-1) + 1) % 3; moveDisk(FromPole, ToPole);} This post在答案之一中也具有类似的Delphi代码。但是，对于我的一生来说，我似乎无法找到一个很好的解释为什么这样做有效。谁能帮助我理解它？ 最佳答案 河内塔楼的递归解决方案可以使您将N个磁盘从钉A移到C，首先将N-1从A移到B，然后将底部的N-1移到C，然后再移N-从B到C 1个磁盘。本质上，hanoi(from, to, spare, N): hanoi(from, spare, to, N-1) moveDisk(from, to) hanoi(spare, to, from, N-1)显然，hanoi(_，_，_，1)采取了一个 Action ，而hanoi(_，_，_，k)采取了与2 * hanoi(_，_，_，k-1)+ 1一样多的 Action 。解决方案长度按顺序1、3、7、15，...增长。这与(1 如果您自己查看解决方案，则对于N = 1，您将获得FROM TO ; hanoi(0, 2, 1, 1) 0 2 movedisk对于N = 2，您得到FROM TO ; hanoi(0, 2, 1, 2) ; hanoi(0, 1, 2, 1) 0 1 ; movedisk 0 2 ; movedisk ; hanoi(1, 2, 0, 1) 1 2 ; movedisk对于N = 3，您得到FROM TO ; hanoi(0, 2, 1, 3) ; hanoi(0, 1, 2, 2) ; hanoi(0, 2, 1, 1) 0 2 ; movedisk 0 1 ; movedisk ; hanoi(2, 1, 0, 1) 2 1 ; movedisk 0 2 ; movedisk *** ; hanoi(1, 2, 0, 2) ; hanoi(1, 0, 2, 1) 1 0 ; movedisk 1 2 ; movedisk ; hanoi(0, 2, 1, 1) 0 2 ; movedisk由于该解决方案具有递归性质，因此FROM和TO列遵循递归逻辑:如果您在列上使用中间条目，则上方和下方的部分是彼此的副本，但数字互不相同。这是算法本身的明显结果，该算法不对桩号执行任何算术运算，而仅对它们进行置换。在N = 4的情况下，中间行位于x = 4(上面标有三颗星)。现在表达式(X＆(X-1))取消设置了X的最小置位，因此它映射了数字从1到7，如下所示: 1 -> 0 2 -> 0 3 -> 2 4 -> 0 (***) 5 -> 4 % 3 = 1 6 -> 4 % 3 = 1 7 -> 6 % 3 = 0诀窍在于，由于中间行始终精确地为2的幂，因此恰好设置了一位，所以当您将中间行值(本例中为4)添加到中间行之后，中间行之后的部分等于之前的那一部分。行(即4 = 0 + 4、6 = 2 + 6)。这实现了“copy”属性，中间行的添加实现了置换部分。表达式(X |(X-1))+1设置了最低的零位，该位右边有一个零，并将这些零清除，因此它具有与预期相似的属性: 1 -> 2 2 -> 4 % 3 = 1 3 -> 4 % 3 = 1 4 -> 8 (***) % 3 = 2 5 -> 6 % 3 = 0 6 -> 8 % 3 = 2 7 -> 8 % 3 = 2至于为什么这些序列实际上产生正确的桩号，让我们考虑一下FROM列。递归解决方案以hanoi(0，2，1，N)开头，因此在中间行(2 **(N-1))您必须具有movedisk(0，2)。现在，根据递归规则，在(2 **(N-2))处，您需要具有movedisk(0，1)和(2 **(N-1))+ 2 **(N-2)个移动磁盘( 1、2)。这将为from钉创建“0,0,1”模式，该模式在上表中以不同排列可见(对于0,0,1，请检查第2、4和6行，对于0,0，请检查第1、2、3行) ，2，以及第1,1,0行的第5、6、7行，都是同一模式的所有置换版本)。现在，在所有具有此特性的函数中，它们以2的幂为单位创建自己的副本，但具有偏移量，因此作者选择了能够对正确的排列模3的那些。这不是一个艰巨的任务，因为三个整数0..2只有6个可能的排列，并且排列在算法中以逻辑顺序进行。 (X |(X-1))+ 1不一定与河内问题有很深的联系，也不一定是；它具有复制属性，并且恰好能够以正确的顺序产生正确的排列就足够了。