Rückgabe beim erweiterten Euklidischen Algorithmus?
Hallo liebe Community,
meine Tochter und ich sitzen hier an einer Aufgabe, bei der wir nicht ganz weiterkommen. Eine Tabelle soll mit dem erweiterten Euklidischen Algorithmus gelöst werden. Den ersten Teil der Tabelle haben wir wie folgt gelöst (alle Werte in Hellblau) die linke Spalte und grüne Zahlen sind vorgegeben. Wir wissen nicht ganz wofür Rückgabe stehen soll. Und sind unsere Lösungen in Blau korrekt, bzw. kommen sie in diese Spalten?
Liebe Grüße
Matti
2 Antworten
Wichtig wäre heir natürlich mal den eigentlichen Algorithmus zu sehen, denn darauf basierend wird sich ja die Rückgabe ergeben.
Aber vermutlich wird aus (d*,s*,t*)=(1,1,0) ein (d,s,t)=(d*,t*,s*-(a div b)t*)=(1,0,1-(2 div1)*0)=(1,0,1). Das wäre zumindest eine gängige Variante.
Konnten es knacken, Ihre Variante war sehr ähnlich. Vielen Dank für die Hilfe!
Vielleicht hat das Tripel etwas mit den Bézout-Koeffizienten zu tun: sa+tb=ggT(a,b)
Das kommt auf den Algorithmus an, welchen ihr für die Berechnung benutzt.
Welcher ist es denn?
Daran hatten wir auch erst gedacht, das war es aber nicht. Ich hätte den Algo hier erwähnen müssen, mein Fehler! Dennoch vielen Dank für die Hilfe! :)