Erweiterter euklidischer Algorithmus
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
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
OMG, bitte benutz Funktionen !
hier eine kleine Beispiel funktion, die nichts weiter tut, als 2 Zahlen zu addieren und das Ergebniss zurueckzugeben.
diese Funktion ist jetzt vielleicht sinnlos,
aber sollte ja auch nur ein Beispiel sein.
Vielleicht solltest du auch noch 1 oder 2 Tutorials durcharbeiten.
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
aber sollte ja auch nur ein Beispiel sein.
Vielleicht solltest du auch noch 1 oder 2 Tutorials durcharbeiten.
Hi nochmal,
sorry das hatte ich übersehen
1 oder 2 Tutorials können mir mit Sicherheit nicht schaden
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
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 ("--------------------------------------------------------------------")
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
Wenn du eine Liste umdrehen willst kannst du auch
verwenden.
Code: Alles auswählen
>>> x = [1,2,3,4]
>>> x = x[::-1]
>>> x
[4, 3, 2, 1]
>>>
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
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
oh, sorry^^
und Danke Nergal, jetzt ist das ganze nicht mehr sooo lang
Grüße
Kalira
und Danke Nergal, jetzt ist das ganze nicht mehr sooo lang
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 ("--------------------------------------------------------------------")
Kalira
Stattdie wohl etwas lesbarere VarianteFür den GGT gibt esMfG
HWK
Code: Alles auswählen
x = x[::-1]
Code: Alles auswählen
x.reverse()
Code: Alles auswählen
fractions.gcd(a, b)
HWK
@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.
`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.
@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.
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.
@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.
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
Liebe Grüße
Kalira
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
Liebe Grüße
Kalira
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.HWK hat geschrieben:Für den GGT gibt esCode: Alles auswählen
fractions.gcd(a, b)
- 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:
@Kalira: Mit Hilfe der Tutorials darfst du jetzt versuchen, das zu verstehen .
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)
Zuletzt geändert von Goswin am Donnerstag 30. April 2009, 07:03, insgesamt 2-mal geändert.
Nur dass die Ausgabe nicht so ist, wie gewünscht und dass dein Code nur bei ausgewählten Werten funktioniert ....Goswin hat geschrieben:Es geht in der Tat etwas kürzer als oben und auch ohne Funktionen: <Code>
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
Und wenn kalira ins Tutorial schaut, wird er/sie sich wundern, warum in deinem Code soooooo viele Klammern stehen ... (und: such mal nach divmod())
- Goswin
- User
- Beiträge: 363
- Registriert: Freitag 8. Dezember 2006, 11:47
- Wohnort: Ulm-Böfingen
- Kontaktdaten:
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 :numerix hat geschrieben:Nur dass die Ausgabe nicht so ist, wie gewünscht und dass dein Code nur bei ausgewählten Werten funktioniert ...
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)
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:Goswin hat geschrieben:Kalira wird es schon schaffen, die Ausgabe nach ihren Vorgaben zu verändern.numerix hat geschrieben:Nur dass die Ausgabe nicht so ist, wie gewünscht und dass dein Code nur bei ausgewählten Werten funktioniert ...
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
Diese Art von Spannung erschließt sich mir jedenfalls nicht.Goswin hat geschrieben:Und Flüchtichkeitsfehler im Code werden doch noch erlaubt sein, das macht die Sache so richtig spannend :
Im übrigen funktioniert dein Code für a==b immer noch nicht ...
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
Und in 9 und 10 könnte man sicher noch das eine oder andere Klammerpaar reinsetzen.derdon hat geschrieben:Und warum benutzt du keine Klammern in Zeile 8, das wäre doch sowas von cool.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
- Goswin
- User
- Beiträge: 363
- Registriert: Freitag 8. Dezember 2006, 11:47
- Wohnort: Ulm-Böfingen
- Kontaktdaten:
OK, ich versuche einmal ernstlich, meinen Klammernstil zu erklären, falls euch so etwas wirklich interessieren sollte:derdon hat geschrieben:Und warum benutzt du keine Klammern in Zeile 8, das wäre doch sowas von cool.
(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.
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?Leonidas hat geschrieben:Und in 9 und 10 könnte man sicher noch das eine oder andere Klammerpaar reinsetzen.
Python nervt. (Nicht immer, und natürlich nur mich, niemals andere)