Zum Inhalt springen

Visual Basic .NET: Diophantische Gleichung

Aus Wikibooks

Erklärung

[Bearbeiten]

Dass die Gleichung nicht immer lösbar ist, kann durch das Beispiel und veranschaulicht werden. Es gibt auch nicht so triviale Beispiele, z. B. wenn und beide gerade, jedoch ungerade ist. Die linke Seite wäre immer gerade und die rechte ungerade.

Der nächsten beiden Tipps sind für die Implementierung besonders wertvoll. Der erste gibt einen Hinweis auf eine mögliche Signatur der Funktion. Zum zweiten: Nun, wenn gilt, können wir mit sofort eine einfache Lösung angeben. Vor allem aber können wir in den folgenden Überlegungen immer annehmen, da dieser Fall ja gerade behandelt wurde.

Nun überlegen wir uns, was bedeutet. und sind vertauschbar, wenn wir die danach die Lösungen vertauschen. Wenn nun auch gilt gewinnen wir damit zwar nichts, aber wir können es ja extra behandeln, denn dieser Fall ist sehr einfach: Die linke Seite ist unabhängig von und immer . Die rechte Seite ist , von dem wir ausgeschlossen haben, dass es ist. Also gibt es keine Lösung. Für den Fall wenden wir die erwähnte Methode mit Vertauschen an. Wir verlassen uns dabei darauf, dass wir die Aufgabe dann lösen können

Jetzt kommt der wesentliche Algorithmus. Wenn wir die vorhergehenden Überlegungen zusammenfassen, wissen wir an dieser Stelle nur, dass und gilt. Wenn wir nun auch noch annehmen, reduziert sich die Gleichung auf . Weil wir ja mit ganzen Zahlen arbeiten, ist das nur lösbar, wenn ein Teiler von ist; mit anderen Worten, der Divisionsrest von geteilt durch ist . Der Quotient ist dann die Lösung , und wir können setzen.

Für den anderen Fall, also , behandeln, werden uns eine recht klare Anweisungen gegeben. Unter Umständen können wir die Schritte noch optimieren.

Aus den Überlegungen folgt, dass der Algorithmus terminiert wenn er es für tut. In allen anderen Fällen können wir die Lösung direkt angeben oder erkennen, dass sie nicht existiert. Wenn wir den rekursiven Aufruf betrachten, erkennen wir, dass dort wo eingesetzt wird, steht. Aus der Angabe wissen wir, dass gilt. Also spätestens nach Schritten wird für , d. h. für der Wert eingesetzt. Dann terminiert die Funktion bekanntermaßen.

Code:  

' Die Signatur wird uns schon auf dem Silbertablett serviert.
Private Function Diophant(ByVal a As Integer, ByVal b As Integer, ByVal c As Integer, ByRef x As Integer, ByRef y As Integer) As Boolean
    ' Behandlung der Trivialfälle.
    If c = 0 Then
        x = 0 ' Wir geben die Lösungen an.
        y = 0
        Return True ' Wir haben Lösungen, also True.
    ElseIf a = 0 Then
        If b = 0 Then Return False ' c <> 0, also keine Lösung.
        Return Diophant(b, a, c, y, x) ' Hier vertauschen wir geschickt a und b sowie x und y.
    End If
    
    ' Nun der eigentliche Algorithmus:
    If b = 0 Then
        ' Dass Mod den Divisionsrest liefert, sollte bekannt sein.
        If c Mod a = 0 Then
            x = c \ a ' Der ganzzahlige Divisionsoperator \ sollte bekannt sein.
            y = 0
            Return True
        Else
            Return False
        End If
    Else
        Dim q = a  \  b,
            r = a Mod b
        ' Beachte: Hier sind x und y vertauscht! Damit wird die Zuordnung x = y' ohne extra Anweisung erledigt.
        If Diophant(b, r, c, y, x) Then
            ' Wenn wir hier sind, war das bisherige Lösen erfolgreich und wir können die Lösung nach Anleitung angeben.
            ' in der Zuweisung für y müssen wir x' und y' vertauschen, also steht da: y = y' - q * x'.
            ' x' und y' sind schon in Form von x und y vorhanden.
            y -= q * x ' bleibt als einziges zu tun.
            Return True
        Else
            Return False
        End If
    End If
End Function

Dieser Code ist mit den obigen Erklärungen gut verständlich. Potenzial für Optimierungen gibt es durchaus, sie beziehen sich auf die Abschnitte mit Else Return False und es ist verhältnismäßig gering.

Die imperative Methode

[Bearbeiten]

Nun wollen wir uns noch an die Implementierung des imperativen Algorithmus wagen. Wenn wir die rekursive Lösung betrachten so fällt uns auf, dass wir nach dem rekursiven Aufruf nur noch zusätzlich benötigen. Alles andere wird durch Parameter weitergegeben. Da jeder rekursive Aufruf sein eigenes hat, gibt es nicht ein , sondern eine ganze Reihe. Sie wird genau in umgekehrter Reihenfolge auf- und abgebaut, entspricht also einem Stapel, auch Stack oder Kellerspeicher genannt. Im .NET Framework gibt es die Klasse System.Collections.Generics.Stack(Of T), die uns einen vorgefertigten Stapelspeicher zur Verfügung stellt. Mit Push legen wir etwas oben drauf, mit Pop nehmen wir etwas herunter.

Code:  

Private Function Diophant(ByVal a As Integer, ByVal b As Integer, ByVal c As Integer, ByRef x As Integer, ByRef y As Integer) As Boolean
    ' Behandlung der Trivialfälle erfolgt wie vorhin. Der einzelne rekursive Aufruf soll uns nicht stören; er ist verschmerzbar, da er höchstens einmal auftritt.
    Dim stack As New Stack(Of Integer)
    While b <> 0
        Dim q = a  \  b,
            r = a Mod b
        stack.Push(q)
        a = b
        b = r
    Wend
    ' Ab hier gilt b = 0.
    If c Mod a <> 0 Then Return False
    x = c \ a
    y = 0
    While stack.Count > 0
        Dim q = stack.Pop
        ' Hier kommen wir leider um eine Hilfsvariable nicht herum.
        Dim h = x
        x = y
        y = h - q * y
    Wend
    Return True
End Function

Auch dieser Code ist optimierbar. Jedoch leidet dann die Verständlichkeit arg darunter.