Erweiterter euklidischer Algorithmus

[numerix]

Kann bitte jemand das einfach mit mir schritt für schritt durchgehen wie man so eine Erweiterung schreibt??

Wie du in diesem Thread nachlesen kannst, bin ich nicht der einzige, der der Ansicht ist, dass die Aufgabenstellung für dich unter den gegebenen Voraussetzungen eine Überforderung darstellt. Es ehrt dich wirklich, dass du so gewillst bist, das selbst auf die Reihe zu bekommen und keinen fertigen Algorithmus willst, aber es ist eben mit "einfach durchgehen" nicht getan.

Kurz gesagt: Man "schreibt so eine Erweiterung", indem man
- zunächst einmal exakt festlegt, welche Form der Darstellung man gerne hätte;
- den Algorithmus ausreichend analysiert (ich kann das am besten mit Bleistift und Papier - andere haben da sicher andere Präferenzen);
- den Algorithmus dann implementiert, wobei eine Trennung von Logik und Darstellung eine gute Sache ist.

Ich habe es so gemacht, dass ich zunächst den "normalen" Euklidischen Algorithmus durchlaufen lasse und dabei eine Liste mit Quadrupeln derjenigen Werte anlege, die beim Euklidischen Algorithmus Zeile für Zeile anfallen.

Die darin enthaltenen Werte bilden dann die Grundlage für die Darstellung der einzelnen Rechenschritte, und zwar für beide Richtungen.

ABER: Hast du mit deiner Lehrerin gesprochen?

[Kalira]

ja und sie hat mir gesagt, da ich keine informatikfacharbeit schreibe wäre es auch in ordnung wenn das Programm den Rechenweg nur so weit darstellt wie es halt jetzt funktioniert und mir dann einfach das Ergebnis gibt...
Also ich muss das jetzt nicht mehr so darstellen, dass er für jede Zeile zeigt wie die Terme für die Reste eingesetzt werden...
Aber ich weiß trotzdem einfach nicht wie ich das Programm schreiben soll... auch wenn der Computer es jetzt halt im Hintergrund berechnen soll....

Liebe Grüße
Kalira

[numerix]

Aber ich weiß trotzdem einfach nicht wie ich das Programm schreiben soll... auch wenn der Computer es jetzt halt im Hintergrund berechnen soll....

Dann nimm doch einfach die gepostete Lösung von yipyip - die liefert doch (u.a.) das von dir gewünschte Endergebnis.

[Dill]

das schöne am erweiterten euklid ist doch, dass du dir keine gedanken über den algorithmus machen musst, dass hat euklid doch schon getan.
nimm einfach einen fertigen pseudocode und implementiere den in python.

[Kalira]

Dann nimm doch einfach die gepostete Lösung von yipyip - die liefert doch (u.a.) das von dir gewünschte Endergebnis.

Naja, das Problem ist einfach nur ich will nicht einfach etwas übernehmen.. ich will es verstehen! sonst bin ich nachher bei meiner Lehrerin aufgeschmissen...

[Hyperion]

Dann nimm doch einfach die gepostete Lösung von yipyip - die liefert doch (u.a.) das von dir gewünschte Endergebnis.

Naja, das Problem ist einfach nur ich will nicht einfach etwas übernehmen.. ich will es verstehen! sonst bin ich nachher bei meiner Lehrerin aufgeschmissen...

Wo genau liegt denn jetzt das Problem? Beim Verständnis von Python oder beim Verständnis des Algos?

[Kalira]

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:

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 ("--------------------------------------------------------------------")

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

[Hyperion]

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 ...

[Dill]

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:

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)

[yipyip]

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

[Kalira]

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!

[yipyip]

Um Missverständnissen vorzubeugen:
Mein Programm macht keine Termersetzung
wie bei Numerix:

Du erhältst bei mir eine Augabe der Form:

> 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

Hatte das jetzt so verstanden, dass Dir diese
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

[Hyperion]

@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]

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:

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

Viel Vergnügen beim Entziffern!

[derdon]

Zeile 24 und 38 würdest du so lassen? Die stechen mir beim Überfliegen als erstes ins Auge.

[Goswin]

Zeile 24 und 38 würdest du so lassen? Die stechen mir beim Überfliegen als erstes ins Auge.

Ich denke, das sollen sie doch gerade!

[derdon]

So kann man es natürlich auch sehen. Ich meinte, das mir bei den Zeilen sofort etwas wie

Code: Alles auswählen

print('-' * 68)

einfiel.

[Dill]

ich habe mal den rekursiven algo implementiert.
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)

[BlackJack]

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

[Dill]

wow, sehr hübsch! was es nicht alles gibt.
richtig sexy langsam der code