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

Erweiterter euklidischer Algorithmus

Beitragvon Kalira » Mittwoch 29. April 2009, 11:28

Hi
Ich schreibe grade eine Facharbeit in Mathe und hab mir jetzt das Programmieren über Internet selbst beigebracht da ich vorher noch nie Informatik hatte... ich hab da ein kleines Problem mit dem erweiterten euklidischen Algorithmus und zwar weiß ich nicht wie ich dem Programm sagen soll, dass er für bestimmte Zahlen wiederholt die vorherigen Gleichungen einsetzen soll...
ich wollte auch gerne, dass er das Rechnen nicht einfach im Hintergrund macht sondern die Rechenschritte zeigt daher habe ich das erst mal so angefangen:

a = 481
b = 253
aList = [a, b, a%b]
modulList = []
vielfachList = []
restList = []
multiList = []
while aList[2] > 0:
print (aList[0], "=", aList[0]//aList[1], "*", aList[1], "+", aList[2])
modulList.append(aList[0])
vielfachList.append(aList[1])
multiList.append(aList[0]//aList[1])
restList.append(aList[2])
aList[0] = aList[1]
aList[1] = aList[2]
aList[2] = aList[0] % aList[1]
if aList[0] < aList[1]:
print (aList[1], "=", aList[1]//aList[0], "*", aList[0], "+", aList[1] % aList[0])
if aList[1] % aList[0] == 0:
break
print ("--------------------------------------------------------------------")

i = 1
copyRestList = []
while len(copyRestList) <= len(restList):
copyRestList.append(restList[len(restList)-i])
i = i + 1
if len(copyRestList) == len(restList):
break
restList = copyRestList

i = 1
copyModulList = []
while len(copyModulList) <= len(modulList):
copyModulList.append(modulList[len(modulList)-i])
i = i + 1
if len(copyModulList) == len(modulList):
break
modulList = copyModulList

i = 1
copyMultiList = []
while len(copyMultiList) <= len(multiList):
copyMultiList.append(multiList[len(multiList)-i])
i = i + 1
if len(copyMultiList) == len(multiList):
break
multiList = copyMultiList

i = 1
copyVielfachList = []
while len(copyVielfachList) <= len(vielfachList):
copyVielfachList.append(vielfachList[len(vielfachList)-i])
i = i + 1
if len(copyVielfachList) == len(vielfachList):
break
vielfachList = copyVielfachList

i = 0
while len(restList) > i:
print (restList[i], "=", modulList[i], "-", multiList[i], "*", vielfachList[i])
i = i + 1

print ("--------------------------------------------------------------------")

er rechnet jetzt halt erst einmal den ggT aus, was in diesem Fall die 1 ist, und dann formt er im nächsten Schritt alle Gleichungen zu dem Rest um... das sieht dann so aus:

481 = 1 * 253 + 228
253 = 1 * 228 + 25
228 = 9 * 25 + 3
25 = 8 * 3 + 1
--------------------------------------------------------------------
1 = 25 - 8 * 3
3 = 228 - 9 * 25
25 = 253 - 1 * 228
228 = 481 - 1 * 253
----------------------------------------------------------------

jetzt müsste er nur von der Gleichung 1= ausgehen und z.B. die 25 mit dem Term 253-1*228 ersetzen, wie auch die 8*3 mit 8*(228-9*25)...
im Endeffekt sollte das dann so in etwa aussehen:

1=25-8*3=(253-1*228)-8*(228-9*25)
=253-9*(481-1*253)+72*(253-1*228)
=82*253-9*481-72*(481-1*253)
=154*253-81*481


Kann mir da bitte jemand helfen??? Ich komm hier einfach nicht mehr weiter

Danke schon mal im Voraus :)
EyDu
User
Beiträge: 4866
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Mittwoch 29. April 2009, 11:39

Packe deinen Code bitte in Code-Tags, sonst wird es schwierig bis unmöglich dir zu Helfen.
Das Leben ist wie ein Tennisball.
nuss
User
Beiträge: 53
Registriert: Donnerstag 28. August 2008, 11:36

Beitragvon nuss » Mittwoch 29. April 2009, 11:44

OMG, bitte benutz Funktionen !

hier eine kleine Beispiel funktion, die nichts weiter tut, als 2 Zahlen zu addieren und das Ergebniss zurueckzugeben.

Code: Alles auswählen

def add(x, y):
    return x+y

diese Funktion ist jetzt vielleicht sinnlos,
aber sollte ja auch nur ein Beispiel sein.

Vielleicht solltest du auch noch 1 oder 2 Tutorials durcharbeiten. ;)
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Beitragvon Kalira » Mittwoch 29. April 2009, 12:06

Hi nochmal,
sorry das hatte ich übersehen

Code: Alles auswählen

a = 481
b = 253
aList = [a, b, a%b]
modulList = []
vielfachList = []
restList = []
multiList = []
while aList[2] > 0:
print (aList[0], "=", aList[0]//aList[1], "*", aList[1], "+", aList[2])
modulList.append(aList[0])
vielfachList.append(aList[1])
multiList.append(aList[0]//aList[1])
restList.append(aList[2])
aList[0] = aList[1]
aList[1] = aList[2]
aList[2] = aList[0] % aList[1]
if aList[0] < aList[1]:
print (aList[1], "=", aList[1]//aList[0], "*", aList[0], "+", aList[1] % aList[0])
if aList[1] % aList[0] == 0:
break
print ("--------------------------------------------------------------------")

i = 1
copyRestList = []
while len(copyRestList) <= len(restList):
copyRestList.append(restList[len(restList)-i])
i = i + 1
if len(copyRestList) == len(restList):
break
restList = copyRestList

i = 1
copyModulList = []
while len(copyModulList) <= len(modulList):
copyModulList.append(modulList[len(modulList)-i])
i = i + 1
if len(copyModulList) == len(modulList):
break
modulList = copyModulList

i = 1
copyMultiList = []
while len(copyMultiList) <= len(multiList):
copyMultiList.append(multiList[len(multiList)-i])
i = i + 1
if len(copyMultiList) == len(multiList):
break
multiList = copyMultiList

i = 1
copyVielfachList = []
while len(copyVielfachList) <= len(vielfachList):
copyVielfachList.append(vielfachList[len(vielfachList)-i])
i = i + 1
if len(copyVielfachList) == len(vielfachList):
break
vielfachList = copyVielfachList

i = 0
while len(restList) > i:
print (restList[i], "=", modulList[i], "-", multiList[i], "*", vielfachList[i])
i = i + 1

print ("--------------------------------------------------------------------")


1 oder 2 Tutorials können mir mit Sicherheit nicht schaden :wink:
mir läuft nur leider die Zeit zur Abgabe davon, und es ist ja auch Gott sei Dank keine Informatikarbeit^^
Daher reicht es meiner Lehrerin, wenn ich die Mathematik verstanden hab und wenn das Programm funktioniert
Aber ich guck mal, wenn ich noch Zeit habe, dass ich es dann etwas schöner schreibe :) es muss nur erstmal funktionieren und da liegt das Problem^^

Grüße
Kalira
Nergal
User
Beiträge: 72
Registriert: Montag 6. Oktober 2008, 14:02

Beitragvon Nergal » Mittwoch 29. April 2009, 12:17

Wenn du eine Liste umdrehen willst kannst du auch

Code: Alles auswählen

>>> x = [1,2,3,4]
>>> x = x[::-1]
>>> x
[4, 3, 2, 1]
>>>

verwenden.
nuss
User
Beiträge: 53
Registriert: Donnerstag 28. August 2008, 11:36

Beitragvon nuss » Mittwoch 29. April 2009, 12:23

in python ist ausserdem die Einrückung wichtig,
so kann man bei dem was du geschrieben hast nicht erkennen,
wo die schleifen aufhören und der Code ist so ausserdem nicht lauffähig.
also die in deinem Quelltext eingerückten stellen bitte auch hier einrücken ;)
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Beitragvon Kalira » Mittwoch 29. April 2009, 12:56

oh, sorry^^
und Danke Nergal, jetzt ist das ganze nicht mehr sooo lang :wink:

Code: Alles auswählen

a = 481
b = 253
aList = [a, b, a%b]
modulList = []
vielfachList = []
restList = []
multiList = []
while aList[2] > 0:
   print (aList[0], "=", aList[0]//aList[1], "*", aList[1], "+", aList[2])
   modulList.append(aList[0])
   vielfachList.append(aList[1])
   multiList.append(aList[0]//aList[1])
   restList.append(aList[2])
   aList[0] = aList[1]
   aList[1] = aList[2]
   aList[2] = aList[0] % aList[1]
   if aList[0] < aList[1]:
      print (aList[1], "=", aList[1]//aList[0], "*", aList[0], "+", aList[1] % aList[0])
   if aList[1] % aList[0] == 0:
      break
print ("--------------------------------------------------------------------")

restList = restList[::-1]
modulList = modulList[::-1]
vielfachList = vielfachList[::-1]
multiList = multiList[::-1]

i = 0
while len(restList) > i:                                # nun
    print (restList[i], "=", modulList[i], "-", multiList[i], "*", vielfachList[i])
    i = i + 1

print ("--------------------------------------------------------------------")


Grüße
Kalira
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Beitragvon HWK » Mittwoch 29. April 2009, 13:16

Statt

Code: Alles auswählen

x = x[::-1]
die wohl etwas lesbarere Variante

Code: Alles auswählen

x.reverse()
Für den GGT gibt es

Code: Alles auswählen

fractions.gcd(a, b)
MfG
HWK
BlackJack

Beitragvon BlackJack » Mittwoch 29. April 2009, 13:16

@Kalira: Den Datentyp sollte man möglichst nicht in den Namen stecken. Also all die `*Liste`-Zusätze würde ich weglassen und Namen wie `reste`, `vielfache`, usw. verwenden.

`aList` wird so als Liste nie benötigt, sondern immer nur die einzelnen Elemente. Warum stecken die drei Werte also überhaupt in einer Liste statt sie einzeln an Namen zu binden!? Damit wird der Quelltext viel übersichtlicher.

Bei der Ausgabe böte sich eine ``for``-Schleife anstelle der ``while``-Schleife an. Vielleicht sogar ohne das `i` sondern mit der `zip()`-Funktion gleich über die Elemente der Listen.
nuss
User
Beiträge: 53
Registriert: Donnerstag 28. August 2008, 11:36

Beitragvon nuss » Mittwoch 29. April 2009, 13:37

@HWK
aber x[::-1] hat einen entscheidenden Vorteil gegenüber x.reverse()
x.reverse() gibt None zurueck und dreht die Liste um, x[::-1] gibt
eine umgedrehte Liste zurueck, dreht die Liste aber nicht um.
Obwohls hier jetzt jetzt keinen Unterschied macht.
BlackJack

Beitragvon BlackJack » Mittwoch 29. April 2009, 13:49

@nuss: Der entscheidende "Vorteil" ist keiner. Das die Liste kopiert wird, kann man genauso als Nachteil sehen. Hier macht's keinen Unterschied ausser halt im Speicherverbrauch und der Lesbarkeit, also macht's eigentlich doch wieder einen Unterschied: `list.reverse()` wäre hier IMHO deutlich besser geeignet.
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Beitragvon Kalira » Mittwoch 29. April 2009, 13:50

Hi^^

Vielen Dank für die vielen Meldungen und Vorschläge!
Ich kann mich leider erst morgen darum kümmern, denn ich schreib morgen noch Physik und muss mich erst mal drauf vorbereiten..
ich werde dann mal versuchen mich mit den Funktionen von Python vertraut zu machen.
Kann mir jemand bitte noch erklären wie ich den erweiterten euklidischen Algorithmus zuende schreiben kann?? Also wie ich die Terme für die Reste wiederholt einsetze bis ich wieder eine Aussage über die beiden ursprünglichen Zahlen a und b bekommen???
Dieser Teil zerbricht mir echt den Kopf :wink:

Liebe Grüße
Kalira
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Mittwoch 29. April 2009, 16:21

HWK hat geschrieben:Für den GGT gibt es

Code: Alles auswählen

fractions.gcd(a, b)


So er/sie denn Python > 2.5 hat ... aber selbst dann nützt das nichts: Es geht ja nicht um den einfachen Euklidischen Algorithmus - der ist in einer Zeile schnell programmiert - sondern um den erweiterten Euklidischen Algorithmus und (und das ist das eigentlich anspruchsvolle an der Aufgabe) um eine lesbare Darstellung des ganzen Rechenweges.
Benutzeravatar
Goswin
User
Beiträge: 361
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen

Beitragvon Goswin » Mittwoch 29. April 2009, 18:18

Es geht in der Tat etwas kürzer als oben und auch ohne Funktionen:

Code: Alles auswählen

(aa, bb) = (a0, b0) = (481, 253)
(amult_a0, amult_b0) = (0, 1)  #alte Multiplikatoren von a0 und b0
#
(mm,rr) = (aa//bb, aa%bb)  #aa == (aa//bb) * bb + (aa%bb)
(mult_a0, mult_b0) = (1, -mm)  #Multiplikatoren von a0 und b0
#
while bb>1: #FEHLER, RICHTIG IST while rr>0:
  print "%3i = %3i * %3i + %3i   ==>  " %(aa,mm,bb,rr),
  print "%3i = (%3i) * %3i + (%3i) * %3i" %(rr, mult_a0,a0, mult_b0,b0)
  #
  (aa,bb) = (bb,rr)
  (mm,rr) = (aa//bb, aa%bb)
  (nmult_a0, nmult_b0) = (amult_a0-mm*mult_a0, amult_b0-mm*mult_b0)
  #
  (amult_a0, amult_b0) = (mult_a0, mult_b0)
  (mult_a0, mult_b0) = (nmult_a0, nmult_b0)


@Kalira: Mit Hilfe der Tutorials darfst du jetzt versuchen, das zu verstehen :wink:.
Zuletzt geändert von Goswin am Donnerstag 30. April 2009, 07:03, insgesamt 2-mal geändert.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Mittwoch 29. April 2009, 19:12

Goswin hat geschrieben:Es geht in der Tat etwas kürzer als oben und auch ohne Funktionen: <Code>


Nur dass die Ausgabe nicht so ist, wie gewünscht und dass dein Code nur bei ausgewählten Werten funktioniert ....

ggt(66, 12) liefert z.B.

Code: Alles auswählen

66 =   5 *  12 +   6   ==>     6 = (  1) *  66 + ( -5) *  12
 12 =   2 *   6 +   0   ==>     0 = ( -2) *  66 + ( 11) *  12
Traceback (most recent call last):
  File "nix-gcd-1.py", line 12, in <module>
    (mm,rr) = (aa//bb, aa%bb)
ZeroDivisionError: integer division or modulo by zero


:cry:

Und wenn kalira ins Tutorial schaut, wird er/sie sich wundern, warum in deinem Code soooooo viele Klammern stehen ... (und: such mal nach divmod())

Wer ist online?

Mitglieder in diesem Forum: Google [Bot], Sirius3