Seite 4 von 5

Verfasst: Dienstag 5. Mai 2009, 18:42
von Hyperion
Kalira hat geschrieben:
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...
Wo genau liegt denn jetzt das Problem? Beim Verständnis von Python oder beim Verständnis des Algos?

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

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

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

Verfasst: Dienstag 5. Mai 2009, 19:25
von 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.)

:wink:
yipyip

Verfasst: Dienstag 5. Mai 2009, 21:04
von Kalira
Hi Leute,

Also was die mathematik angeht, so hab ich das verstanden, ich habs ja schon an ein paar Beispielen auf einem Blatt papier durchprobiert... also das ist kein Problem... mein Problem ist einfach nur, dass ich ganz ehrlich keine Ahnung von informatik habe :!: .. ich meine ich hatte es nie in der Schule und ich hab auch nie jemanden gehabt der mir mal so sachen über informatik erklärt hat oder mir gezeigt hat wie man das macht.. ich hab einfach nur internet seiten verwendet und logisch überlegt... nur jetzt hab ich einfach keine Zeit mehr um das so weiter zu machen denn ich muss schon nächste Woche Freitag abgeben und muss noch einen haufen dazu schreiben....
Also vielen Dank für die vielen Lösungen aber ich verstehe sie einfach nicht... wenn ich da so einen code bekomme dann blicke ich nicht durch weil ich so viele Abkürzungen nicht verstehe und so weiter...

daher yipyip kannst du mir bitte einfach nur den Teil raussuchen, der die wirkliche Erweiterung ist... also den Teil wo du dem Programm sagst, dass es die einzelnen Zahlen durch vorherberechnete Terme ersetzen soll...
und wenn es dir nichts ausmacht, dann kannst du mir bitte einfach nur jeden Schritt dazu erklären?? Also wie man darauf kommt, wie man anfängt, worauf man achten muss und so???? und vielleicht einfach nur in Wörtern dahinter schreibst was das Programm jetzt durch diesen Befehl machen soll....Denn sonst kann ich dir wirklich nicht mehr folgen :(

Vielen, vielen Dank
und liebe Grüße

Kalira

PS: ich kann leider erst wieder morgen schreiben!

Verfasst: Dienstag 5. Mai 2009, 21:20
von yipyip
Um Missverständnissen vorzubeugen:
Mein Programm macht keine Termersetzung
wie bei Numerix:

Du erhältst bei mir eine Augabe der Form:
> ggt.py 1234 24
Euclid Equations:
1234 = 24 * 51 + 10
24 = 10 * 2 + 4
10 = 4 * 2 + 2
4 = 2 * 2 + 0

Rest Equations:
0 = 4 - 2 * 2
2 = 10 - 2 * 4
4 = 24 - 2 * 10
10 = 1234 - 51 * 24

ggt Equations:
2 = 1 * 2 + 0 * 0
2 = 0 * 4 + 1 * 2
2 = 1 * 10 - 2 * 4
2 = -2 * 24 + 5 * 10
2 = 5 * 1234 - 257 * 24
Hatte das jetzt so verstanden, dass Dir diese
Art der Ausgabe, also ohne Termersetzung,
prinzipiell ausreicht.

Der für Dich wichtige Teil steht in
'get_ggt_equations()', der die Faktoren
für die obigen letzten 5 Gleichungen liefert.
(Ich mache Dir dann in Kürze noch eine
genau kommentierte Version.)

:wink:
yipyip

Verfasst: Dienstag 5. Mai 2009, 21:37
von Hyperion
@Kalira: Wieso machst Du denn bitte schön eine Programmieraufgabe, wenn Du davon keine Ahnung hast und auch keine Vorbildung? Zudem wenn die eigentlich Aufgabe über das simple Implementieren des Algos hinausgeht? Evtl. wäre es da geschickter, das Thema noch zu wechseln ...

"Des Codes dritter Akt"

Verfasst: Mittwoch 6. Mai 2009, 20:04
von Goswin
Hallo Kalira,
Dein unvollendetes Programm, welches immerhin glatt durchläuft und die richtigen Ergebnisse liefert, finde ich für eine(n) Anfänger(in) sehr ordentlich. Man braucht auch gar keine tiefgehende Python-Kenntnisse, um es zu vollenden; ich bin da nicht der Meinung einiger anderer Forumsteilnehmer. (Aber dem Mathematikeer :-) ist ja nichts zu schwer) Die meisten Vorschläge im folgenden Code, den ich dir mit kollegialen Grüßen zusende, sind reine Schönheitskorrekturen:

Code: Alles auswählen

(a,b) = (187,115)  #Vorschlag
assert a%b>0  #Trivialfaelle verbleiben als Hausaufgabe

