recursion - ハノイの塔: 再帰アルゴリズム

Question

再帰を理解するのにまったく問題はありませんが、ハノイの塔の問題に対する再帰的な解決策に頭を悩ませているようには見えません。ウィキペディアのコードは次のとおりです。

procedure Hanoi(n: integer; source, dest, by: char);
Begin
    if (n=1) then
        writeln('Move the plate from ', source, ' to ', dest)
    else begin
        Hanoi(n-1, source, by, dest);
        writeln('Move the plate from ', source, ' to ', dest);
        Hanoi(n-1, by, dest, source);
    end;
End;

基本的なケースと、単一のディスクを移動できるようになるまで問題をより小さな部分に分割するという概念を理解しています。ただし、非基本ケースの 2 つの再帰呼び出しがどのように連携するのかわかりません。おそらく誰かが私を助けることができますか？ありがとう。

score 48 · Accepted Answer

実際、そのコードを取得したセクションにも説明があります。

ペグ A からペグ C に n 個のディスクを移動するには:

n−1 個のディスクを A から B に移動します。これにより、ディスク #n だけがペグ A に残ります。

ディスク #n を A から C に移動します

n−1 個のディスクを B から C に移動して、ディスク #n に配置する

n番目のディスクにアクセスするには、最初にn − 1 個のディスクを削除する必要があることは明らかです。そして、最初に完全なタワーを表示したい場所以外の別のペグに移動する必要があります.

投稿のコードには、ディスクの数に加えて、3 つの引数があります。ソースペグ、デスティネーションペグ、およびその間にディスクを格納できる一時的なペグ (サイズn − 1 のすべてのディスクが収まる場所)。

再帰は実際には 2 回発生writelnします。の前のものは、宛先ペグを一時ストレージとして使用して、nwriteln − 1 個のディスクを一時ペグに移動します (再帰呼び出しの引数の順序は異なります)。その後、残りのディスクが目的のペグに移動され、その後、2 番目の再帰がタワー全体の移動を強制します。つまり、n − 1 タワーを一時ペグからディスクn の上の目的のペグに移動します。

score 32 · Accepted Answer

1 年前、私は関数型プログラミングのコースを受講し、アルゴリズムのためにこの図を描きました。それが役に立てば幸い！

(0)  _|_         |          |
    __|__        |          |
   ___|___       |          |
  ____|____  ____|____  ____|____

(1.1) |          |          |
    __|__        |          |
   ___|___      _|_         |
  ____|____  ____|____  ____|____ (A -> B)

(1.2) |          |          |
      |          |          |
   ___|___      _|_       __|__
  ____|____  ____|____  ____|____ (A -> C)

(1.3) |          |          |
      |          |         _|_
   ___|___       |        __|__
  ____|____  ____|____  ____|____ (B -> C)



(2.1) |          |          |
      |          |         _|_
      |       ___|___     __|__
  ____|____  ____|____  ____|____ (A -> B)



(3.1) |          |          |
      |          |          |
     _|_      ___|___     __|__
  ____|____  ____|____  ____|____ (C -> A)

(3.2) |          |          |
      |        __|__        |
     _|_      ___|___       |
  ____|____  ____|____  ____|____ (C -> B)

(3.3) |         _|_         |
      |        __|__        |
      |       ___|___       |
  ____|____  ____|____  ____|____ (A -> B)

3 リングの問題は 2 つの 2 リングの問題 (1.x および 3.x) に分割されました。

score 14 · Accepted Answer

http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.htmlに、再帰的なハノイの実装に関する適切な説明があります。

要約すると、下のプレートをスティック A からスティック B に移動する場合、最初にその上にある小さなプレートをすべて A から C に移動する必要があります。2 番目の再帰呼び出しは、移動したプレートを C に移動することです。ベースケースが単一の大きなプレートを A から B に移動した後、B に戻ります。

score 13 · Accepted Answer

これは、最初に見たときにすぐに理解できるものではないことに同意しますが、理解するとかなり単純です。

