java - 仅使用 int[ ][ ] 的 Java 汉诺塔(可以做到吗？)

Question

这不是家庭作业，我没有钱上学，所以我在高速公路上的收费站轮类工作时自学(漫长的夜晚，几乎没有顾客)。

我正在尝试用 Java 实现一个简单版本的 Hanoi Towers 求解器。我正在使用堆栈和递归函数，没有咨询外部资源，以便有机会思考自己。

我从一组数组 ( int[][] pegs ) 开始，但在“移动”步骤的实现上卡住了，特别是如何知道我需要从起始位置数组中“选择”哪个“高度”在哪个“高度”我会将光盘放在目标位置数组中。当然有 Stack<Integer>它是为我做这件事的数据结构，我不需要跟踪任何事情。我编写了这个版本，但对放弃感到消极懒惰；我对扩展我的大脑和理解如何用数组来完成这一切很感兴趣。

是否可以使用 int[][] pegs 实现此代码？ ？如何？ (一个提示就足够了，我只是停留在方法上，我可以在确定正确的路径后自己做跑腿)。

顺便说一句，我编写的代码是“合格的”Java 还是我在滥用某些东西？ (我仍然不确定是专注于 Java 还是 C++。我有两者的电子书)。

package exercises;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class HanoiTowers {
  private static final int N_DISCS = 6;
  private static final int N_PEGS = 3;
  private static int nMoves = 0;
  private static final int POSITION_END_PEG = N_PEGS - 1;
  private static final int POSITION_START_PEG = 0;
  public static void main(String[] args) {
    List<Stack<Integer>> pegs = new ArrayList<Stack<Integer>>(N_PEGS);
    for (int i = 0; i < N_PEGS; i++) {
      pegs.add(new Stack<Integer>());
    }
    for (int i = 0; i < N_DISCS; i++) {
      pegs.get(POSITION_START_PEG).push(N_DISCS - i);
    }
    printPegs(pegs);
    moveTowers(pegs, POSITION_START_PEG, POSITION_END_PEG, N_DISCS);
    System.out.println(String.format("# moves: %d", nMoves));
  }
  private static void moveTowers(List<Stack<Integer>> pegs, int fromPeg,
      int toPeg, int ofHeight) {
    if (ofHeight <= 0) {
      return;
    }
    int throughPeg = N_PEGS - fromPeg - toPeg; // Kind of a hack?
    moveTowers(pegs, fromPeg, throughPeg, ofHeight - 1);
    pegs.get(toPeg).push(pegs.get(fromPeg).pop());
    nMoves++;
    printPegs(pegs);
    moveTowers(pegs, throughPeg, toPeg, ofHeight - 1);
  }
  private static void printPegs(List<Stack<Integer>> stacks) {
    for (int j = N_DISCS - 1; j >= 0; j--) {
      for (int i = 0; i < N_PEGS; i++) {
        Stack<Integer> stack = stacks.get(i);
        int disc = stack.size() < j + 1 ? 0 : stack.get(j);
        System.out.print(String.format("[%d]", disc));
      }
      System.out.println();
    }
    System.out.println();
  }
}

Answer 1

我能想到的使用简单数组的最佳方法是将它们视为钉子，给它们一个等于你拥有的圆盘数量的长度，然后，当你使用整数时，使每个的值位置等于圆盘的大小，然后要移动它们，您需要从上到下扫描整个钉子(顶部和底部由您决定)，当您找到第一个时，将其移动到下一个 Hook ，这还包括扫描接收 Hook 以寻找合适的位置。

如果你想避免对钉子的扫描，你可以使用额外的变量，将最新知道的占用或空闲位置存储在相应的钉子中。

此外，最好的方法是使用列表而不是简单的数组，但这可能是另一项练习。