用给定的安排解决河内塔

Question

我得到了有效的河内塔排列。排列以数组形式给出。

例如[2,2,0]：数组的索引是磁盘的标识，从小到大排序，数组的值是对应磁盘的位置（位置总是0、1 或 2）。在[2,2,0]的情况下，最小的两个圆盘在第三极，而最大的圆盘在第一极：

      |           |           |
      |           |          [0]
   [22222]        |         [111] 
  ----+----   ----+----   ----+----

另一个例子：[0,2,1]

      |           |           |
      |           |           |
     [0]       [22222]      [111] 
  ----+----   ----+----   ----+----

将所有圆盘移动到目标极点（第二极点）所需的剩余步骤是否可以递归求解？

public int solveForSteps(int[] disks){
    // Is there a possible way to solve with given arrangements?
}

Answer 1

我没有适合你的递归解决方案。当您查看汉诺塔的常用递归算法时，实际状态可能发生在递归树的深处，如果您想象这样的状态被传递给您的函数，那么从该状态进一步解决问题不需要只是一个递归调用，还要重建"outer"个递归调用的栈。这似乎使它变得相当复杂。

但是你可以迭代地做。这是一种方法：

static void solveForSteps(int[] disks) {
    int n = disks.length;
    // Calculate the next target rod for each of the disks
    int target = 2; // The biggest disk should go to the rightmost rod
    int[] targets = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        targets[i] = target;
        if (disks[i] != target) {
            // To allow for this move, the smaller disk needs to get out of the way
            target = 3 - target - disks[i];
        }
    }
    int i = 0;
    while (i < n) { // Not yet solved?
        // Find the disk that should move
        for (i = 0; i < n; i++) {
            if (targets[i] != disks[i]) { // Found it
                target = targets[i]; // This and smaller disks should pile up here 
                System.out.format("move disk %d from rod %d to %d.\n", i, disks[i], target);
                disks[i] = target; // Make move
                // Update the next targets of the smaller disks
                for (int j = i - 1; j >= 0; j--) {
                    targets[j] = target;
                    target = 3 - target - disks[j];
                }
                break;
            }
        }
    }
}

这将打印将所有磁盘移动到最右边的极点所需的剩余移动。相反，如果您想瞄准中心杆，则只需将 int target = 2 更改为 int target = 1。

Answer 2

要从任意位置解决汉诺塔问题，您可以使用类似于从标准起始位置开始工作的标准解决方案的递归过程。

只是需要更笼统一些。

编写一个递归过程 moveDisks(maxSize,targetPeg) 将所有大小 <= maxSize 的磁盘移动到挂钩 targetPeg，像这样：

找到最大的磁盘 m 使得 m.size <= maxSize 和 m 在 targetPeg 上不是。如果没有这个盘，那么return，因为所有大小<=maxSize的盘都已经在正确的地方了
设 sourcePeg 为当前 m 所在的挂钩，并设 otherPeg 是不是 sourcePeg 或 targetPeg.
递归调用 moveDisks(m.size-1, otherPeg) 以将较小的磁盘移开。
将 m 从 sourcePeg 移动到 targetPeg.
递归调用moveDisks(m.size-1, targetPeg)将较小的磁盘放在它们所属的位置。

在Java中，我会这样写：

/**
 * Solve towers of hanoi from an arbitrary position
 * 
 * @param diskPositions the current peg for each disk (0, 1, or 2) in increasing
 *                      order of size.  This will be modified
 * @param disksToMove  number of smallest disks to moves
 * @param targetPeg target peg for disks to move
 */
static void moveDisks(int[] diskPositions, int disksToMove, int targetPeg)
{
    for (int badDisk = disksToMove-1; badDisk >= 0; --badDisk) {
        int currentPeg = diskPositions[badDisk];
        if (currentPeg != targetPeg) {
            // found the largest disk on the wrong peg

            // sum of the peg numbers is 3, so to find the other one:
            int otherPeg = 3 - targetPeg - currentPeg;

            // before we can move badDisk, we have to get the smaller
            // ones out of the way
            moveDisks(diskPositions, badDisk, otherPeg);

            // Move
            diskPositions[badDisk] = targetPeg;
            System.out.println(
                "Move " + badDisk + " from " + currentPeg + " to " + targetPeg
            );

            //Now we can put the smaller ones in the right place
            moveDisks(diskPositions, badDisk, targetPeg);
            break;
        }
    }
}

...好吧，我在现实生活中不会完全这样写。您实际上可以删除第二次递归调用和中断，因为循环中的其余迭代将完成相同的事情。

用给定的安排解决河内塔

Solving tower of Hanoi with given arrangements

java

algorithm

recursion

towers-of-hanoi