Visual Basic .NET: Diophantische Gleichung

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.