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.
yipyip
User
Beiträge: 418
Registriert: Samstag 12. Juli 2008, 01:18

Beitragvon yipyip » Donnerstag 30. April 2009, 20:47

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

:wink:
yipyip
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Donnerstag 30. April 2009, 21:28

Kalira hat geschrieben: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 ...
Benutzeravatar
Dill
User
Beiträge: 470
Registriert: Mittwoch 10. Januar 2007, 14:52
Wohnort: Köln

Beitragvon Dill » Donnerstag 30. April 2009, 21:50

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
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Beitragvon Kalira » Donnerstag 30. April 2009, 21:59

ok^^

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

Bis dann
Kalira
Benutzeravatar
Goswin
User
Beiträge: 361
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen

Beitragvon Goswin » Montag 4. Mai 2009, 18:25

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
Zuletzt geändert von Goswin am Dienstag 5. Mai 2009, 09:07, insgesamt 2-mal geändert.
Python nervt. (Nicht immer, und natürlich nur mich, niemals andere)
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Montag 4. Mai 2009, 19:32

@Goswin:
ggT(60,12) funktioniert z.B. nicht.
Und: Warum ein assert? ggT(253, 481) ist doch ebenso definiert.
Benutzeravatar
Goswin
User
Beiträge: 361
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen

Beitragvon Goswin » Dienstag 5. Mai 2009, 07:43

numerix hat geschrieben: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.

numerix hat geschrieben: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
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Dienstag 5. Mai 2009, 16:11

Goswin hat geschrieben: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


Goswin hat geschrieben: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
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Beitragvon Kalira » Dienstag 5. Mai 2009, 17:11

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
Benutzeravatar
Goswin
User
Beiträge: 361
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen

Beitragvon Goswin » Dienstag 5. Mai 2009, 17:12

@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.
Python nervt. (Nicht immer, und natürlich nur mich, niemals andere)
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Dienstag 5. Mai 2009, 17:31

Kalira hat geschrieben: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
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Beitragvon Kalira » Dienstag 5. Mai 2009, 17:40

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
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Dienstag 5. Mai 2009, 18:21

Kalira hat geschrieben: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.
Benutzeravatar
Dill
User
Beiträge: 470
Registriert: Mittwoch 10. Januar 2007, 14:52
Wohnort: Köln

Beitragvon Dill » Dienstag 5. Mai 2009, 18:30

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
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Beitragvon Kalira » Dienstag 5. Mai 2009, 18:38

numerix hat geschrieben: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...

Wer ist online?

Mitglieder in diesem Forum: redone