Code zu Algorithmen in .NET

• Die Türme von Hanoi
• Ausgabe einer Zeichentabelle

Die Türme von Hanoi

Das Spiel Die Türme von Hanoi besteht aus einem Brett, auf dem drei Stäbe montiert sind. Auf einem der Stäbe liegen vier oder fünf „Klötzchen“, das größte zuunterst (wie bei einer Pyramide). Man muß nun versuchen, diesen Klötzchen-Turm auf einen anderen Stab zu bringen. Dabei darf nie ein größeres Klötzchen auf einem kleineren zu liegen kommen.

Hinter dem Spiel steckt eine Legende, nach der in Hanoi drei Säulen standen, eine aus Kupfer, eine aus Silber und die dritte aus Gold. Auf einer dieser Säulen standen hundert Porphyrscheiben. Die Scheibe mit dem größten Umfang lag unten und die kleineren darauf, sodaß oben die kleinste der Scheiben lag. Ein alter Mönch stellte sich die Aufgabe, diese Scheiben auf eine andere Säule umzuschichten. In einem Schritt sollte aber nur eine Scheibe bewegt werden und zudem galt die Bedingung, daß eine größere Scheibe niemals auf eine kleinere gelegt werden durfte.

Der Mönch setzte sich also hin und machte einen Plan. Am nächsten Tag hatte er eine Lösung gefunden, die er alsbald an die Tür des Klosters schlug:

• Falls der Turm aus mehr als einer Scheibe besteht, bitte deinen ältesten Schüler, einen Turm von $n-1$ Scheiben von der ersten zur dritten Säule unter Verwendung der zweiten Säule umzusetzen.

• Trage selbst die erste Scheibe von einer zur anderen Säule.

• Falls der Turm aus mehr als einer Scheibe besteht, bitte deinen ältesten Schüler, einen Turm aus $n-1$ Scheiben von der dritten zu der anderen Säule unter Verwendung der ersten Säule zu transportieren.

Und so setzte er dann auch seine Idee in die Tat um. Sobald die Arbeit beendet wäre, so sagte es die Legende, wäre auch das Ende der Welt gekommen.

Mit der heutigen Rechenleistungen ist man schon sehr viel schneller als das Herumtragen des Mönches. Allerdings ist es bei einer Anzahl von hundert Scheiben auch noch heute praktisch nicht möglich, die Aufgabe durchzuführen: Ein Computer, der 100 Millionen Anweisungen in der Sekunde ausführen kann, bräuchte für hundert Scheiben die enorme Zeit von $4\cdot {10}^{13}$ Jahren. Bereits das Durchlaufen der Funktion mit 10 Scheiben dauert schon ziemlich lange.

Public Sub Main()

    ' Berechne Lösung für 5 Scheiben.
    MoveTower(5, "Kupfer", "Silber", "Gold")
End Sub

Private Sub MoveSlice( _
    ByVal n As Integer, _
    ByVal From As String, _
    ByVal [To] As String _
)
    Console.WriteLine( _
        "Schiebe Scheibe {0} von {1} nach {2}", _
        n, _
        From, _
        [To] _
    )
End Sub

Private Sub MoveTower( _
    ByVal n As Integer, _
    ByVal Copper As String, _
    ByVal Silver As String, _
    ByVal Gold As String _
)
    If n > 1 Then
        MoveTower(n - 1, Copper, Gold, Silver)
        MoveSlice(n, Copper, Gold)
        MoveTower(n - 1, Silver, Copper, Gold)
    Else
        MoveSlice(n, Copper, Gold)
    End If
End Sub

Das Beispiel wurde ursprünglich von Daniel Noll geschrieben und von mir etwas angepaßt.

Ausgabe einer Zeichentabelle

Das folgende Beispiel demonstriert die Divisions- und Modulooperatoren. Dabei soll eine Art Tabelle ausgegeben werden, die sich wie folgt aufbaut:

• Jedes dritte Zeichen ist ein „x“, alle anderen sind Leerzeichen.

• Jede Zeile ist um eins nach links versetzt.

• Links und rechts steht jeweils ein senkrechter Strich.

Gesucht ist nun eine Prozedur PrintTable, die eine Tabelle mit obigem Aussehen und den übergebenen Maßen auf die Konsole schreibt. Das Resultat eines Aufrufs mit Breite und Höhe gleich 7 würde folgende Ausgabe liefern:

|x  x  x|
|  x  x |
| x  x  |
|x  x  x|
|  x  x |
| x  x  |
|x  x  x|

Eine mögliche Implementierung könnte wie folgt aussehen:

Private Sub PrintTable(ByVal Width As Integer, ByVal Height As Integer)
    For Line As Integer = 1 To Height
        Console.Write("|")
        For Column As Integer = 1 To Width

            ' Alternative Bedingung: '(Column + (Line Mod 3)) Mod 3 = 2'.
            If Column Mod 3 = 2 - (Line Mod 3) Then
                Console.Write("x")
            Else
                Console.Write(" ")
            End If
        Next Column
        Console.WriteLine("|")
    Next Line
End Sub