6

これは宿題ではありません。学校にお金がないので、高速道路の料金所で交代制勤務をしている間（顧客が少ない長い夜）、自分で教えています。

JavaでHanoiTowersソルバーの単純なバージョンを実装しようとしています。私は自分自身を考える機会を得るために外部ソースに相談することなく、スタックと再帰関数を使用しています。

配列の配列（int[][] pegs）から始めましたが、「移動」ステップの実装、特に開始位置の配列から「選択」する必要がある「高さ」と「高さ」を知る方法に行き詰まりました。ディスクをdestination-position配列にドロップします。もちろん、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

私の通常のアプローチでは、ペグを明示的に表すことはありません。タイプの単一の値を使用するだけ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 に答える