基本ケース: タワーのサイズは 1 です。したがって、ソースから直接宛先に 1 回の移動で実行できます。

再帰的なケース: タワーのサイズは n > 1 です。したがって、サイズ n-1 の一番上のタワーを追加のペグ (by) に移動し、サイズ 1 の一番下の「タワー」を目的のペグに移動し、一番上のタワーを移動しますから宛先まで。

したがって、単純なケースでは、高さ 2 の塔があります。

 _|_    |     |
__|__   |     |
===== ===== =====

最初のステップ: 2-1 (=1) の一番上のタワーを追加のペグ (真ん中のペグとしましょう) に移動します。

  |     |     |
__|__  _|_    |
===== ===== =====

次へ: 一番下のディスクを移動先に移動します:

  |     |     |
  |    _|_  __|__
===== ===== =====

そして最後に(2-1)=1の一番上の塔を目的地に移動します。

  |     |    _|_
  |     |   __|__
===== ===== =====

考えてみれば、タワーが 3 つ以上だったとしても、タワーを交換するときに再帰を使用するために、常に空の余分なペグ、またはすべての大きなディスクを含むペグが存在します。

score 4 · Accepted Answer

ディスクを A から B を介して C に移動するとします。

小さいディスクを B に移動します。
別のディスクを C に移動します。
BをCに移動します。
AからBに移動します。
C から A にすべて移動します。

上記の手順をすべて繰り返すと、ディスクが転送されます。

score 3 · Accepted Answer

これらの説明をすべて読んだ後、私の教授がハノイの塔の再帰的解法を説明するために使用した方法について検討することにしました。nがリングの数を表し、A、B、C がペグを表すアルゴリズムを次に示します。関数の最初のパラメーターはリングの数、2 番目のパラメーターは元のペグ、3 番目は目的のペグ、4 番目は予備のペグを表します。

procedure Hanoi(n, A, B, C);
  if n == 1
    move ring n from peg A to peg B
  else
    Hanoi(n-1, A, C, B);
    move ring n-1 from A to C
    Hanoi(n-1, C, B, A);
end;

私は大学院で、小さく考えることを決して恥じないように教えられました。それでは、n = 5 の場合のこのアルゴリズムを見てみましょう。最初に自問する質問は、5 番目のリングを A から B に移動したい場合、他の 4 つのリングはどこにあるのかということです。5 番目のリングがペグ A を占めていて、それをペグ B に移動したい場合、残りの 4 つのリングはペグ C にしか配置できません。関数Hanoi (n-1, A, C, B) の上のアルゴリズムではは他の 4 つのリングをペグ C に移動しようとしているため、リング 5 は A から B に移動できます。このアルゴリズムに従って、n = 4 を調べます。リング 4 が A から C に移動する場合、リング3以下？次に、n = 3 の場合、リング 3 が A から B に移動する場合、リング 2 と 1 はどこにありますか? もちろんペグCで。このパターンに従い続けると、再帰アルゴリズムが何をしているかを視覚化できます。このアプローチは、最後のディスクを最初に見て、最初のディスクを最後に見るという点で、初心者のアプローチとは異なります。

score 2 · Accepted Answer

ディスクの直径が整数（4,3,2,1）で表されるスタックと考えてください。最初の再帰呼び出しは3回呼び出されるため、次のようにランタイムスタックがいっぱいになります。

最初の呼び出し：1。2番目の呼び出し：2,1。3番目の呼び出し：3、2、1。

最初の再帰が終了した後、ランタイムスタックの内容は、最大の直径から最小の直径へ（最初から最後へ）中央の極にポップされます。次に、直径4のディスクを移動先に移動します。

2番目の再帰呼び出しは、要素を中央の極から宛先に移動することを除いて、最初の呼び出しと同じです。

score 1 · Accepted Answer

最初の再帰呼び出しは、補助パイルとして dest を使用して、ソースから最大のものを除くすべてのピースを移動します。完了すると、最大のものを除くすべてのピースが横になり、最大のものは無料になります。これで、最大のものを dest に移動し、別の再帰呼び出しを使用して by から dest にすべてのピースを移動できます。

