Seite 3 von 5

Verfasst: Donnerstag 30. April 2009, 20:47
von 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".

:wink:
yipyip

Verfasst: Donnerstag 30. April 2009, 21:28
von numerix
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 ...

Verfasst: Donnerstag 30. April 2009, 21:50
von 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.

Verfasst: Donnerstag 30. April 2009, 21:59
von Kalira
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

Verfasst: Montag 4. Mai 2009, 18:25
von 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

Verfasst: Montag 4. Mai 2009, 19:32
von numerix
@Goswin:
ggT(60,12) funktioniert z.B. nicht.
Und: Warum ein assert? ggT(253, 481) ist doch ebenso definiert.

Verfasst: Dienstag 5. Mai 2009, 07:43
von Goswin
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

Verfasst: Dienstag 5. Mai 2009, 16:11
von numerix
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.

Verfasst: Dienstag 5. Mai 2009, 17:11
von 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

Verfasst: Dienstag 5. Mai 2009, 17:12
von 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.

Verfasst: Dienstag 5. Mai 2009, 17:31
von numerix
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?

Verfasst: Dienstag 5. Mai 2009, 17:40
von 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

Verfasst: Dienstag 5. Mai 2009, 18:21
von numerix
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.

Verfasst: Dienstag 5. Mai 2009, 18:30
von 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.

Verfasst: Dienstag 5. Mai 2009, 18:38
von Kalira
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...