Das Türme von Hanoi Problem ist ein klassisches Problem für die Rekursion. Sie erhalten 3 Stifte mit Scheiben auf einem von ihnen, und Sie müssen alle Scheiben von einem Stift auf einen anderen verschieben, indem Sie die angegebenen Regeln befolgen. Sie müssen dies auch mit der Mindestanzahl von Zügen tun.

Hier ist ein rekursiver Algorithmus, der das Problem löst:

void Hanoi3(int nDisks, char source, char intermed, char dest)
{
    if( nDisks > 0 )
    {
        Hanoi3(nDisks - 1, source, dest, intermed);
        cout << source << " --> " << dest << endl;
        Hanoi3(nDisks - 1, intermed, source, dest);
    }
}


int main()
{
    Hanoi3(3, 'A', 'B', 'C');

    return 0;
}

Jetzt stell dir das gleiche Problem vor, nur mit 4 Stiften, also fügen wir einen weiteren Zwischenstift hinzu. Wenn wir vor dem Problem stehen, dass wir uns an einem Punkt für einen Zwischenstift entscheiden müssen, wählen wir den am weitesten links stehenden, falls mehr als 1 frei ist.

Ich habe den folgenden rekursiven Algorithmus für dieses Problem:

void Hanoi4(int nDisks, char source, char intermed1, char intermed2, char dest)
{
    if ( nDisks == 1 )
        cout << source << " --> " << dest << endl;
    else if ( nDisks == 2 )
    {
        cout << source << " --> " << intermed1 << endl;
        cout << source << " --> " << dest << endl;
        cout << intermed1 << " --> " << dest << endl;
    }
    else
    {
        Hanoi4(nDisks - 2, source, intermed2, dest, intermed1);
        cout << source << " --> " << intermed2 << endl;
        cout << source << " --> " << dest << endl;
        cout << intermed2 << " --> " << dest << endl;
        Hanoi4(nDisks - 2, intermed1, source, intermed2, dest);
    }
}

int main()
{
    Hanoi4(3, 'A', 'B', 'C', 'D');

    return 0;
}

Nun, meine Frage ist, wie ich diesen rekursiven Ansatz verallgemeinern würde, um für @ zu arbeiteK Heringe? Die rekursive Funktion würde ein @ erhaltchar[], das die Beschriftungen jedes Stapels enthält, sodass die Funktion ungefähr so aussieht:

void HanoiK(int nDisks, int kStacks, char labels[]) { ... }

ch kenne den Frame-Stewart-Algorithmus, der höchstwahrscheinlich optimal, aber nicht bewiesen ist und Ihnen das @ gibNumme von Zügen. Ich bin jedoch an einer streng rekursiven Lösung interessiert, die dem Muster der rekursiven Lösungen für 3 und 4 Stifte folgt und die tatsächlichen Züge ausgibt.

Zumindest für mich ist der auf Wikipedia präsentierte Pseudocode des Frame-Stewart-Algorithmus eher abstrakt, und es ist mir nicht gelungen, ihn in Code zu übersetzen, der die Bewegungen druckt. Ich würde eine Referenzimplementierung davon akzeptieren (für randomk) oder noch detaillierterer Pseudocode.

Ich habe versucht, einen Algorithmus zu finden, der das Label-Array entsprechend permutiert, aber ich hatte kein Glück, ihn zum Laufen zu bringen. Anregungen sind willkommen.

Aktualisieren

Dies scheint in einer funktionalen Sprache viel einfacher zu lösen zu sein. Hier ist eine F # -Implementierung basierend auf LarsHs Haskell-Lösung:

let rec HanoiK n pegs = 
    if n > 0 then 
        match pegs with
        | p1::p2::rest when rest.IsEmpty            
            ->  printfn "%A --> %A" p1 p2
        | p1::p2::p3::rest when rest.IsEmpty        
            ->  HanoiK (n-1) (p1::p3::p2::rest)
                printfn "%A --> %A" p1 p2
                HanoiK (n-1) (p3::p2::p1::rest)    
        | p1::p2::p3::rest when not rest.IsEmpty    
            ->  let k = int(n / 2)
                HanoiK k (p1::p3::p2::rest)
                HanoiK (n-k) (p1::p2::rest)
                HanoiK k (p3::p2::p1::rest)

let _ =
    HanoiK 6 [1; 2; 3; 4; 5; 6]

Und ohne 3 Heringe als Randfall zu behandeln:

let rec HanoiK n pegs = 
    if n > 0 then 
        match pegs with
        | p1::p2::rest when rest.IsEmpty            
            ->  printfn "%A --> %A" p1 p2
        | p1::p2::p3::rest     
            ->  let k = if rest.IsEmpty then n - 1 else int(n / 2) 
                HanoiK k (p1::p3::p2::rest)
                HanoiK (n-k) (p1::p2::rest)
                HanoiK k (p3::p2::p1::rest)

Beachten Sie, dass dies nicht für entartete Fälle gilt, für die es keine Lösung gibt, z. B.HanoiK 2 [1; 2]