再帰呼び出しは最大のピースについては何も知りません (つまり、無視します) が、再帰呼び出しは小さいピースのみを処理し、最大のピースに自由に移動したり外したりできるため、問題ありません。

score 1 · Accepted Answer

それは簡単です。AからCに移動したいとします

ディスクが 1 つしかない場合は、移動するだけです。

複数のディスクがある場合は、

一番下のディスクを除くすべてのディスク (n-1 ディスク) を A から B に移動します。
一番下のディスクを A から C に移動します
最初のステップの n-1 個のディスクを A から C に移動します

n-1 個のディスクを移動する場合、n 番目はまったく問題にならないことに注意してください (他のすべてのディスクよりも大きい場合)。

n-1 ディスクを移動すると、n-1 = 1 になるまで同じ問題が繰り返されることに注意してください。この場合、最初の if (移動する必要がある場所) になります。

score 1 · Accepted Answer

public static void hanoi(int number, String source, String aux, String dest)
{
    if (number == 1)
    {
        System.out.println(source + " - > "+dest);
    }
    else{
        hanoi(number -1, source, dest, aux);
        hanoi(1, source, aux, dest);
        hanoi(number -1, aux, source, dest);
    }
}

score 1 · Accepted Answer

void TOH(int n, int a, int b){
        /*Assuming a as source stack numbered as 1, b as spare stack numbered as 2 and  c as target stack numbered as 3. So once we know values of a and b, we can determine c as there sum is a constant number (3+2+1=)6.
       */
int c = 6-a-b;
if(n==1){
    cout<<"Move from "<<a<<" to "<<b<<"\n";
}
else{
    // Move n-1 disks from 1st to 2nd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.
    TOH(n-1, a, c);
    // Move the last alone disk from 1st to 3rd stack.
    TOH(1, a, b);
    // Put n-1 disks from 2nd to 3rd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.        
    TOH(n-1, c, b);
}
}
int main() {

TOH(2, 1, 3);
cout<<"FINISHED                        \n";
TOH(3, 1, 3);
cout<<"FINISHED                        \n";
TOH(4, 1, 3);
return 0;
}

score 1 · Accepted Answer

質問に対する答えは、プログラムはどのようにして「src」から「aux」への偶数であり、「src」から「dst」への奇数であることを知っているのかという質問に対する答えは、プログラムにあります。拳の動きを 4 つのディスクで分解すると、次のようになります。

