Integrale Lösung für die Gleichung 'a + bx = c + dy'

7

In der Gleichung a + bx = c + dy sind alle Variablen Ganzzahlen. a , b , c und d sind bekannt. Wie finde ich integrale Lösungen für x und y ? Wenn ich richtig denke, wird es eine unendliche Anzahl von Lösungen geben, getrennt durch das niedrigste gemeinsame Vielfache von b und d , aber alles, was ich brauche, ist eine Lösung, und ich kann den Rest berechnen. Hier ist ein Beispiel:

%Vor%

Im Moment durchlaufe ich ganzzahlige Werte von x , bis ich einen integralen Wert für y (Pseudocode) gefunden habe:

%Vor%

Ich habe das Gefühl, dass es einen besseren Weg gibt, dies zu tun. Gibt es eine Möglichkeit, x und y ohne Schleife zu finden? Ich benutze C ++, wenn das von Bedeutung ist.

    
Joel 12.10.2013, 20:01
quelle

1 Antwort

26

lineare diophantische Gleichungen haben die Form ax + by = c . Wenn c der größte gemeinsame Teiler von a und b ist, bedeutet dies a=z'c und b=z''c , dann ist dies Bézouts Identität des Formulars

mit a=z' und b=z'' und die Gleichung hat eine unendliche Anzahl von Lösungen. Statt der Methode der Versuchssuche können Sie überprüfen, wenn c der größte gemeinsame Teiler (GCD) von a und b ist (in Ihrem Fall bedeutet dies bx - dy = c - a )

Wenn a und b ein Vielfaches von c sind, dann können x und y mit berechnet werden erweiterter euklidischer Algorithmus , der die Ganzzahlen x und y (von denen eine typischerweise negativ ist) findet, die Bézouts Identität erfüllen

und deine Antwort ist:

a = k*x , %Code%, b = k*y für jede Ganzzahl k .

(als Randnotiz: dies gilt auch für jede andere euklidische Domäne , dh Polynomring und jede euklidische Domäne ist eindeutige Faktorisierungsdomäne ). Sie können die Iterative Methode verwenden, um diese Lösungen zu finden:

Iterative Methode

Durch routinemäßige Algebra zum Expandieren und Gruppieren ähnlicher Begriffe (siehe letzten Abschnitt des zuvor erwähnten Wikipedia-Artikels ) Algorithmus für iterative Methode wird erhalten:

  • 1. Wenden Sie den euklidischen Algorithmus an und lassen Sie qn (n beginnt bei 1) eine endliche Liste von Quotienten in der Division.
  • 2. Initialisiere x0, x1 als 1, 0 und y0, y1 jeweils als 0,1.
    • 2.1 Dann für jedes i solange Qi definiert ist,
    • 2.2 Berechne xi + 1 = xi-1 - qixi
    • 2.3 Berechne yi + 1 = yi-1 - qiyi
    • 2.4 Wiederholen Sie das obige Verfahren, nachdem Sie i um 1 erhöht haben.
  • 3. Die Antworten sind die vorletzten von xn und yn.

Pseudocode:

%Vor%

Also habe ich einen Beispielalgorithmus geschrieben, der größten gemeinsamen Teiler mit der Euklidischer Algorithmus für nicht-negative c - a = k * gcd(a,b) und a berechnet (für negative - diese zusätzlichen Schritte werden benötigt), es gibt GCD zurück und speichert Lösungen für b und x in den Variablen, die als Referenz übergeben wurden:

%Vor%

durch Übergeben eines Beispiels aus Wikipedia für y und a = 120 erhalten wir:

%Vor%

r: 5,3,2,1,0,

q: 5,4,1,1,2,

x: 1,0,1, -4,5, -9,23,

y: 0,1, -5,21, -26,47, -120,

was mit der angegebenen Tabelle für dieses Beispiel übereinstimmt:

    
4pie0 12.10.2013, 20:31
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Wie ändere ich die Reihenfolge eines Arrays mit v-for und orderBy Filter in Vue JS?