Das deutsche Python-Forum

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, "=", modulList, "-", multiList, "*", vielfachList)
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

Packe deinen Code bitte in Code-Tags, sonst wird es schwierig bis unmöglich dir zu Helfen.

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.

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

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

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.

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

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

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

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

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

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

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

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

Liebe Grüße
Kalira

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.

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

.

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

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

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

Kalira wird es schon schaffen, die Ausgabe nach ihren Vorgaben zu verändern. Und Flüchtichkeitsfehler im Code werden doch noch erlaubt sein, das macht die Sache so richtig spannend

:

Code: Alles auswählen

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

Übrigens, was hast du gegen Klammern? Mir wurde gesagt, Python sei eine so kuhle Sprache, weil man fast überall Klammern setzen kann

Wer hat dir das denn erzählt? Und warum benutzt du keine Klammern in Zeile 8, das wäre doch sowas von cool.

Goswin hat geschrieben:
numerix hat geschrieben:Nur dass die Ausgabe nicht so ist, wie gewünscht und dass dein Code nur bei ausgewählten Werten funktioniert ...
Kalira wird es schon schaffen, die Ausgabe nach ihren Vorgaben zu verändern.

Da bin ich ziemlich sicher, dass sie das nicht schaffen wird.

(Versuch du es doch mal ... ). Wenn ich es richtig aufgenommen habe, dann sollte die Darstellung wohl so aussehen, wie man es z.B. in der Wikipedia findet. Das sähe dann z.B. so aus:

Code: Alles auswählen

1 = 1·25-8·3
  = 1·25-8·(228-9·25) = 73·25-8·228
  = 73·(253-1·228)-8·228 = 73·253-81·228
  = 73·253-81·(481-1·253) = 154·253-81·481

Mit ein bisschen Verändern ist das aber nicht getan. Der Algorithmus muss anders angelegt werden, um das zu erreichen.

Goswin hat geschrieben:Und Flüchtichkeitsfehler im Code werden doch noch erlaubt sein, das macht die Sache so richtig spannend :

Diese Art von Spannung erschließt sich mir jedenfalls nicht.
Im übrigen funktioniert dein Code für a==b immer noch nicht ...

derdon hat geschrieben:Und warum benutzt du keine Klammern in Zeile 8, das wäre doch sowas von cool.

Und in 9 und 10 könnte man sicher noch das eine oder andere Klammerpaar reinsetzen.

derdon hat geschrieben:Und warum benutzt du keine Klammern in Zeile 8, das wäre doch sowas von cool.

OK, ich versuche einmal ernstlich, meinen Klammernstil zu erklären, falls euch so etwas wirklich interessieren sollte:
(1) Für MICH hat das Komma (natursprachlich bedingt) eine gaaanz niedrige Bindepräzedenz; wenn also eng zusammengehörende Ausdrücke in Python durch Kommas getrennt werden (müssen), dann setze ich sie immer in Klammern; in Deutschaufsätzen würde ich das Gleiche tun. Also (a,b)=(c,d) statt a,b=c,d.
(2) Außerdem setze ich Klammern, wo sie in einem normalen Mathematikbuch auch stehen würden, also x=a*(-b) anstelle von x=a*-b, und x=(a/b)/c anstelle von x=a/b/c.

Leonidas hat geschrieben:Und in 9 und 10 könnte man sicher noch das eine oder andere Klammerpaar reinsetzen.

Das hat wohl eher mit Python_3.x zu tun, und ich gebe zu dass ich das noch nicht installiert habe. Könnte man im Code-Tag dieses Forums nicht vielleicht zwischen code=py2 und code=py3 unterscheiden?

Das deutsche Python-Forum

Erweiterter euklidischer Algorithmus

Erweiterter euklidischer Algorithmus

Klammern