Erweiterter euklidischer Algorithmus

[yipyip]

Ok, ich hatte nur Wert darauf gelegt, dass die Operanden immer an
der gleichen Stelle stehen, damit man sieht, wie die Gleichungen
auf die Lösung
ggt(a, b) = s*a + t*b
"zuwandern".


yipyip

[numerix]

Wenn ich dein Programm bei Python mal ausprobiere krieg ich folgende Fehlermeldung :

Code: Alles auswählen

Traceback (most recent call last):
  File "C:/Python30/von nummerix.py", line 1, in <module>
    e = Euclid(481,253)
NameError: name 'Euclid' is not defined

muss ich davor irgendetwas importieren???

Naja, du brauchst halt meine Klasse Euclid ... aber den Code dazu habe ich ja absichtlich nicht gepostet, weil ich noch nicht weiß, wie es mit der Geschichte weitergeht ...

[Dill]

ich finde die aufgabe deutlich zu anspruchsvoll für eine facharbeit.

kläre mit deiner lehrerin, dass du den aufwand für die version mit ausgabe des rechenweges unterschätzt hast und liefere ihr eine gut dokumentierte (standard-)implementierung des algorithmus.

[Kalira]

ok^^

ich hab ihr auch schon geschrieben aber noch keine Antwort daher bin ich mal gespannt
Froher Maifeiertag an alle

Bis dann
Kalira

[Goswin]

Der folgende Code "setzt wiederholt Terme für den Rest ein" ; wie man die Ergebnisse dann ausdruckt, ist wohl Geschmackssache. Die Namensgebung der Variablen ist wahrscheinlich nicht optimal, aber das ist ja leicht zu ändern. Natürlich ist das Ganze auch ohne Klassen und Methoden zu machen, aber dann ist es halt weniger elegant...

Code: Alles auswählen

class Link(object):
  #affin-LINearer AusdrucK :-)
  #
  def __init__(link,fvar,linfun):
    #fvar == sum(mult*key for (key,mult) in linfun.items())
    link.fvar = fvar #int
    link.linfun = linfun #dict
  #
  def __str__(link):
    _linkrep = "%3i =" %link.fvar
    (var,mult) =  link.linfun.items()[0]
    _linkrep += " (%4i) * %3i " %(mult,var)
    for (var,mult) in link.linfun.items()[1:]:
      _linkrep += "+ (%4i) * %3i " %(mult,var)
    return _linkrep
  #
  def frei_von(link,unterlink):
    mult = link.linfun.pop(unterlink.fvar)
    _nlinfun = link.linfun.copy()
    for var in unterlink.linfun:
      _nlinfun.setdefault(var,0)
      _nlinfun[var] += mult * unterlink.linfun[var]
    return Link(link.fvar,_nlinfun)


print
(a0, b0) = (962, 506)
#(a0, b0) = ( 66,  18)
#
(aa,bb) = (int(a0),int(b0))
assert a0>b0>0  #BESSER: assert (a0%b0)>0
rrlinks = []
while True:
  (qq,rr) = divmod(aa,bb)
  if rr==0: break
  print "%3i = %3i * %3i + %3i" %(aa,qq,bb,rr)
  rrlinks.append(Link(rr,{aa:1,bb:-qq}))
  (aa,bb) = (bb,rr)
#
print
rrlinks.reverse()
_rrkum = rrlinks.pop(0)
print "GGN(%i,%i) ="%(a0,b0), _rrkum
#
for rrlink in rrlinks:
  print rrlink, "==>",
  _rrkum = _rrkum.frei_von(rrlink)
  print _rrkum

[numerix]

@Goswin:
ggT(60,12) funktioniert z.B. nicht.
Und: Warum ein assert? ggT(253, 481) ist doch ebenso definiert.

[Goswin]

ggT(60,12) funktioniert z.B. nicht.

Danke für den Hinweis. Ja, testen will eben gelernt sein! Ich wüsste freilich nicht, was für eine Ausgabe beim ERWEITERTEN euklidschen Algorithmus in so einem Sonderfall erwünscht ist.

Und: Warum ein assert? ggT(253, 481) ist doch ebenso definiert.

Am besten erlegen wir zwei Fliegen auf einen Schlag und ersetzen das obige assert durch:

Code: Alles auswählen

assert (a0%b0)>0

[numerix]

Ich wüsste freilich nicht, was für eine Ausgabe beim ERWEITERTEN euklidschen Algorithmus in so einem Sonderfall erwünscht ist.

Ich habe mich dafür entschieden:

Code: Alles auswählen

e = Euclid(60, 12)
print e.extended

Liefert

Code: Alles auswählen

12 = 1·60-4·12

Am besten erlegen wir zwei Fliegen auf einen Schlag und ersetzen das obige assert durch:

Code: Alles auswählen

assert (a0%b0)>0

Das verstehe ich jetzt nicht. Zum einen kannst du damit nicht zusichern, dass a > b ist (so habe ich dich jedenfalls verstanden; oder ging es um eine andere 2. Fliege?) und zum anderen gibt es dafür keinen Grund.
Warum sollte z.B. ggT(321, 172) erlaubt sein, ggT(172, 321) aber nicht? Vielmehr sollte man in beiden Fällen das gleiche Ergebnis erwarten.

[Kalira]

Hi Leute:)

Wow, sag ich dazu erstmal, also da brauch ich ein bisschen zum durchlesen.
Merci beaucoup!

also vielen Dank für die Mühe aber kannst du mir vielleicht auch erklären wie du das geschrieben hast??? Also eigentlich möchte ich gar keinen vollständig geschriebenen Algorithmus ich würde gerne meinen weiter schreiben nur ich hab keine Ahnung wie...
also kann mir jemand erklären wie man so etwas anfängt, also halt schritt für schritt das mit mir durchgeht??
Also zuerst wäre da mal meine Frage wie ich da die Schleife begrenze... ich weiß ja nicht wie viele Zeilen mein Gleichungssystem von zwei beliebigen Zahlen im Endeffekt haben wird... und dann weiß ich auch nicht wie man dem Programm sagt, dass es die ehemaligen Restwerte nicht einfach verwerfen soll, sondern bis zum Schluss mitziehen soll... und dann weiß ich auch nicht wie man es verhindert, dass er nicht einfach die ganze Gleichung ausrechnet.. dann würden mir ja die Rest-Werte verloren gehen und ich könnte sie nicht mehr ersetzen lassen....
Kann bitte jemand das einfach mit mir schritt für schritt durchgehen wie man so eine Erweiterung schreibt??

Liebe Grüße
Kalira

[Goswin]

@numerix:
Ich schließe mit (a0%b0)>0 alle Fälle aus, für welche (1) mein Algorthmus abstürzt, und das sind alles Fälle, für welche (2) ich nicht wusste, welche Ausgabe gewünscht war. Für Ausreißer wie (12,60) funktioniert der Algorithmus; das war nicht geplant, tut aber auch nicht weh. Es geht mir hier nur um Denkanstöße für Kalira; dein Euclid-Modul ist sicher viel ausgefeilter.

[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