c = a%b
modul = []
vielfach = []
rest = []
multi = []
while c > 0:
#   print (a, "=", a//b, "*", b, "+", c) #unschoen bei Python_2.x
#   print  a, "=", a//b, "*", b, "+", c  #falsch bei Python_3.x
#   print( "%i = %i * %i + %i" %(a, a//b, b, c) )  #Vorschlag_1
    print( "%3i = %3i * %3i + %3i" %(a, a//b, b, c) )  #Vorschlag_2
    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 ("--------------------------------------------------------------------")

#Vorsicht: folgende Listen sind leer falls b%a==0 gilt!
rest.reverse()
modul.reverse()
vielfach.reverse()
multi.reverse()

i = 0
while len(rest) > i:
#   print (rest[i], "=", modul[i], "-", multi[i], "*", vielfach[i])
    print("%3i = %3i - %3i * %3i" %(rest[i],modul[i],multi[i],vielfach[i])) #V
    i = i + 1

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

ggn = rest[0]
(multA,zahlA, multB,zahlB) = (0,0, 1,ggn)

i = 0
while len(rest) > i:
    #Tupel werden komponentenweise zugewiesen:
    ( multA, zahlA,  multB, zahlB ) = (
        multB, modul[i],  multA-multB*multi[i], vielfach[i] )
    print("%3i = (%3i) * %3i + (%3i) * %3i" %(ggn, multA,zahlA, multB,zahlB))
    i = i + 1
Viel Vergnügen beim Entziffern!

Verfasst: Mittwoch 6. Mai 2009, 20:17
von derdon
Zeile 24 und 38 würdest du so lassen? Die stechen mir beim Überfliegen als erstes ins Auge.

Verfasst: Mittwoch 6. Mai 2009, 20:32
von Goswin
derdon hat geschrieben:Zeile 24 und 38 würdest du so lassen? Die stechen mir beim Überfliegen als erstes ins Auge.
Ich denke, das sollen sie doch gerade!

Verfasst: Mittwoch 6. Mai 2009, 20:47
von derdon
So kann man es natürlich auch sehen. Ich meinte, das mir bei den Zeilen sofort etwas wie

Code: Alles auswählen

print('-' * 68)
einfiel.

Verfasst: Mittwoch 6. Mai 2009, 20:53
von Dill
ich habe mal den rekursiven algo implementiert.
vorteil: hier kann man viel natürlicher die rechenschritte darstellen.
nachteil: evtl. schwer verdaulich, da rekursiv.

Code: Alles auswählen




def extended_euclid(a, b):
    if b == 0:
        print "\nggT: %d\nFinde jetzt Linearkombination des ggT aus Ausgangszahlen:\n" % a
        return a, 1, 0
        
    else:
        print "%(a)d = %(faktor)d * %(b)d +  %(a_mod_b)d" % {"a":a, "faktor":a/b, "b":b, "a_mod_b":a%b}
        
        d_, s_, t_ = extended_euclid(b, a % b)
        d, s, t = d_, t_, s_ - (a/b) * t_
        
        print("%(d)d = %(s)d * %(a)d + %(t)d * %(b)d") % {"d":d, "s":s, "a":a, "t":t, "b":b}
        
        return d, s, t

Code: Alles auswählen

>>> extended_euclid(99, 78)
99 = 1 * 78 +  21
78 = 3 * 21 +  15
21 = 1 * 15 +  6
15 = 2 * 6 +  3
6 = 2 * 3 +  0

ggT: 3
Finde jetzt Linearkombination des ggT aus Ausgangszahlen:

3 = 0 * 6 + 1 * 3
3 = 1 * 15 + -2 * 6
3 = -2 * 21 + 3 * 15
3 = 3 * 78 + -11 * 21
3 = -11 * 99 + 14 * 78
(3, -11, 14)

Verfasst: Donnerstag 7. Mai 2009, 06:44
von BlackJack
Verbesserungsvorschlag für's einsetzen der Werte in die Zeichenketten:

Code: Alles auswählen

def extended_euclid(a, b):
    if b == 0:
        print ('\nggT: %d\n'
               'Finde jetzt Linearkombination des ggT aus Ausgangszahlen:\n'
               % a)
        return a, 1, 0
    else:
        faktor, a_mod_b = divmod(a, b)
        print '%(a)d = %(faktor)d * %(b)d +  %(a_mod_b)d' % locals()
        
        d_, s_, t_ = extended_euclid(b, a % b)
        d, s, t = d_, t_, s_ - (a/b) * t_
        
        print '%(d)d = %(s)d * %(a)d + %(t)d * %(b)d' % locals()
        
        return d, s, t

Verfasst: Donnerstag 7. Mai 2009, 07:51
von Dill
wow, sehr hübsch! was es nicht alles gibt.
richtig sexy langsam der code :)