U2.3 Doppeter Aufruf

Tobias Stöckert
Mausschubser
Mausschubser
Beiträge: 52
Registriert: 18. Apr 2015 15:35

U2.3 Doppeter Aufruf

Beitrag von Tobias Stöckert »

Im Code wird awesomealgo zweimal mit den gleichen Parametern aufgerufen jedoch kann ich den Sinn dahinter sehen denn implementiert funktioniert es auch mit nur einem dieser beiden Aufrufe.
Handelt es sich um einen Fehler in der Aufgabe oder hab ich irgend einen Fall übersehen?

kurzeFrage()
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 13. Mai 2015 21:06

Re: U2.3 Doppeter Aufruf

Beitrag von kurzeFrage() »

Ich nehme an, dass die Beispiele, die du dir angeguckt hast, jeweils nur ein k =1 ergeben. Probiere es mal mit einer größeren Sequenz.
Was passiert z.B., wenn bei einer Sequenz mit 9 Zeichen an zweit-hinterster Stelle die niedrigste Zahl steht?

KaeferZuechter
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 108
Registriert: 15. Apr 2015 19:24

Re: U2.3 Doppeter Aufruf

Beitrag von KaeferZuechter »

Versuche einfach mal, die Korrektheit ohne den zweiten Aufruf zu beweisen.
IT'S CALLED A FOURIER TRANSFORM WHEN YOU TAKE A NUMBER AND CONVERT IT TO THE BASE SYSTEM WHERE IT WILL HAVE MORE FOURS, THUS MAKING IT "FOURIER". IF YOU PICK THE BASE WHERE IS HAS THE MOST FOURS, THE NUMBER IS SAID TO BE "FOURIEST".

\(1160_8 \rightarrow 624_{10} \rightarrow 440_{12} \rightarrow 4444_5\)

- Zach Weiner -

Tobias Stöckert
Mausschubser
Mausschubser
Beiträge: 52
Registriert: 18. Apr 2015 15:35

Re: U2.3 Doppeter Aufruf

Beitrag von Tobias Stöckert »

okay werd ich mal probieren :D

gangster
Erstie
Erstie
Beiträge: 19
Registriert: 10. Apr 2015 13:15

Re: U2.3 Doppeter Aufruf

Beitrag von gangster »

Hänge an dieser Aufgabe auch ein wenig:
Was meinst du mit "Korrektheit ohne 2. Aufruf beweisen"? Soll man nur den ersten rekursiven Aufruf durchspielen? Die anderen beiden rekursiven Aufrufe in der Methode erfolgen ja erst, wenn man beim ersten Aufruf bis zum Rekursionsanker vorgedrungen ist. Mir ist deshalb noch nicht so ganz klar, was hier Variante und Invariante sein soll...

Sheldon
Erstie
Erstie
Beiträge: 20
Registriert: 23. Apr 2015 17:08

Re: U2.3 Doppeter Aufruf

Beitrag von Sheldon »

Nach welcher Regel werden denn die Parameter l und r im ersten Aufruf von awesomealgo() gewählt?
Meiner Meinung nach sind die Erklärungen "left bound" und "right bound" nicht selbstverständlich...

Danke im Voraus
Sheldon

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: U2.3 Doppeter Aufruf

Beitrag von R_Egert »

Left- und Right bound sind initial Indizes für das erste und letzte Element.

VG,

Rolf
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

Benutzeravatar
felicis
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 114
Registriert: 14. Apr 2015 20:25

Re: U2.3 Doppeter Aufruf

Beitrag von felicis »

kurzeFrage() hat geschrieben:Ich nehme an, dass die Beispiele, die du dir angeguckt hast, jeweils nur ein k =1 ergeben. Probiere es mal mit einer größeren Sequenz.
Was passiert z.B., wenn bei einer Sequenz mit 9 Zeichen an zweit-hinterster Stelle die niedrigste Zahl steht?
Stimmt, der letzte Aufruf ist nötig. Ein einfaches und greifbares Beispiel:
Wir teilen unsere (zum Schluss) sortierte Sequenz mal gedanklich in drei Teile: den Anfang, die Mitte und das Ende...
\(\fbox{Anfang}\fbox{Mitte}\fbox{Ende}\).

Der worst-case Fall hierzu ist ja, wenn die Sequenz so geordnet ist:
\(\fbox{Ende}\fbox{Mitte}\fbox{Anfang}\).
Im ersten Aufruf von awesomealgo() wird es dann:
\(\fbox{Mitte}\fbox{Ende}\fbox{Anfang}\),
nach dem zweiten Aufruf dann:
\(\fbox{Mitte}\fbox{Anfang}\fbox{Ende}\),
und zum Schluss:
\(\fbox{Anfang}\fbox{Mitte}\fbox{Ende}\).

Hier wird schnell klar, wofür der letzte Aufruf con awesomealgo() nötig ist ;)

felicis

h4ktheworld
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 29. Apr 2015 12:34

Re: U2.3 Doppeter Aufruf

Beitrag von h4ktheworld »

Moooment. Alleine die erste Abfrage stellt sicher, dass Anfang und Ende geswappt werden würde und somit die Sequenz passend sortiert wäre.

Die Anweisung ist aber natürlich wichtig, denn sie stellt eben dieses von meinem Vorposter bildhaft aufgezeigte sicher. (Letzte und vorletzte Schritte beachten).

