Doppelpost! Rekursive Algorithmen - Verständnisprobleme |
| 05.08.2014, 14:14 | Trillhouse420 | Auf diesen Beitrag antworten » | ||
| Rekursive Algorithmen - Verständnisprobleme vorweg: ich bin Laie (vielleicht demnächst Informatikstudent) und habe mir mal spaßeshalber einen Algorithmus, der von der RWTH Aachen im Rahmen des "Algorithmus der Woche" vorgestellt wurde, angeschaut. Allerdings verstehe ich ihn nicht, was sehr frustrierend ist. Mein Ehrgeiz wurde aber geweckt! Es geht um die Berechnung des Wertes von (3^9) mod 17, was man ja so schaffen kann: 1. Berechne: (3^2) mod 17 ( = 9) 2. Es gilt: (3^4) mod 17 = ((3^2 mod 17) * (3^2 mod 17)) mod 17 = (9*9) mod 17 = 13 3. Dementsprechend: (3^8) mod 17 = (13*13) mod 17 4. Somit: (3^9) mod 17 = (13*13*3) mod 17 = 14 Das kann man scheinbar rekursiv so umsetzen: ExpMod(a, b, p) If b=0 then return 1 If b=1 then return a If b is odd then begin h = ExpMod(a, b-1, p) return (h*a) mod p end h = ExpMod(a, b/2, p) return (h*h) mod p Im obigen Fall, d.h. (3, 9, 17), kämen dann doch folgende Schritte: b is odd, also ruft man ExpMod(3, 8, 17) auf. Somit kommt man zur letzten Zeile, die man aufruft, bis ExpMod(3, 1, 17) ansteht. Dann bekommt h den Wert a, also 3. ABER: was passiert jetzt? Eigentlich müsste die Anweisung return (3*3) mod 17 ( = 9) ausgeführt werden. Was genau bedeutet das return nun, bzw. wohin gebe ich den Wert zurück? An den if-Block etwa? Und wie kommt dabei je das richtige Ergebnis raus?! Ich weiß im Prinzip, was passieren muss: Man baut die Multiplikation so auf wie in der obigen Liste. Aber wie schafft das das Programm?! Vielen Dank, ich steh total auf dem Schlauch!!! |
||||
| 05.08.2014, 14:34 | Steffen Bühler | Auf diesen Beitrag antworten » | ||
| RE: Rekursive Algorithmen - Verständnisprobleme Ist zwar eher Informatik, aber jetzt bist Du schon mal hier... 
An die aufrufende Funktion. Die wiederum führt dann ihre letzte Zeile aus und gibt (9*9) mod 17 zurück, und zwar an ihre aufrufende Funktion. Die wiederum... Viele Grüße Steffen |
||||
| 05.08.2014, 20:16 | RavenOnJ | Auf diesen Beitrag antworten » | ||
| Doppelposting Es wird hier nicht gerne gesehen, wenn man ein Problem oder Frage auf mehreren Webseiten postet und das auch noch nahezu zeitgleich! |
||||
| 06.08.2014, 09:13 | Steffen Bühler | Auf diesen Beitrag antworten » | ||
| RE: Rekursive Algorithmen - Verständnisprobleme Allerdings. Es ist nämlich sehr unhöflich, mehrere unbezahlte Leute auf sein Problem anzusetzen. Ich schließe. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
