Erweiterter euklidischer Algorithmus

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Hi
Ich schreibe grade eine Facharbeit in Mathe und hab mir jetzt das Programmieren über Internet selbst beigebracht da ich vorher noch nie Informatik hatte... ich hab da ein kleines Problem mit dem erweiterten euklidischen Algorithmus und zwar weiß ich nicht wie ich dem Programm sagen soll, dass er für bestimmte Zahlen wiederholt die vorherigen Gleichungen einsetzen soll...
ich wollte auch gerne, dass er das Rechnen nicht einfach im Hintergrund macht sondern die Rechenschritte zeigt daher habe ich das erst mal so angefangen:

a = 481
b = 253
aList = [a, b, a%b]
modulList = []
vielfachList = []
restList = []
multiList = []
while aList[2] > 0:
print (aList[0], "=", aList[0]//aList[1], "*", aList[1], "+", aList[2])
modulList.append(aList[0])
vielfachList.append(aList[1])
multiList.append(aList[0]//aList[1])
restList.append(aList[2])
aList[0] = aList[1]
aList[1] = aList[2]
aList[2] = aList[0] % aList[1]
if aList[0] < aList[1]:
print (aList[1], "=", aList[1]//aList[0], "*", aList[0], "+", aList[1] % aList[0])
if aList[1] % aList[0] == 0:
break
print ("--------------------------------------------------------------------")

i = 1
copyRestList = []
while len(copyRestList) <= len(restList):
copyRestList.append(restList[len(restList)-i])
i = i + 1
if len(copyRestList) == len(restList):
break
restList = copyRestList

i = 1
copyModulList = []
while len(copyModulList) <= len(modulList):
copyModulList.append(modulList[len(modulList)-i])
i = i + 1
if len(copyModulList) == len(modulList):
break
modulList = copyModulList

i = 1
copyMultiList = []
while len(copyMultiList) <= len(multiList):
copyMultiList.append(multiList[len(multiList)-i])
i = i + 1
if len(copyMultiList) == len(multiList):
break
multiList = copyMultiList

i = 1
copyVielfachList = []
while len(copyVielfachList) <= len(vielfachList):
copyVielfachList.append(vielfachList[len(vielfachList)-i])
i = i + 1
if len(copyVielfachList) == len(vielfachList):
break
vielfachList = copyVielfachList

i = 0
while len(restList) > i:
print (restList, "=", modulList, "-", multiList, "*", vielfachList)
i = i + 1

print ("--------------------------------------------------------------------")

er rechnet jetzt halt erst einmal den ggT aus, was in diesem Fall die 1 ist, und dann formt er im nächsten Schritt alle Gleichungen zu dem Rest um... das sieht dann so aus:

481 = 1 * 253 + 228
253 = 1 * 228 + 25
228 = 9 * 25 + 3
25 = 8 * 3 + 1
--------------------------------------------------------------------
1 = 25 - 8 * 3
3 = 228 - 9 * 25
25 = 253 - 1 * 228
228 = 481 - 1 * 253
----------------------------------------------------------------

jetzt müsste er nur von der Gleichung 1= ausgehen und z.B. die 25 mit dem Term 253-1*228 ersetzen, wie auch die 8*3 mit 8*(228-9*25)...
im Endeffekt sollte das dann so in etwa aussehen:

1=25-8*3=(253-1*228)-8*(228-9*25)
=253-9*(481-1*253)+72*(253-1*228)
=82*253-9*481-72*(481-1*253)
=154*253-81*481


Kann mir da bitte jemand helfen??? Ich komm hier einfach nicht mehr weiter

Danke schon mal im Voraus :)
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Packe deinen Code bitte in Code-Tags, sonst wird es schwierig bis unmöglich dir zu Helfen.
Das Leben ist wie ein Tennisball.
nuss
User
Beiträge: 53
Registriert: Donnerstag 28. August 2008, 11:36

OMG, bitte benutz Funktionen !

hier eine kleine Beispiel funktion, die nichts weiter tut, als 2 Zahlen zu addieren und das Ergebniss zurueckzugeben.

Code: Alles auswählen

def add(x, y):
    return x+y
diese Funktion ist jetzt vielleicht sinnlos,
aber sollte ja auch nur ein Beispiel sein.

Vielleicht solltest du auch noch 1 oder 2 Tutorials durcharbeiten. ;)
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Hi nochmal,
sorry das hatte ich übersehen

Code: Alles auswählen

a = 481
b = 253
aList = [a, b, a%b]
modulList = []
vielfachList = []
restList = []
multiList = []
while aList[2] > 0:
print (aList[0], "=", aList[0]//aList[1], "*", aList[1], "+", aList[2])
modulList.append(aList[0])
vielfachList.append(aList[1])
multiList.append(aList[0]//aList[1])
restList.append(aList[2])
aList[0] = aList[1]
aList[1] = aList[2]
aList[2] = aList[0] % aList[1]
if aList[0] < aList[1]:
print (aList[1], "=", aList[1]//aList[0], "*", aList[0], "+", aList[1] % aList[0])
if aList[1] % aList[0] == 0:
break
print ("--------------------------------------------------------------------")

i = 1
copyRestList = []
while len(copyRestList) <= len(restList):
copyRestList.append(restList[len(restList)-i])
i = i + 1
if len(copyRestList) == len(restList):
break
restList = copyRestList

i = 1
copyModulList = []
while len(copyModulList) <= len(modulList):
copyModulList.append(modulList[len(modulList)-i])
i = i + 1
if len(copyModulList) == len(modulList):
break
modulList = copyModulList

i = 1
copyMultiList = []
while len(copyMultiList) <= len(multiList):
copyMultiList.append(multiList[len(multiList)-i])
i = i + 1
if len(copyMultiList) == len(multiList):
break
multiList = copyMultiList

i = 1
copyVielfachList = []
while len(copyVielfachList) <= len(vielfachList):
copyVielfachList.append(vielfachList[len(vielfachList)-i])
i = i + 1
if len(copyVielfachList) == len(vielfachList):
break
vielfachList = copyVielfachList

i = 0
while len(restList) > i:
print (restList[i], "=", modulList[i], "-", multiList[i], "*", vielfachList[i])
i = i + 1

print ("--------------------------------------------------------------------") 
1 oder 2 Tutorials können mir mit Sicherheit nicht schaden :wink:
mir läuft nur leider die Zeit zur Abgabe davon, und es ist ja auch Gott sei Dank keine Informatikarbeit^^
Daher reicht es meiner Lehrerin, wenn ich die Mathematik verstanden hab und wenn das Programm funktioniert
Aber ich guck mal, wenn ich noch Zeit habe, dass ich es dann etwas schöner schreibe :) es muss nur erstmal funktionieren und da liegt das Problem^^

Grüße
Kalira
Nergal
User
Beiträge: 72
Registriert: Montag 6. Oktober 2008, 14:02

Wenn du eine Liste umdrehen willst kannst du auch

Code: Alles auswählen

>>> x = [1,2,3,4]
>>> x = x[::-1]
>>> x
[4, 3, 2, 1]
>>> 
verwenden.
nuss
User
Beiträge: 53
Registriert: Donnerstag 28. August 2008, 11:36

in python ist ausserdem die Einrückung wichtig,
so kann man bei dem was du geschrieben hast nicht erkennen,
wo die schleifen aufhören und der Code ist so ausserdem nicht lauffähig.
also die in deinem Quelltext eingerückten stellen bitte auch hier einrücken ;)
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

oh, sorry^^
und Danke Nergal, jetzt ist das ganze nicht mehr sooo lang :wink:

Code: Alles auswählen

a = 481
b = 253
aList = [a, b, a%b]
modulList = []
vielfachList = []
restList = []
multiList = [] 
while aList[2] > 0:
	print (aList[0], "=", aList[0]//aList[1], "*", aList[1], "+", aList[2])
	modulList.append(aList[0])
	vielfachList.append(aList[1])
	multiList.append(aList[0]//aList[1])
	restList.append(aList[2])
	aList[0] = aList[1]
	aList[1] = aList[2]
	aList[2] = aList[0] % aList[1]
	if aList[0] < aList[1]:
		print (aList[1], "=", aList[1]//aList[0], "*", aList[0], "+", aList[1] % aList[0])
	if aList[1] % aList[0] == 0:
		break
print ("--------------------------------------------------------------------")

restList = restList[::-1]
modulList = modulList[::-1]
vielfachList = vielfachList[::-1]
multiList = multiList[::-1]

i = 0
while len(restList) > i:                                # nun
    print (restList[i], "=", modulList[i], "-", multiList[i], "*", vielfachList[i])
    i = i + 1

print ("--------------------------------------------------------------------")
Grüße
Kalira
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Statt

Code: Alles auswählen

x = x[::-1]
die wohl etwas lesbarere Variante

Code: Alles auswählen

x.reverse()
Für den GGT gibt es

Code: Alles auswählen

fractions.gcd(a, b)
MfG
HWK
BlackJack

@Kalira: Den Datentyp sollte man möglichst nicht in den Namen stecken. Also all die `*Liste`-Zusätze würde ich weglassen und Namen wie `reste`, `vielfache`, usw. verwenden.

`aList` wird so als Liste nie benötigt, sondern immer nur die einzelnen Elemente. Warum stecken die drei Werte also überhaupt in einer Liste statt sie einzeln an Namen zu binden!? Damit wird der Quelltext viel übersichtlicher.

Bei der Ausgabe böte sich eine ``for``-Schleife anstelle der ``while``-Schleife an. Vielleicht sogar ohne das `i` sondern mit der `zip()`-Funktion gleich über die Elemente der Listen.
nuss
User
Beiträge: 53
Registriert: Donnerstag 28. August 2008, 11:36

@HWK
aber x[::-1] hat einen entscheidenden Vorteil gegenüber x.reverse()
x.reverse() gibt None zurueck und dreht die Liste um, x[::-1] gibt
eine umgedrehte Liste zurueck, dreht die Liste aber nicht um.
Obwohls hier jetzt jetzt keinen Unterschied macht.
BlackJack

@nuss: Der entscheidende "Vorteil" ist keiner. Das die Liste kopiert wird, kann man genauso als Nachteil sehen. Hier macht's keinen Unterschied ausser halt im Speicherverbrauch und der Lesbarkeit, also macht's eigentlich doch wieder einen Unterschied: `list.reverse()` wäre hier IMHO deutlich besser geeignet.
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Hi^^

Vielen Dank für die vielen Meldungen und Vorschläge!
Ich kann mich leider erst morgen darum kümmern, denn ich schreib morgen noch Physik und muss mich erst mal drauf vorbereiten..
ich werde dann mal versuchen mich mit den Funktionen von Python vertraut zu machen.
Kann mir jemand bitte noch erklären wie ich den erweiterten euklidischen Algorithmus zuende schreiben kann?? Also wie ich die Terme für die Reste wiederholt einsetze bis ich wieder eine Aussage über die beiden ursprünglichen Zahlen a und b bekommen???
Dieser Teil zerbricht mir echt den Kopf :wink:

Liebe Grüße
Kalira
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

HWK hat geschrieben:Für den GGT gibt es

Code: Alles auswählen

fractions.gcd(a, b)
So er/sie denn Python > 2.5 hat ... aber selbst dann nützt das nichts: Es geht ja nicht um den einfachen Euklidischen Algorithmus - der ist in einer Zeile schnell programmiert - sondern um den erweiterten Euklidischen Algorithmus und (und das ist das eigentlich anspruchsvolle an der Aufgabe) um eine lesbare Darstellung des ganzen Rechenweges.
Benutzeravatar
Goswin
User
Beiträge: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

Es geht in der Tat etwas kürzer als oben und auch ohne Funktionen:

Code: Alles auswählen

(aa, bb) = (a0, b0) = (481, 253)
(amult_a0, amult_b0) = (0, 1)  #alte Multiplikatoren von a0 und b0
#
(mm,rr) = (aa//bb, aa%bb)  #aa == (aa//bb) * bb + (aa%bb)
(mult_a0, mult_b0) = (1, -mm)  #Multiplikatoren von a0 und b0
#
while bb>1: #FEHLER, RICHTIG IST while rr>0:
  print "%3i = %3i * %3i + %3i   ==>  " %(aa,mm,bb,rr),
  print "%3i = (%3i) * %3i + (%3i) * %3i" %(rr, mult_a0,a0, mult_b0,b0)
  #
  (aa,bb) = (bb,rr)
  (mm,rr) = (aa//bb, aa%bb)
  (nmult_a0, nmult_b0) = (amult_a0-mm*mult_a0, amult_b0-mm*mult_b0)
  #
  (amult_a0, amult_b0) = (mult_a0, mult_b0)
  (mult_a0, mult_b0) = (nmult_a0, nmult_b0)
@Kalira: Mit Hilfe der Tutorials darfst du jetzt versuchen, das zu verstehen :wink:.
Zuletzt geändert von Goswin am Donnerstag 30. April 2009, 07:03, insgesamt 2-mal geändert.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Goswin hat geschrieben:Es geht in der Tat etwas kürzer als oben und auch ohne Funktionen: <Code>
Nur dass die Ausgabe nicht so ist, wie gewünscht und dass dein Code nur bei ausgewählten Werten funktioniert ....

ggt(66, 12) liefert z.B.

Code: Alles auswählen

66 =   5 *  12 +   6   ==>     6 = (  1) *  66 + ( -5) *  12
 12 =   2 *   6 +   0   ==>     0 = ( -2) *  66 + ( 11) *  12
Traceback (most recent call last):
  File "nix-gcd-1.py", line 12, in <module>
    (mm,rr) = (aa//bb, aa%bb)
ZeroDivisionError: integer division or modulo by zero
:cry:

Und wenn kalira ins Tutorial schaut, wird er/sie sich wundern, warum in deinem Code soooooo viele Klammern stehen ... (und: such mal nach divmod())
Benutzeravatar
Goswin
User
Beiträge: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

numerix hat geschrieben:Nur dass die Ausgabe nicht so ist, wie gewünscht und dass dein Code nur bei ausgewählten Werten funktioniert ...
Kalira wird es schon schaffen, die Ausgabe nach ihren Vorgaben zu verändern. Und Flüchtichkeitsfehler im Code werden doch noch erlaubt sein, das macht die Sache so richtig spannend :lol: :

Code: Alles auswählen

(a0, b0) = (481, 253)
(amult_a0, amult_b0) = (0, 1)  #alte Multiplikatoren von a0 und b0
#
(aa,bb) = (a0, b0)
(qq,rr) = divmod(aa,bb)  #aa == qq*bb + rr
(mult_a0, mult_b0) = (1, -qq)  #Multiplikatoren von a0 und b0
#
while rr>0:
  print "%3i = %3i * %3i + %3i   ==>  " %(aa,qq,bb,rr),
  print "%3i = (%4i) * %3i + (%4i) * %3i" %(rr, mult_a0,a0, mult_b0,b0)
  #
  (aa,bb) = (bb,rr)
  (qq,rr) = divmod(aa,bb)
  (nmult_a0, nmult_b0) = (amult_a0-qq*mult_a0, amult_b0-qq*mult_b0)
  #
  (amult_a0, amult_b0) = (mult_a0, mult_b0)
  (mult_a0, mult_b0) = (nmult_a0, nmult_b0)
:mrgreen: Übrigens, was hast du gegen Klammern? Mir wurde gesagt, Python sei eine so kuhle Sprache, weil man fast überall Klammern setzen kann :mrgreen:
derdon
User
Beiträge: 1316
Registriert: Freitag 24. Oktober 2008, 14:32

Wer hat dir das denn erzählt? Und warum benutzt du keine Klammern in Zeile 8, das wäre doch sowas von cool.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Goswin hat geschrieben:
numerix hat geschrieben:Nur dass die Ausgabe nicht so ist, wie gewünscht und dass dein Code nur bei ausgewählten Werten funktioniert ...
Kalira wird es schon schaffen, die Ausgabe nach ihren Vorgaben zu verändern.
Da bin ich ziemlich sicher, dass sie das nicht schaffen wird. :? (Versuch du es doch mal ... ). Wenn ich es richtig aufgenommen habe, dann sollte die Darstellung wohl so aussehen, wie man es z.B. in der Wikipedia findet. Das sähe dann z.B. so aus:

Code: Alles auswählen

1 = 1·25-8·3
  = 1·25-8·(228-9·25) = 73·25-8·228
  = 73·(253-1·228)-8·228 = 73·253-81·228
  = 73·253-81·(481-1·253) = 154·253-81·481
Mit ein bisschen Verändern ist das aber nicht getan. Der Algorithmus muss anders angelegt werden, um das zu erreichen.
Goswin hat geschrieben:Und Flüchtichkeitsfehler im Code werden doch noch erlaubt sein, das macht die Sache so richtig spannend :lol: :
Diese Art von Spannung erschließt sich mir jedenfalls nicht.
Im übrigen funktioniert dein Code für a==b immer noch nicht ... :)
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

derdon hat geschrieben:Und warum benutzt du keine Klammern in Zeile 8, das wäre doch sowas von cool.
Und in 9 und 10 könnte man sicher noch das eine oder andere Klammerpaar reinsetzen.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Benutzeravatar
Goswin
User
Beiträge: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

derdon hat geschrieben:Und warum benutzt du keine Klammern in Zeile 8, das wäre doch sowas von cool.
OK, ich versuche einmal ernstlich, meinen Klammernstil zu erklären, falls euch so etwas wirklich interessieren sollte:
(1) Für MICH hat das Komma (natursprachlich bedingt) eine gaaanz niedrige Bindepräzedenz; wenn also eng zusammengehörende Ausdrücke in Python durch Kommas getrennt werden (müssen), dann setze ich sie immer in Klammern; in Deutschaufsätzen würde ich das Gleiche tun. Also (a,b)=(c,d) statt a,b=c,d.
(2) Außerdem setze ich Klammern, wo sie in einem normalen Mathematikbuch auch stehen würden, also x=a*(-b) anstelle von x=a*-b, und x=(a/b)/c anstelle von x=a/b/c.
Leonidas hat geschrieben:Und in 9 und 10 könnte man sicher noch das eine oder andere Klammerpaar reinsetzen.
Das hat wohl eher mit Python_3.x zu tun, und ich gebe zu dass ich das noch nicht installiert habe. Könnte man im Code-Tag dieses Forums nicht vielleicht zwischen code=py2 und code=py3 unterscheiden?
Python nervt. (Nicht immer, und natürlich nur mich, niemals andere)
Antworten