Visual Basic .NET: Diophantische Gleichung

Erklärung

Dass die Gleichung nicht immer lösbar ist, kann durch das Beispiel $a=b=0$ und $c=1$ veranschaulicht werden. Es gibt auch nicht so triviale Beispiele, z. B. wenn $a$ und $b$ beide gerade, $c$ 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 $c=0$ gilt, können wir mit $x=y=0$ sofort eine einfache Lösung angeben. Vor allem aber können wir in den folgenden Überlegungen immer $c\ne 0$ annehmen, da dieser Fall ja gerade behandelt wurde.

Nun überlegen wir uns, was $a=0$ bedeutet. $a$ und $b$ sind vertauschbar, wenn wir die danach die Lösungen vertauschen. Wenn nun auch $b=0$ 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 $x$ und $y$ immer $0$. Die rechte Seite ist $c$, von dem wir ausgeschlossen haben, dass es $0$ ist. Also gibt es keine Lösung. Für den Fall $b\ne 0$ 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 $a\ne 0$ und $c\ne 0$ gilt. Wenn wir nun auch noch $b=0$ annehmen, reduziert sich die Gleichung auf $ax=c$. Weil wir ja mit ganzen Zahlen arbeiten, ist das nur lösbar, wenn $a$ ein Teiler von $c$ ist; mit anderen Worten, der Divisionsrest von $c$ geteilt durch $a$ ist $0$. Der Quotient ist dann die Lösung $x$, und wir können $y=0$ setzen.

Für den anderen Fall, also $b\ne 0$, 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 $a,b,c\ne 0$ 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 $b$ eingesetzt wird, $r$ steht. Aus der Angabe wissen wir, dass $|r|<|b|$ gilt. Also spätestens nach $|b|$ Schritten wird für $r$, d. h. für $b$ der Wert $0$ eingesetzt. Dann terminiert die Funktion bekanntermaßen.

Code

Visual Basic .NET: Vorlage:Code 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

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 $q$ zusätzlich benötigen. Alles andere wird durch Parameter weitergegeben. Da jeder rekursive Aufruf sein eigenes $q$ hat, gibt es nicht ein $q$, 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.

Visual Basic .NET: Vorlage:Code Auch dieser Code ist optimierbar. Jedoch leidet dann die Verständlichkeit arg darunter.