Benutzeravatar
felicis
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 114
Registriert: 14. Apr 2015 20:25

Re: U2.3 Doppeter Aufruf

Beitrag von felicis »

Nur zur Info: mit Anfang, Mitte und Ende meine ich keineswegs einzelne Elemente, sondern Teilsequenzen! (Wenn es einzelne Elemente wären, dann wäre das Beispiel trivial und mit der ersten if-Abfrage gelöst)

felicis

Benutzeravatar
Rosa
Erstie
Erstie
Beiträge: 11
Registriert: 18. Mai 2015 01:42

Re: U2.3 Doppeter Aufruf

Beitrag von Rosa »

Ich verstehe nicht wie das Programm zu Zeile 20 ( awesomealgo ( input , l+k , r ) ) überhaupt kommt :cry: .
Bei zweite if- Bedingung ruft sich methode wieder auf mit erstem aufruf in Zeile 19, deswegen verstehe ich nicht wie das Programm überhaupt zu Zeile 20 oder 21 kommt.

Kann mir jemand bitte erklären wie Rekrusion in diesem Fall funktioniert?

Danke

Benutzeravatar
felicis
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 114
Registriert: 14. Apr 2015 20:25

Re: U2.3 Doppeter Aufruf

Beitrag von felicis »

Die Erklärung ist: GENERATIVE REKURSION!!!
--> Allen drei Methodenaufrufen wird tatsächlich gefolgt!! Das heißt du hast exponentielles Wachstum (zum Glück haben wir Rekursionsanker... :lol: )
Wie du zum Teil schon richtig vermutet hast folgt der Computer konkret aber erst nur einem Pfad bis dieser abbricht (= zu ende ist: Rekursionsanker erreicht), dann geht er zurück zum nächten Pfad und macht dort weiter bis dieser wieder abbricht, usw.
Das Problem wird dabei nicht direkt angegangen (wie zum Beispiel bei struktureller Rekursion), sondern wird so lange in Teilprobleme aufgeteilt, bis diese elementar (lösbar) sind.
Aber er folgt definitiv JEDEM Pfad, also kannst du dir sicher sein, dass die beiden anderen Aufrufe auch ausgeführt werden (Achtung hier: die Sequenz hat sich dann aber schon geändert!!)

felicis

PS: Mergesort funktioniert ja genauso: Du nimmst deine Sequenz und teilst sie in zwei ähnlich große Teilsequenzen; dadurch ist die Liste aber nicht sortierter! Erst wenn du bei einem Element angekommen bist, wird erst angefangen zu sortieren und dabei den ganzen riesigen Methodenbaum, der mitgeschleppt wurde wieder abzubauen :)

PS2: Das Motto dazu: Divide-And-Conquer (Teile-Und-Herrsche)

PS3: Nein, auch Computer sind, genauso wie Menschen, nicht zu "richtigem" Mulititasking fähig :mrgreen:

Benutzeravatar
Rosa
Erstie
Erstie
Beiträge: 11
Registriert: 18. Mai 2015 01:42

Re: U2.3 Doppeter Aufruf

Beitrag von Rosa »

Danke für dein Antwort aber ich habe noch eine frage, da ich leider immer noch nicht verstehe wie das genau funktioniert.

Erste und dritte Aufruf sind gleich. Werden sie dann mit gleichen parameter aufgerufen? Bleibt k gleich oder wird der an letzte gültige Aufruf von zweiten Aufruf angepasst?

Grüße

KaeferZuechter
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 108
Registriert: 15. Apr 2015 19:24

Re: U2.3 Doppeter Aufruf

Beitrag von KaeferZuechter »

Rosa hat geschrieben:Danke für dein Antwort aber ich habe noch eine frage, da ich leider immer noch nicht verstehe wie das genau funktioniert.

Erste und dritte Aufruf sind gleich. Werden sie dann mit gleichen parameter aufgerufen? Bleibt k gleich oder wird der an letzte gültige Aufruf von zweiten Aufruf angepasst?

Grüße
Vorsicht:
Die Liste bzw. das Array hat sich nach den ersten zwei Aufrufen verändert.
Es sind im dritten Aufruf zwar nach wie vor die gleichen Parameter, allerdings eine andere Eingabemenge!

Tipp:
- Implementieren
- Testen
- Mit Veränderungen spielen
IT'S CALLED A FOURIER TRANSFORM WHEN YOU TAKE A NUMBER AND CONVERT IT TO THE BASE SYSTEM WHERE IT WILL HAVE MORE FOURS, THUS MAKING IT "FOURIER". IF YOU PICK THE BASE WHERE IS HAS THE MOST FOURS, THE NUMBER IS SAID TO BE "FOURIEST".

\(1160_8 \rightarrow 624_{10} \rightarrow 440_{12} \rightarrow 4444_5\)

- Zach Weiner -

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: U2.3 Doppeter Aufruf

Beitrag von R_Egert »

KaeferZuechter hat geschrieben: Tipp:
- Implementieren
- Testen
- Mit Veränderungen spielen
Oder aber ein nicht triviales Beispiel wählen + Zettel und Stift ;) :twisted:

Viele Grüße,

Rolf
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

Antworten

Zurück zu „Archiv“