Eine lineare Diophantische Gleichung lösen (siehe Beschreibung für Beispiele)

Brute-Force-Rekursion ist eine Option, abhängig davon, wie groß der Wert oder die Anzahl der Werte sein soll.

Annahmen: Die Benutzereingaben (die Multiplikanden) sind immer verschiedene positive ganze Zahlen. Die zu findenden Koeffizienten müssen nicht negative ganze Zahlen sein.

Algorithmus:

Dies ist eher eine mathematische Frage als eine Programmierfrage. Sobald Sie einen geeigneten Algorithmus haben, sollte es nicht zu schwer sein.

Ich schlage vor, Sie googeln auf Diophantische Gleichungen.

Ich habe eine Erklärung für Sie gefunden.

Ich habe dafür Java-Code geschrieben. Bitte hilf dir selbst. Die Lösungen werden nicht ausgiebig getestet, aber bisher scheint es gut zu funktionieren.

Hinzufügen zu Klas sehr genauer Antwort:

  

Hilberts 10. Problem fragte, ob ein Algorithmus existiere, um zu bestimmen, ob eine beliebige Diophantische Gleichung eine Lösung hat. Ein solcher Algorithmus existiert für die Lösung von Diophantine-Gleichungen erster Ordnung. Die Unmöglichkeit, eine allgemeine Lösung zu finden, wurde jedoch 1970 von Yuri Matiyasevich nachgewiesen.

entnommen aus: Wolfram MathWorld

Ein Brute-Force-Algorithmus ist wie folgt (3-Variable-Fall):

Um dies für den Fall der Variablen N zu verallgemeinern, müssen Sie in eine rekursive Form konvertieren.

Dieser Algorithmus ist O(f(size, a)^N) für eine Funktion f .

• Wir können Grenzen wie folgt auf f setzen: size / MaxValue(a) <= f(size, a) <= size / MinValue(a) .
• Im schlimmsten Fall (wo alle a[i] s 1 sind) f(size, a) ist size .

Wie auch immer, das ist ziemlich schrecklich für große Werte von N . Während also der rekursive N-Variablen-Algorithmus eleganter wäre, ist er wahrscheinlich nicht sehr praktisch.

Wenn Sie bereit sind, 34 Euro an den Springer Verlag zu geben, klicken Sie hier einen Link zu einer Zeitung , die (lt zur Zusammenfassung) enthält einen Algorithmus zum Lösen des N-Variablenfalls.

Es gibt entweder keine oder unendlich viele Lösungen. Es ist oft der Fall, dass Sie eine zusätzliche Einschränkung haben, dass die Lösung übereinstimmen muss. Ist das bei Ihrem Problem der Fall?

Beginnen wir mit der einfachsten Situation, in der zwei Unbekannte vorkommen: a*x + b*y = c :

Der erste Schritt besteht darin, den euklidischen Algorithmus zu verwenden, um die GCD von a und b zu finden, nennen wir sie es d . Als Bonus stellt der Algorithmus x' und y' so bereit, dass a*x' + b*y' = d . Wenn d c nicht teilt, gibt es keine Lösung. Andernfalls ist eine Lösung:

Der zweite Schritt besteht darin, alle Lösungen zu finden. Das heißt, wir müssen alle p und q so finden, dass a*p + b*q = 0 . Wenn sowohl (x,y) als auch (X, Y) Lösungen sind, dann

Die Antwort darauf ist p = b/d und q = -a/d wo d = GCD(a,b) und ist bereits in Schritt 1 berechnet. Die allgemeine Lösung ist nun:

wobei n eine ganze Zahl ist.

Der erste Schritt ist einfach auf mehrere Variablen zu erweitern. Ich bin mir nicht sicher, den zweiten Schritt zu verallgemeinern. Meine erste Vermutung wäre, eine Lösung für alle Koeffizientenpaare zu finden und diese Lösungen zu kombinieren.

Dies ist eine Lösung in Perl. eher ein Hack mit Regex.

Nach diesem Blog posten , um algebraische Gleichungen mit regex zu lösen.

Wir können das folgende Skript für 3x + 2y + 5z = 40

Ausgabe: x = 11, y = 1, z = 1

das berühmte Älteste spielt das Klavier Puzzle endet als 3 Variable Gleichung

Diese Methode gilt für eine Bedingung , dass die Variablen sind tatsächlich positiv und die Konstante ist positiv.

Der Grund, warum es keine Bibliothek gibt, die das tut, ist ähnlich, warum Sie keine Bibliothek für Permutationen finden - Sie erzeugen so viele Daten, dass dies wahrscheinlich das Falsche ist.

Genauer gesagt, wenn Sie n Variablen haben, deren Gesamtsummen X sind, dann haben Sie O(Xn-1) Antworten. X und n müssen nicht sehr groß sein, damit dies zu einem Problem wird.

Das heißt, hier ist etwas Python, das ziemlich effizient alle notwendigen Informationen ermittelt, um die Antwort zu kodieren:

Wenn ich "encode" sage, sieht die Datenstruktur so aus. Für jeden möglichen Koeffizienten erhalten wir ein Array von (coefficient, [subanswers]) . Wann immer es möglich ist, werden Unterabfragen verwendet, um die Datenstruktur so klein wie möglich zu machen. Wenn Sie es nicht können, können Sie das Ergebnis in eine Reihe von Antworten rekursiv erweitern, und auf diese Weise werden Sie ziemlich effizient sein. (Tatsächlich ist es O(nX) .) Sie werden sehr wenig Logik wiederholen, um die gleichen Fakten immer wieder zu entdecken. (Die zurückgegebene Liste kann jedoch sehr groß werden, weil eine große Liste von Antworten zurückgegeben wird.)