Algorithmus zur Bestimmung nicht negativer Werte zur Lösung der Lösung für die lineare diophantinische Gleichung

StackOverflow https://stackoverflow.com/questions/1467907

  •  13-09-2019
  •  | 
  •  

Frage

Ich suche eine Methode, um festzustellen, ob es eine Lösung für Gleichungen gibt, wie z. B.:3n1+4n2+5n3 = 456, wo N1, N2, N3 sind positive Ganzzahlen.

Oder allgemeiner: sind da Null oder positiv Ganzzahlen N1, N2, N3... das löst die Gleichung k1n1+k2n2+k3n3 ... = m wo K1, K2, K3... und m sind positive Ganzzahlen bekannt.

Ich muss keine Lösung finden - nur um festzustellen, ob eine Lösung vorhanden ist.

Bearbeiten:

In Bezug auf die praktische Verwendung dieses Algorithmus:

In einer Kommunikationsbibliothek möchte ich entscheiden, ob eine bestimmte Nachricht gemäß ihrer Größe gültig ist, bevor sie mit der Nachricht handelt. Zum Beispiel: Ich weiß, dass eine Nachricht null-or-more-3-Bytes-Elemente, Null-or-More-4-Bytes-Elemente und Elemente von Null-or-More 5-Byte enthält. Ich habe eine Nachricht von 456 Bytes erhalten, und ich möchte ihre Gültigkeit bestimmen, bevor ich den Inhalt weiter inspiziert habe. Natürlich enthält der Header der Nachricht die Anzahl der Elemente jedes Typs, aber ich möchte in der Kommunikations-Bibliothek-Ebene eine erste Inspektion erstellen, indem ich etwas wie etwas verabschiedete pair<MsgType,vector<3,4,5>>.

War es hilfreich?

Lösung

Sie fragen, ob der reguläre Ausdruck

(xxx | xxxx | xxxxx)*

Übereinstimmung mit xx ... x, wobei x 456 -mal auftritt.

Hier ist eine Lösung in O (n+a^2), wobei a die kleinste der Zahlen auf der linken Seite (in diesem Fall 3) ist.

Angenommen, Ihre Zahlen betragen 6,7,15. Ich nenne eine Nummer, die in Form 6x+7y+15z "verfügbar" ausdrucksfähig ist. Sie müssen überprüfen, ob eine bestimmte Nummer verfügbar ist.

Wenn Sie in der Lage sind, eine Nummer N zu erhalten Sie können keine Nummer n erhalten, dann ist N-6 sicherlich auch nicht verfügbar (wenn Sie (n-6) erhalten könnten, dann (n-6)+6 = n wäre verfügbar), bedeutet dies N-12. N-18, N-6K sind auch nicht verfügbar.

Angenommen, Sie haben festgestellt, dass 15 verfügbar sind, 9, aber nicht. In unserem Fall 15 = 6*0+7*0+15*1, kann aber in keiner Weise 9 bekommen. Nach unserer vorherigen Argumentation ist 15+6k für alle k> = 0 und 9-6k für alle k> = 0 verfügbar. Wenn Sie eine Nummer haben, die durch 6 als Rest (3, 9, 15, 21, ...) 3 enthält, können Sie schnell beantworten: Zahlen <= 9 sind nicht verfügbar, Zahlen> = 15 sind.

Es reicht aus, für alle möglichen Überreste der Division um 6 (dh 0,1,2,3,4,5) zu bestimmen. Dies ist die kleinste Zahl, die verfügbar ist. (Ich habe nur gezeigt, dass diese Zahl für den Rest 3 15 ist).

So machen Sie es: Erstellen Sie ein Diagramm mit Scheitelpunkten 0,1,2,3,4,5. Für alle Zahlen k, dass Sie verabreicht werden (7,15 - Wir ignorieren 6) Fügen Sie eine Kante von x zu (x + k) mod 6 hinzu. Geben Sie ihm Gewicht (x + k) div 6. Dijkstra -Algorithmus Verwenden Sie 0 als Anfangsknoten. Die vom Algorithmus gefundenen Entfernungen sind genau die Zahlen, nach denen wir suchen.

In unserem Fall (6,7,15) führt die Zahl 7 auf 0 -> 1 (Gewicht 1), 1 -> 2 (Gewicht 1), 2 -> 3 (Gewicht 1), ..., 5 -> 0 (Gewicht 1) und die Zahl 15 ergibt 0 -> 3 (Gewicht 2), 1 -> 4 (Gewicht 2), ..., 5 -> 1 (Gewicht 2). Der kürzeste Weg von 0 bis 3 hat eine Kante - sein Gewicht beträgt 2. 6*2 + 3 = 15 ist die kleinste Zahl, die 3 als Rest ergibt. 6*1 + 3 = 9 ist nicht verfügbar (na ja, wir haben das zuvor von Hand überprüft).

Und was ist die Verbindung zu regulären Ausdrücken? Nun, jeder reguläre Ausdruck hat einen äquivalenten endlichen Automaten, und ich habe einen von ihnen gebaut.

