6

这不是家庭作业，我没有钱上学，所以我一边在高速公路上的收费站轮班工作，一边自学（长夜，顾客很少）。

我正在尝试用 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();
  }
}
4

2 回答 2

1

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

如果要避免扫描挂钩，可以使用附加变量，将最新已知的占用或空闲位置存储在相应挂钩中。

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

于 2012-08-20T17:46:58.910 回答
0

我通常的方法不会明确表示挂钩：我只会使用 type 的单个值int[]。每个挂钩只是 1 到 3 之间的一个数字，每个圆盘都位于阵列中的固定位置。例如：

    *****                                
  *********                       *      
 ***********       ***         *******

将表示为{1,1,3,1,2,3}或{3,2,1,3,1,1}，具体取决于您是从最大到最小还是从最小到最大排序。

这种表示的优点：它极大地简化了寻找下一步行动的算法。缺点：它不像大多数人想象的那样接近问题。

使用此表示查找下一步的伪代码，假设圆盘从大到小排列：

nextMove (int[] world, int targetPeg) {
  move = no move
  for(int i = 0; i < world.length; i++) {
    if(world[i] != targetPeg) {
      move = from world[i] to targetPeg
      targetPeg = ∈ {1,2,3} ∖ {world[i],targetPeg}
    }
  }
  return move;
}
于 2014-04-04T09:08:40.470 回答