Wo genau liegt denn jetzt das Problem? Beim Verständnis von Python oder beim Verständnis des Algos?Kalira hat geschrieben:Naja, das Problem ist einfach nur ich will nicht einfach etwas übernehmen.. ich will es verstehen! sonst bin ich nachher bei meiner Lehrerin aufgeschmissen...numerix hat geschrieben:Dann nimm doch einfach die gepostete Lösung von yipyip - die liefert doch (u.a.) das von dir gewünschte Endergebnis.
Erweiterter euklidischer Algorithmus
- Hyperion
- Moderator
- Beiträge: 7478
- Registriert: Freitag 4. August 2006, 14:56
- Wohnort: Hamburg
- Kontaktdaten:
den Algorithmus kann ich ja man rechnet einfach den größten gemeinsamen Teiler von a und b raus.. formt alle Gleichungen zum Rest um und setzt dann die jeweiligen Zahlen die man in der ersten Gleichung also 1 = ... sieht durch vorherige Terme der Reste ein und das macht man so lange bis man wieder ne aussage hat von 1 = (irgendeine Zahl) * a - (irgnedeineZahl)*b
aber wie programmiere ich das ???? das ist das Problem ich kann mir das gar nicht vorstellen...
Bis jetzt sieht es ja so aus:
und es funktioniert auch für jede erdenkbare natürliche Zahl... also es rechnet mir den ggT aus und formt zu den Resten um...
nur jetzt weiß ich nicht mehr weiter
also das Programm muss mir ja jetzt nicht mehr die Rechenschritte angeben er soll mir jetzt einfach nur diese 2 Zahlen berechnen mit denen man a und b multipliziert und dann durch eine Subtraktion den Wert 1 der Gleichung erhält...
kannst du mir bitte einfach schritt für schritt erklären wie man das macht???
also erstmal wie man die schleife begrenzt und dann wie man dem Programm den Befehl gibt vorherige Zeilen einzusetzen...
für die größere Zahl, (also die ohne dem Minuszeichen) muss man ja stets den Term einsetzen der vor zwei Gleichungen berechnet wurde... für die vielfach Zahl, (also die Zahl mit dem Minuszeichen) muss man den Term in der nächsten Gleichung einsetzen...
also ist es für modul immmer i+2 und für vielfach stets i+1....
kann man das verwenden?
Liebe Grüße
Kalira
aber wie programmiere ich das ???? das ist das Problem ich kann mir das gar nicht vorstellen...
Bis jetzt sieht es ja so aus:
Code: Alles auswählen
a = 187
b = 115
c = a%b
modul = []
vielfach = []
rest = []
multi = []
while c > 0:
print (a, "=", a//b, "*", b, "+", c)
modul.append(a)
vielfach.append(b)
multi.append(a//b)
rest.append(c)
a = b
b = c
c = a%b
if a%b == 0:
break
print ("--------------------------------------------------------------------")
rest.reverse()
modul.reverse()
vielfach.reverse()
multi.reverse()
i = 0
while len(rest) > i:
print (rest[i], "=", modul[i], "-", multi[i], "*", vielfach[i])
i = i + 1
print ("--------------------------------------------------------------------")
nur jetzt weiß ich nicht mehr weiter
also das Programm muss mir ja jetzt nicht mehr die Rechenschritte angeben er soll mir jetzt einfach nur diese 2 Zahlen berechnen mit denen man a und b multipliziert und dann durch eine Subtraktion den Wert 1 der Gleichung erhält...
kannst du mir bitte einfach schritt für schritt erklären wie man das macht???
also erstmal wie man die schleife begrenzt und dann wie man dem Programm den Befehl gibt vorherige Zeilen einzusetzen...
für die größere Zahl, (also die ohne dem Minuszeichen) muss man ja stets den Term einsetzen der vor zwei Gleichungen berechnet wurde... für die vielfach Zahl, (also die Zahl mit dem Minuszeichen) muss man den Term in der nächsten Gleichung einsetzen...
also ist es für modul immmer i+2 und für vielfach stets i+1....
kann man das verwenden?
Liebe Grüße
Kalira
- Hyperion
- Moderator
- Beiträge: 7478
- Registriert: Freitag 4. August 2006, 14:56
- Wohnort: Hamburg
- Kontaktdaten:
Also an Deinem Code zumzudoktern bringt irgend wie nicht viel imho. Kannst Du mir mal nen Link zu dem Algo posten? Um welchen genau handelt es sich? Bei wikipedia finde ich nichts, was so auf Anhieb zu Deinem Code passt
Generell denke ich, dass mathematische Probleme sich i.a. sehr schön für den Programmier-Einstieg eignen, da häufig stark aus dem Pseudo-Code hervorgehen und diesem extrem ähneln. Außerdem sind mathematische Operatoren am Anfang auch meist eher verständlich, als andere ...
Generell denke ich, dass mathematische Probleme sich i.a. sehr schön für den Programmier-Einstieg eignen, da häufig stark aus dem Pseudo-Code hervorgehen und diesem extrem ähneln. Außerdem sind mathematische Operatoren am Anfang auch meist eher verständlich, als andere ...
du versuchst die "stift und papier" variante des algos in ein programm zu pressen. will man einen algorithmus implementieren nimmt man sich den pseudocode her und implementiert den.
eweiterter euklid:
rekursiv:
eweiterter euklid:
Code: Alles auswählen
b0 = b
n0 = n
t0 = 0
t = 1
q = n0 / b0 (abgerundet)
r = n0 - q * b0
while r > 0 do
temp = t0 - q * t
if temp >= 0 then temp = temp mod n
if temp < 0 then temp = n - (( -temp) mod n)
t0 = t
t = temp
n0 = b0
b0 = r
q = n0 / b0 (abgerundet)
r = n0 - q * b0
if b0 != 1 then
b hat kein Inverses modulo n
else
b-1 = t mod n
rekursiv:
Code: Alles auswählen
extended_euclid(a,b)
wenn b = 0
dann return (a,1,0)
(d',s',t') = extended_euclid(b, a mod b)
(d,s,t) = (d',t',s' - floor(a/b)t')
return (d,s,t)
http://www.kinderpornos.info
Hallo Kalira,
schau Dir (noch)mal den 1. Algorithmus aus dem
Wikipedia Artikel an.
http://de.wikipedia.org/wiki/Erweiterte ... lgorithmus
(Rekursive Variante, aber keine Angst, rekursive Algorithmen
kommen bei der Berechnung nicht vor.)
Versuche, mit Bleistift und Papier diesen Algorithmus anhand
einiger Zahlenbeispiele nachzuvollziehen.
Dann solltest Du dich etwas vertraut mit Listen und Tupeln machen
und was man mit ihnen so alles in Python anstellen kann.
Danach schau Dir nochmal den Kern meines Programmes,
die Funktion 'get_ggt_equations()', an und versuche, den
Wikipedia-Algorithmus wiederzuerkennen.
Wenn Dir das dann alles etwas klarer wird, kannst Du
ja nochmal versuchen, es eigenständig zu implementieren.
(Das ist das, wozu ich Dir momentan raten würde.)
yipyip
schau Dir (noch)mal den 1. Algorithmus aus dem
Wikipedia Artikel an.
http://de.wikipedia.org/wiki/Erweiterte ... lgorithmus
(Rekursive Variante, aber keine Angst, rekursive Algorithmen
kommen bei der Berechnung nicht vor.)
Versuche, mit Bleistift und Papier diesen Algorithmus anhand
einiger Zahlenbeispiele nachzuvollziehen.
Dann solltest Du dich etwas vertraut mit Listen und Tupeln machen
und was man mit ihnen so alles in Python anstellen kann.
Danach schau Dir nochmal den Kern meines Programmes,
die Funktion 'get_ggt_equations()', an und versuche, den
Wikipedia-Algorithmus wiederzuerkennen.
Wenn Dir das dann alles etwas klarer wird, kannst Du
ja nochmal versuchen, es eigenständig zu implementieren.
(Das ist das, wozu ich Dir momentan raten würde.)
yipyip
Hi Leute,
Also was die mathematik angeht, so hab ich das verstanden, ich habs ja schon an ein paar Beispielen auf einem Blatt papier durchprobiert... also das ist kein Problem... mein Problem ist einfach nur, dass ich ganz ehrlich keine Ahnung von informatik habe .. ich meine ich hatte es nie in der Schule und ich hab auch nie jemanden gehabt der mir mal so sachen über informatik erklärt hat oder mir gezeigt hat wie man das macht.. ich hab einfach nur internet seiten verwendet und logisch überlegt... nur jetzt hab ich einfach keine Zeit mehr um das so weiter zu machen denn ich muss schon nächste Woche Freitag abgeben und muss noch einen haufen dazu schreiben....
Also vielen Dank für die vielen Lösungen aber ich verstehe sie einfach nicht... wenn ich da so einen code bekomme dann blicke ich nicht durch weil ich so viele Abkürzungen nicht verstehe und so weiter...
daher yipyip kannst du mir bitte einfach nur den Teil raussuchen, der die wirkliche Erweiterung ist... also den Teil wo du dem Programm sagst, dass es die einzelnen Zahlen durch vorherberechnete Terme ersetzen soll...
und wenn es dir nichts ausmacht, dann kannst du mir bitte einfach nur jeden Schritt dazu erklären?? Also wie man darauf kommt, wie man anfängt, worauf man achten muss und so???? und vielleicht einfach nur in Wörtern dahinter schreibst was das Programm jetzt durch diesen Befehl machen soll....Denn sonst kann ich dir wirklich nicht mehr folgen
Vielen, vielen Dank
und liebe Grüße
Kalira
PS: ich kann leider erst wieder morgen schreiben!
Also was die mathematik angeht, so hab ich das verstanden, ich habs ja schon an ein paar Beispielen auf einem Blatt papier durchprobiert... also das ist kein Problem... mein Problem ist einfach nur, dass ich ganz ehrlich keine Ahnung von informatik habe .. ich meine ich hatte es nie in der Schule und ich hab auch nie jemanden gehabt der mir mal so sachen über informatik erklärt hat oder mir gezeigt hat wie man das macht.. ich hab einfach nur internet seiten verwendet und logisch überlegt... nur jetzt hab ich einfach keine Zeit mehr um das so weiter zu machen denn ich muss schon nächste Woche Freitag abgeben und muss noch einen haufen dazu schreiben....
Also vielen Dank für die vielen Lösungen aber ich verstehe sie einfach nicht... wenn ich da so einen code bekomme dann blicke ich nicht durch weil ich so viele Abkürzungen nicht verstehe und so weiter...
daher yipyip kannst du mir bitte einfach nur den Teil raussuchen, der die wirkliche Erweiterung ist... also den Teil wo du dem Programm sagst, dass es die einzelnen Zahlen durch vorherberechnete Terme ersetzen soll...
und wenn es dir nichts ausmacht, dann kannst du mir bitte einfach nur jeden Schritt dazu erklären?? Also wie man darauf kommt, wie man anfängt, worauf man achten muss und so???? und vielleicht einfach nur in Wörtern dahinter schreibst was das Programm jetzt durch diesen Befehl machen soll....Denn sonst kann ich dir wirklich nicht mehr folgen
Vielen, vielen Dank
und liebe Grüße
Kalira
PS: ich kann leider erst wieder morgen schreiben!
Um Missverständnissen vorzubeugen:
Mein Programm macht keine Termersetzung
wie bei Numerix:
Du erhältst bei mir eine Augabe der Form:
Art der Ausgabe, also ohne Termersetzung,
prinzipiell ausreicht.
Der für Dich wichtige Teil steht in
'get_ggt_equations()', der die Faktoren
für die obigen letzten 5 Gleichungen liefert.
(Ich mache Dir dann in Kürze noch eine
genau kommentierte Version.)
yipyip
Mein Programm macht keine Termersetzung
wie bei Numerix:
Du erhältst bei mir eine Augabe der Form:
Hatte das jetzt so verstanden, dass Dir diese> ggt.py 1234 24
Euclid Equations:
1234 = 24 * 51 + 10
24 = 10 * 2 + 4
10 = 4 * 2 + 2
4 = 2 * 2 + 0
Rest Equations:
0 = 4 - 2 * 2
2 = 10 - 2 * 4
4 = 24 - 2 * 10
10 = 1234 - 51 * 24
ggt Equations:
2 = 1 * 2 + 0 * 0
2 = 0 * 4 + 1 * 2
2 = 1 * 10 - 2 * 4
2 = -2 * 24 + 5 * 10
2 = 5 * 1234 - 257 * 24
Art der Ausgabe, also ohne Termersetzung,
prinzipiell ausreicht.
Der für Dich wichtige Teil steht in
'get_ggt_equations()', der die Faktoren
für die obigen letzten 5 Gleichungen liefert.
(Ich mache Dir dann in Kürze noch eine
genau kommentierte Version.)
yipyip
Zuletzt geändert von yipyip am Mittwoch 6. Mai 2009, 20:08, insgesamt 1-mal geändert.
- Hyperion
- Moderator
- Beiträge: 7478
- Registriert: Freitag 4. August 2006, 14:56
- Wohnort: Hamburg
- Kontaktdaten:
@Kalira: Wieso machst Du denn bitte schön eine Programmieraufgabe, wenn Du davon keine Ahnung hast und auch keine Vorbildung? Zudem wenn die eigentlich Aufgabe über das simple Implementieren des Algos hinausgeht? Evtl. wäre es da geschickter, das Thema noch zu wechseln ...
- Goswin
- User
- Beiträge: 363
- Registriert: Freitag 8. Dezember 2006, 11:47
- Wohnort: Ulm-Böfingen
- Kontaktdaten:
Hallo Kalira,
Dein unvollendetes Programm, welches immerhin glatt durchläuft und die richtigen Ergebnisse liefert, finde ich für eine(n) Anfänger(in) sehr ordentlich. Man braucht auch gar keine tiefgehende Python-Kenntnisse, um es zu vollenden; ich bin da nicht der Meinung einiger anderer Forumsteilnehmer. (Aber dem Mathematikeer ist ja nichts zu schwer) Die meisten Vorschläge im folgenden Code, den ich dir mit kollegialen Grüßen zusende, sind reine Schönheitskorrekturen:
Viel Vergnügen beim Entziffern!
Dein unvollendetes Programm, welches immerhin glatt durchläuft und die richtigen Ergebnisse liefert, finde ich für eine(n) Anfänger(in) sehr ordentlich. Man braucht auch gar keine tiefgehende Python-Kenntnisse, um es zu vollenden; ich bin da nicht der Meinung einiger anderer Forumsteilnehmer. (Aber dem Mathematikeer ist ja nichts zu schwer) Die meisten Vorschläge im folgenden Code, den ich dir mit kollegialen Grüßen zusende, sind reine Schönheitskorrekturen:
Code: Alles auswählen
(a,b) = (187,115) #Vorschlag
assert a%b>0 #Trivialfaelle verbleiben als Hausaufgabe
c = a%b
modul = []
vielfach = []
rest = []
multi = []
while c > 0:
# print (a, "=", a//b, "*", b, "+", c) #unschoen bei Python_2.x
# print a, "=", a//b, "*", b, "+", c #falsch bei Python_3.x
# print( "%i = %i * %i + %i" %(a, a//b, b, c) ) #Vorschlag_1
print( "%3i = %3i * %3i + %3i" %(a, a//b, b, c) ) #Vorschlag_2
modul.append(a)
vielfach.append(b)
multi.append(a//b)
rest.append(c)
a = b
b = c
c = a%b
if a%b == 0:
break
print ("--------------------------------------------------------------------")
#Vorsicht: folgende Listen sind leer falls b%a==0 gilt!
rest.reverse()
modul.reverse()
vielfach.reverse()
multi.reverse()
i = 0
while len(rest) > i:
# print (rest[i], "=", modul[i], "-", multi[i], "*", vielfach[i])
print("%3i = %3i - %3i * %3i" %(rest[i],modul[i],multi[i],vielfach[i])) #V
i = i + 1
print ("--------------------------------------------------------------------")
ggn = rest[0]
(multA,zahlA, multB,zahlB) = (0,0, 1,ggn)
i = 0
while len(rest) > i:
#Tupel werden komponentenweise zugewiesen:
( multA, zahlA, multB, zahlB ) = (
multB, modul[i], multA-multB*multi[i], vielfach[i] )
print("%3i = (%3i) * %3i + (%3i) * %3i" %(ggn, multA,zahlA, multB,zahlB))
i = i + 1
Zuletzt geändert von Goswin am Donnerstag 7. Mai 2009, 08:37, insgesamt 2-mal geändert.
So kann man es natürlich auch sehen. Ich meinte, das mir bei den Zeilen sofort etwas wieeinfiel.
Code: Alles auswählen
print('-' * 68)
ich habe mal den rekursiven algo implementiert.
vorteil: hier kann man viel natürlicher die rechenschritte darstellen.
nachteil: evtl. schwer verdaulich, da rekursiv.
vorteil: hier kann man viel natürlicher die rechenschritte darstellen.
nachteil: evtl. schwer verdaulich, da rekursiv.
Code: Alles auswählen
def extended_euclid(a, b):
if b == 0:
print "\nggT: %d\nFinde jetzt Linearkombination des ggT aus Ausgangszahlen:\n" % a
return a, 1, 0
else:
print "%(a)d = %(faktor)d * %(b)d + %(a_mod_b)d" % {"a":a, "faktor":a/b, "b":b, "a_mod_b":a%b}
d_, s_, t_ = extended_euclid(b, a % b)
d, s, t = d_, t_, s_ - (a/b) * t_
print("%(d)d = %(s)d * %(a)d + %(t)d * %(b)d") % {"d":d, "s":s, "a":a, "t":t, "b":b}
return d, s, t
Code: Alles auswählen
>>> extended_euclid(99, 78)
99 = 1 * 78 + 21
78 = 3 * 21 + 15
21 = 1 * 15 + 6
15 = 2 * 6 + 3
6 = 2 * 3 + 0
ggT: 3
Finde jetzt Linearkombination des ggT aus Ausgangszahlen:
3 = 0 * 6 + 1 * 3
3 = 1 * 15 + -2 * 6
3 = -2 * 21 + 3 * 15
3 = 3 * 78 + -11 * 21
3 = -11 * 99 + 14 * 78
(3, -11, 14)
http://www.kinderpornos.info
Verbesserungsvorschlag für's einsetzen der Werte in die Zeichenketten:
Code: Alles auswählen
def extended_euclid(a, b):
if b == 0:
print ('\nggT: %d\n'
'Finde jetzt Linearkombination des ggT aus Ausgangszahlen:\n'
% a)
return a, 1, 0
else:
faktor, a_mod_b = divmod(a, b)
print '%(a)d = %(faktor)d * %(b)d + %(a_mod_b)d' % locals()
d_, s_, t_ = extended_euclid(b, a % b)
d, s, t = d_, t_, s_ - (a/b) * t_
print '%(d)d = %(s)d * %(a)d + %(t)d * %(b)d' % locals()
return d, s, t
- Goswin
- User
- Beiträge: 363
- Registriert: Freitag 8. Dezember 2006, 11:47
- Wohnort: Ulm-Böfingen
- Kontaktdaten:
my cody isch nosch mehr sexxi:
Code: Alles auswählen
def extended_euclid(a, b):
#liefert (ggt, mul_a, mul_b) mit ggt==mul_a*a+mul_b*b
if b==0:
print( "\nggT = %(a)d" %vars() )
print( "Linearkombination des ggT aus Ausgangszahlen:\n" )
#
return (a, 1, 0) #a==1*a+0*b
else:
(faktor, rest) = divmod(a,b) #a==faktor*b+rest
print( "%(a)4d = %(faktor)4d * %(b)4d + %(rest)4d"%vars() )
#
(ggt, inn_mul_a, inn_mul_b) = extended_euclid(b, rest) #innere mul
(mul_a, mul_b) = (inn_mul_b, inn_mul_a-faktor*inn_mul_b)
print("%(ggt)4d = (%(mul_a)4d) * %(a)4d + (%(mul_b)4d) * %(b)4d"%vars())
#
return (ggt, mul_a, mul_b) #ggt==mul_a*a+mul_b*b
(a,b) = (374, 230)
extended_euclid(a, b)
mehr rundungen hat deiner auf jeden fall
ich steh aber auf weniger üppig.
in meiner neuen version verschwinden jetzt die hilfsberechnungen in print() und trüben so nicht den blick auf den eigentlichen algo
(und: ich bleibe bei den namen aus der wikipedia wo ich den algo herhabe)
ich steh aber auf weniger üppig.
in meiner neuen version verschwinden jetzt die hilfsberechnungen in print() und trüben so nicht den blick auf den eigentlichen algo
(und: ich bleibe bei den namen aus der wikipedia wo ich den algo herhabe)
Code: Alles auswählen
def extended_euclid(a, b):
if b == 0:
print('\nggT: %d\nggT:= Linearkombination(Ausgangszahlen):\n' % a)
return a, 1, 0
else:
print('%(a)d = %(faktor)d * %(b)d + %(a_mod_b)d'
% dict({"faktor":a/b, "a_mod_b":a%b}, **locals())
)
d_, s_, t_ = extended_euclid(b, a % b)
d, s, t = d_, t_, s_ - (a/b) * t_
print('%(d)d = %(s)d * %(a)d + %(t)d * %(b)d' % locals())
return d, s, t
http://www.kinderpornos.info
Hi Leute^^
Also erst mal danke für die Verbesserungsvorschläge und Dill, versteh mich nicht falsch aber ich glaub ich verstehe den Algo von Goswin etwas besser
Also Danke ich hab das jetzt auch ein bisschen schöner gemacht, so dass es jetzt so aussieht:
und vielen Dank yipyip, jetzt hab ich endlich mal verstanden, was du die ganze Zeit mit Wikipedia gemeint hast.. ich hab das gar nicht gesehen, dass die das so da berechnet haben!
Also es funktioniert jetzt endlich
und es sieht hoffentlich nicht mehr alzu "unschön" aus
Liebe Grüße
Kalira
Also erst mal danke für die Verbesserungsvorschläge und Dill, versteh mich nicht falsch aber ich glaub ich verstehe den Algo von Goswin etwas besser
Also Danke ich hab das jetzt auch ein bisschen schöner gemacht, so dass es jetzt so aussieht:
Code: Alles auswählen
a = 9013
b = 1556
g = a
h = b
c = a%b
modul = []
vielfach = []
rest = []
multi = []
while c > 0:
print ("%d = %d * %d + %d" % (g, g//h, h, c))
modul.append(g)
vielfach.append(h)
multi.append(g//h)
rest.append(c)
g = h
h = c
c = g%h
if g%h == 0:
break
print ("--------------------------------------------------------------------")
rest.reverse()
modul.reverse()
vielfach.reverse()
multi.reverse()
i = 0
while len(rest) > i:
print ("%d = %d * %d + %d" % (rest[i], modul[i], multi[i], vielfach[i]))
i = i + 1
print ("--------------------------------------------------------------------")
g = a
h = b
def extgcd(a, b):
c=b
u=1
s=0
while b>0:
q=a//b
a, b = b, a-q*b
u, s = s, u-q*s
if u < 0:
u = u + c
return u
d = extgcd(h, g)
print ("d = ", extgcd(h, g))
print ("b = ", b)
print ("a = ", a)
print ("(d * b) % a = ", (d*b)%a)
Also es funktioniert jetzt endlich
und es sieht hoffentlich nicht mehr alzu "unschön" aus
Liebe Grüße
Kalira
- Goswin
- User
- Beiträge: 363
- Registriert: Freitag 8. Dezember 2006, 11:47
- Wohnort: Ulm-Böfingen
- Kontaktdaten:
Aha, BAHNHOF!
@Kalira: Deine Aufgabestellung (was dein extgcd(a,b) ausgibt) ist offenbar NICHT, was andere Leute unter dem "Erweiterten Euklidschen Algorithmus" verstehen, sie geht wohl mehr in Richtung eines "Mysteriösen Kaliraschen Algorithmus".
Ich denke, die Forumsteilnehmer haben nach all diesem Aufwand schon ein Recht auf eine mathematische Beschreibung von was GENAU du die ganze Zeit über gesucht hast; dazu brauchst du ja kein Python, nur Deutsch und Mathe. Du wolltest lineare Ausdrücke in andere lineare Ausdrücke einsetzen, aber MIT WELCHEM ZIEL? Nur Python lernen war es wohl auch nicht auch nicht so ganz.
@Kalira: Deine Aufgabestellung (was dein extgcd(a,b) ausgibt) ist offenbar NICHT, was andere Leute unter dem "Erweiterten Euklidschen Algorithmus" verstehen, sie geht wohl mehr in Richtung eines "Mysteriösen Kaliraschen Algorithmus".
Ich denke, die Forumsteilnehmer haben nach all diesem Aufwand schon ein Recht auf eine mathematische Beschreibung von was GENAU du die ganze Zeit über gesucht hast; dazu brauchst du ja kein Python, nur Deutsch und Mathe. Du wolltest lineare Ausdrücke in andere lineare Ausdrücke einsetzen, aber MIT WELCHEM ZIEL? Nur Python lernen war es wohl auch nicht auch nicht so ganz.
Meine Euclid()-Implementation liefert für
diese Ausgabe:
Da weiß man wenigstens, was man hat ...
Code: Alles auswählen
e = Euclid(9013, 1556)
print e.steps
print e.extended
Code: Alles auswählen
9013 = 5·1556+1233
1556 = 1·1233+323
1233 = 3·323+264
323 = 1·264+59
264 = 4·59+28
59 = 2·28+3
28 = 9·3+1
3 = 3·1+0
1 = 1·28-9·3
= 1·28-9·(59-2·28) = 19·28-9·59
= 19·(264-4·59)-9·59 = 19·264-85·59
= 19·264-85·(323-1·264) = 104·264-85·323
= 104·(1233-3·323)-85·323 = 104·1233-397·323
= 104·1233-397·(1556-1·1233) = 501·1233-397·1556
= 501·(9013-5·1556)-397·1556 = 501·9013-2902·1556