hanoi(4, "src", "aux", "dst");
if (disc > 0) {
    hanoi(3, 'src', 'dst', 'aux');
        if (disc > 0) {
            hanoi(2, 'src', 'aux', 'dst');
                if (disc > 0) {
                    hanoi(1, 'src', 'dst', 'aux');
                        if (disc > 0) {
                            hanoi(0, 'src', 'aux', 'dst');
                                END
                        document.writeln("Move disc" + 1 + "from" + Src + "to" + Aux);
                        hanoi(0, 'aux', 'src', 'dst');
                                END
                        }

また、4 ディスク (偶数) の最初の移動は、Src から Aux に移動します。

score 0 · Accepted Answer

CS の学生として、数学的帰納法について聞いたことがあるかもしれません。ハノイの塔の再帰的な解決策も同様に機能します。唯一の異なる部分は、完全な塔が最終的に終了した場合と同様に、B と C で実際に失われないことです。

score 0 · Accepted Answer

簡単な意味でのアイデアは、3 つの定義されたタワーの中の別のタワーを、存在するディスクと同じ順序で充填することであり、手順中に大きなディスクが小さなディスクに重なることがありません。

「A」、「B」、「C」を 3 つの塔とします。「A」は、最初は「n」個のディスクを含むタワーになります。'B' は中間タワーとして使用でき、'C' はターゲットタワーです。

アルゴリズムは次のとおりです。

「C」を使用してタワー「A」から「B」に n-1 個のディスクを移動する
ディスクを「A」から「C」に移動する
「A」を使用してタワー「B」から「C」に n-1 個のディスクを移動する

Java でのコードは次のとおりです。

public class TowerOfHanoi {

public void TOH(int n, int A , int B , int C){
    if (n>0){
        TOH(n-1,A,C,B);
        System.out.println("Move a disk from tower "+A +" to tower " + C);
        TOH(n-1,B,A,C);
    }
}

public static void main(String[] args) {
    new TowerOfHanoi().TOH(3, 1, 2, 3);
}

}

score 0 · Accepted Answer

これは、再帰的に呼び出されるハノイの塔の C++ コードです。

#include <iostream>
void toh(int n, char A, char B, char C) {
    if(n == 1) {
        std::cout << "Move Disc 1 from " << A << " to " << C << std::endl;
        return;
    }
    toh(n-1, A, C, B);
    std::cout << "Move Disc " << n << " from " << A << " to " << C <<std::endl;
    toh(n-1, B, A, C);
}
int main() {
    int numberOfDisc;
    char A = 'A', B = 'B', C = 'C';
    std::cout << "Enter the number of disc: ";
    std::cin >> numberOfDisc;
    toh(numberOfDisc,  A, B, C);
    return 0;
}

score -1 · Accepted Answer

def Hanoi(n, A, B, C):
    if(n==1): print "move plates to empty peg"
    else:
       Hanoi(n-1, A, B, C)
       print "move"+str(n)+" to peg "+C
       Hanoi(n-1, B, C, A)

score -1 · Accepted Answer

/** * */ パッケージ com.test.recursion;

/** * @author kamals1986 ハノイの塔問題の再帰的アルゴリズム * アルゴリズムは累乗 (2,n) で増加します。*/ public class TowerOfHanoi {

private static String SOURCE_PEG = "B";

private static String SPARE_PEG = "C";

private static String TARGET_PEG = "A";

public void listSteps(int n, String source, String target, String spare) {
    if (n == 1) {
        System.out.println("Please move from Peg " + source + "\tTo Peg\t"
                + target);
    } else {
        listSteps(n - 1, source, spare, target);
        listSteps(1, source, target, spare);
        listSteps(n - 1, spare, target, source);
    }
}

public static void main(String[] args) {
    long startTime = System.currentTimeMillis();
    new TowerOfHanoi().listSteps(18, SOURCE_PEG, TARGET_PEG, SPARE_PEG);

    long endTime = System.currentTimeMillis();

    System.out.println("Done in " + (endTime - startTime) / 1000
            + "\t seconds");
}

}

score -1 · Accepted Answer

Tower (N,source,aux.dest):

if N =1 Then
   Write : Source -> dest
   return
end of if

N-1 ディスクをペグソースからペグ AUX に移動します
```
call Tower (N-1, source, dest, aux)
```
ソースを書き込む -> dest
N-1 ディスクを peg aux から peg dest に移動します
```
call Tower (N-1, source, dest, aux)
```
戻る

score -2 · Accepted Answer

私も再帰を取得しようとしています。

私は自分の考えを見つけました、

私はそれを一連のステップのように考えています（ステップは一定ではなく、前のノードによって変わる可能性があります）

私は2つのことを理解する必要があります：

前のノード
ステップの種類
ステップの後、呼び出しの前に他に何がありますか（これは次の呼び出しの引数です

例

階乗

1,2,6,24,120.........または

1,2 *（1）、3 *（2 * 1）、4 *（3 * 2 * 1,5 *（4 * 3 * 2 * 1）

step=最後のノードで複数

ステップの後、次のノードに到達するために必要なもの、要約1

わかった

function =

n*f(n-1) 

its 2 steps process
from a-->to step--->b

私はこの助けを望んでいました、ノードからノードへの行き方ではなく、ノード->ステップ->ノードの2つのthnikについて考えてください

node->stepは関数の本体ですstep->nodeは他の関数の引数です

さようなら:)私が助けてくれることを願っています

recursion - ハノイの塔: 再帰アルゴリズム

29 に答える 29

Related

Reference