Dieses Problem mit mehreren zulässigen Abfragen erschien auf der Polnische Olympiade Und ich habe die Lösung übersetzt. Wenn Sie jetzt hören, dass eine Person sagt, dass Informatik für echte Programmierer nicht nützlich ist, schlagen Sie sie ins Gesicht.

Andere Tipps

Entsprechend Dies, Wenn der größte gemeinsame Faktor von {n1, n2, n3, ...} kein Divisor von M ist, haben Sie keine Lösung. Diese Seite zeigt ein Beispiel für nur {N1, N2}, erstreckt sich jedoch auf größere Systeme. Das neue Problem besteht darin, einen Algorithmus zu schreiben, um den größten gemeinsamen Faktor zu finden, aber das ist angesichts des ursprünglichen Problems trivial.

Ein Teil Ihres Algorithmus würde also den GCF ({n1, n2, ...}) finden und dann sehen, ob es ein Faktor von m ist. Wenn dies nicht der Fall ist, gibt es keine Lösung. Dies zeigt nicht vollständig, dass eine Lösung existiert, aber sie kann Ihnen schnell zeigen, dass es keine gibt, was immer noch nützlich ist.

Sieht so aus, als würden Sie über ein System von Ungleichheiten mit ganzzahligen Einschränkungen sprechen. Die Realität ist, dass Sie für dieses System lösen:

k1n1+k2n2+k3n3...=m
n1 >= 0
n2 >= 0
n3 >= 0

Und die zusätzliche Einschränkung, dass N1, N2, N3 Ganzzahlen sind. Das ist ein Lineares Programmieren Problem. Leider für Sie der allgemeine Fall der Lösung eines solchen Systems mit Ganzzahlbeschränkungen sind NP-Complete. Es gibt jedoch viele Algorithmen, die es für Sie lösen.

Dies hängt mit dem zusammen FROBENIUS Münzproblem, was für n> 3 nicht gelöst wurde.

Ein Brute-Force-Ansatz (Pseudocode):

def a = 3
def b = 4
def c = 5
def x = 456

for n1 = a to int(x / a) + 1 step a
  for n2 =b to int(x / b) + 1 step b
    for n3 = c to int(x / c) + 1 step c
      if a * n1 + b * n2 + c * n3 = x then
        print n1, n2, n3

Siehe auch http://mail.python.org/pipermail/python-list/2000-april/031714.html

BEARBEITEN: In einer Kommunikationsbibliothek würde dies keinen Sinn machen, da sie sofort funktionieren muss. In der Anwendung des OP würde ich wahrscheinlich eine Art Hash verwenden, aber sein Ansatz klingt interessant.

Hier ist etwas auf dem 2 -Nummern -Fall. Ich habe noch nicht herausgefunden, wie man es skaliert:

Angesichts der 2 relativ primären Ganzzahlen x und y gibt es positive Ganzzahlen A und B, so dass ax+by=c für alle c>=(x-1)(y-1)

Grundsätzlich funktioniert dies, weil, wenn Sie annehmen x<y, Sie können alle Ganzzahlen mod x mit (0, y, 2y, 3y, ..., (x-1) y) ausdrücken. Wenn Sie nun ein positives Vielfaches von x hinzufügen, können Sie alle Ganzzahlen zwischen [(x-1) (y-1), (x-1) y als alle Ganzzahlen zwischen (x-1) (y- 1) und (x-1) y-1 wurden zuvor ausgedrückt.

  1. GCD (x, y). Wenn C nicht mehrfach ist, geben Sie false zurück.
  2. Wenn GCD (x, y)> 1, x, y, c durch GCD teilen
  3. Wenn c> (x-1) (y-1), geben Sie wahr zurück
  4. Sonst Brute Force

Und für die brutale Kraft: 

if int(c/y) >= c*y^(-1) mod x, return true, 
else return false

Vielleicht sind die folgenden Informationen irrelevant, weil es nicht mit der allgemeinen Situation umgeht, sondern ...

Wenn das Problem feststellt, ob eine bestimmte positive Ganzzahl k als Summe gebildet werden kann 3*n1 + 4*n2 + 5*n3, Für nichtnegative ganze ganze Zahlen N1, N2, N3 lautet die Antwort "Ja" für k> = 3.

Rosens bekanntes Lehrbuch Diskrete Mathematik und ihre Anwendungen, p. 287 der sechsten Ausgabe beweist, dass "jeder Porto von 12 Cent oder mehr mit nur 4-Cent- und 5-Cent-Briefmarken unter Verwendung der Induktion gebildet werden kann.

Der Basisschritt ist, dass das Porto von 12 Cent mit 3 Vier-Cent-Briefmarken gebildet werden kann.

Der Induktionsschritt berücksichtigt, dass, wenn P (k) mit vier Cent-Briefmarken wahr ist, einfach einen Vier-Cent-Stempel durch einen Fünf-Cent-Stempel ersetzen, um zu zeigen, dass P (K+1) wahr ist. Wenn P (k) mit keinen Vier-Cent-Briefmarken wahr ist, benötigen wir dann mindestens 3 Fünf-Cent Briefmarken, um K+1 zu erreichen.

Um die oben genannte Lösung für dieses Problem zu erweitern, müssen nur noch einige weitere Fälle berücksichtigt werden.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top