0

私はハノイの塔問題の変種を解こうとしています.3つのペグがあり、同じ高さとディスクサイズの2つの塔があります. タスクは、2 つのタワーを交換することです。

私の解決策は、両方のタワーを積み重ねて大きなタワーにし（同じサイズのディスクを積み重ねることができます）、それらを再び分割します（もちろん、ペグを切り替えます）。

両方のタワーを積み重ねることはできましたが、アルゴリズムを逆にしてそれらを再び分割することはできません。

この状況では、それぞれ 3 つのディスクを持つ 2 つのタワーがあります。左側に 1 つ、中央に 1 つ。私のアルゴリズムの後、右側のペグに 6 つのディスクを備えた 1 つのタワーがあります。

私のアルゴリズムは次のとおりです:(私はJavaを使用しています)

public void solve() {
    combineTo(3, 0, 1, 2); // parameters: (height, from, to, temp)
    splitUp(?, ?, ?, ?);
}

private void moveDisk(int from, int to){
    // here are also a few other things going on but 
    // that doesn't matter in this case
    System.out.println("from: "+from+" - to: "+to);
}

private void moveTower( int i, int from, int to, int temp) {
    if (i == 0) return;
    else{
        moveTower( i-1, from, temp, to );
        moveDisk(from, to);
        moveDisk(from, to);
        moveTower( i-1, temp, to, from );
    }
}

private void combineTo( int i, int from, int to, int temp ){
    if (i==0) return;
    else{
        combineTo(i-1, from, to, temp);
        moveDisk(to, from);
        moveTower(i-1, temp, to, from);
        moveDisk(from, temp);
        moveDisk(from, temp);
        moveTower(i-1, to, temp, from);
    }
}

private void splitUp( int i, int from, int to, int temp ){
    if (i==0) return;
    else{
        ???
    }
}

splitUpでは、メソッドでこれを元に戻すにはどうすればよいですか?

4

2 に答える 2

1

あなたは難しい部分を持っています！デッキの一番下からカードを配ることを考えてみてください。それらが 1 つのスタックに結合されたら、一番下のディスクが必要な場所にスタック全体を移動するだけです。次に、スタック全体から一番下の要素を引いたものを、一番下から 2 番目のディスクが必要な場所に移動します。もっと賢い方法があるかもしれませんが、これは確かにうまくいきます。

(スタックを解除する方法としては、スタックとは逆に、一度に 2 枚ずつ処理することでスタックを解除することもできます。これは少し効率的かもしれません。)

これは、単純なテキスト グラフィックを使用した C バージョンです。単一のスタックを構築するのに少し異なる方法を使用したことに注意してください。あなたのものは、全体の移動でもう少し効率的です。ポジティブ ラベルの付いたディスクをネガティブと交換します。

#include <stdio.h>

// Three pegs with various numbers of integer-labeled disks.
struct peg {
  int disks[30];
  int n_disks;
} pegs[3];

// Set up positive-labeled disks on peg 0 and negative ones on peg 1.
void init(int n_disks)
{
  for (int i = 0; i < n_disks; ++i) {
    pegs[0].disks[i] = n_disks - i;
    pegs[1].disks[i] = -(n_disks - i);
  }
  pegs[0].n_disks = pegs[1].n_disks = n_disks;
}

// Draw simple text graphic of pegs.
void show(void)
{
  printf("|\n");
  for (int i = 0; i < 3; i++) {
    printf("|");
    for (int j = 0; j < pegs[i].n_disks; j++)
      printf("|%2d|", pegs[i].disks[j]);
    printf("\n|\n");
  }
  printf("\n");
}

// Move one disk and draw the pegs.
void move_1(int a, int b)
{
  struct peg *peg_a = &pegs[a], *peg_b = &pegs[b];
  int disk = peg_a->disks[--peg_a->n_disks];
  peg_b->disks[peg_b->n_disks++] = disk;
  //printf("move disk %d from peg %c to peg %c\n", disk, 'A' + a, 'A' + b);
  show();
}

// Move top n disks of tower at from to to using tmp as storage.
void move(int n, int from, int to, int tmp)
{
  if (n == 0) return;
  move(n - 1, from, tmp, to);
  move_1(from, to);
  move(n - 1, tmp, to, from);
}

// Stack the towers 0 and 1 of height n into a single tower on 2.
void stack(int n)
{
  if (n == 0) 
    return;
  // Extra base case skips a couple of redundant moves.
  if (n == 1) {
    move_1(0, 2);
    move_1(1, 2);
    return;
  }
  stack(n - 1);
  move_1(0, 1);
  move(2 * (n - 1), 2, 0, 1);
  move_1(1, 2);
  move_1(1, 2);
  move(2 * (n - 1), 0, 2, 1);
}

// Swap contents of pegs 0 and 1 using 2 as temp storage.
void swap(void)
{
  stack(pegs[0].n_disks);
  int n = pegs[2].n_disks;
  move(n, 2, 1, 0);
  while (n > 0) {
    move(--n, 1, 0, 2);
    move(--n, 0, 1, 2);
  }
}

int main(void)
{
  int n = 3;
  init(n);
  show();
  swap();
  return 0;
}
于 2014-01-30T04:09:39.677 に答える