Entwickler-Ecke
Sonstiges (Delphi) - Rekursion oder Imperativ (eigen) Binäre Suche
Perfektionist - Mi 17.11.10 19:31
Titel: Rekursion oder Imperativ (eigen) Binäre Suche
Hallo zusammen ich ein Programm zur Binären Suche geschrieben und würde nun gerne wissen, ob ich einen rekursiven oder imperativen Weg benutzt habe. Mein Lehrer meinte es währe nur möglich die Binäre Suche mit Hilfe von einer Rekursion zu schaffen, allerdings erkenne ich nicht wirklich die Merkmale. (Beispielsweise: Eigenaufruf der Funktion)
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34:
| function TForm1.Suche(gesucht:integer):integer; var anfang1,ende1,ergebnis, offen, mitte:integer; begin Zeit:= 0; ergebnis:=0; offen:=0; anfang1:= 0; ende1:=z; mitte:=-1; while ergebnis = offen do begin
if mitte <> gesucht then begin if Zeit<10 then begin asd:=((anfang1 + ende1) div 2) + 1; mitte:= halter2[asd]; Zeit:=Zeit+1; if mitte > gesucht then ende1:=asd -1 else anfang1:=asd; end else begin showmessage('die gesuchte Zahl ist nicht vorhanden'); ergebnis := 1; close; end end else ergebnis :=1; result:=asd; end;
end; |
vielen Dank schonmal im varaus!
Gausi - Mi 17.11.10 19:38
Perfektionist hat folgendes geschrieben : |
Mein Lehrer meinte es währe nur möglich die Binäre Suche mit Hilfe von einer Rekursion zu schaffen, [...] |
Dann darfst du deinem Lehrer sagen, dass er Unsinn labert. :mrgreen:
Binärsuche geht auch einfach ohne Rekursion, den Beweis hast du mit deinem Code geliefert, wenn ich den richtig überblicke. Evtl. sind ein oder zwei kleine Fehler drin, aber das Prinzip passt so.
Edit: Das mit der Zeit und der Abfrage auf kleiner 10 ist natürlich unschön, da auch Binärsuche nicht immer mit 10 Vergleichen auskommt. Ebenso das Gedöns mit "Ergebnis" und "offen", da sollte imho eine anständige Abbruchbedingung ran, aber das lässt sich auch lösen.
Perfektionist - Mi 17.11.10 19:43
ah ok :s. ehm welche Fehler habe ich denn gemacht?
Gausi - Mi 17.11.10 19:53
Ich würde da ein paar Variablen sparen und das so machen
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24:
| Idx_links := 0; Idx_Rechts := length(MeinArray) - 1; result := -1; repeat Idx_mitte := (Idx_links + Idx_rechts) Div 2; if MeinArray[Idx_Mitte] = SuchWert then begin result := Idx_Mitte; rechts := -1; end else if MeinArray[Idx_Mitte] > SuchWert then begin Idx_rechts := Idx_Mitte - 1 end else if MeinArray[Idx_Mitte] < SuchWert then begin Idx_links := Idx_Mitte + 1 end; until (Idx_links > Idx_rechts)
|
Perfektionist - Mi 17.11.10 20:13
ah super vielen dank.
hättest du oder vllt jmd. anders ein paar aufgaben wo ich das schreiben von rekursiven programmen üben kann. gut wären auch einfach ein paar beispiele :)
Gausi - Mi 17.11.10 20:18
Naja, du könntest zur Übung die Binärsuche auch noch mal rekursiv implementieren.
Andere Klassiker für Rekursion sind die Fibonacci-Zahlen (wo Rekursion aber ziemlich ineffizient ist), oder die Berechnung der Fakultät einer Zahl.
Perfektionist - Mi 17.11.10 20:36
ah ok. fakultät haben wir schon im unterricht besprochen. haben auch schon kleinster gemeinsamer nenner bestimmt. desweiteren haben wir uns mit einer zahhlenfolge beschäftigt:
1,
121,
1213121,
121312141213121,...
wär super, wenn jmd. noch weitere beispiele hätte, evt. was vllt auch in GK 12 Info Klausur kommen könnte :P.
meine frage jetzt was bedeutet ineffizient.
jaenicke - Mi 17.11.10 20:38
Perfektionist hat folgendes geschrieben : |
Mein Lehrer meinte es währe nur möglich die Binäre Suche mit Hilfe von einer Rekursion zu schaffen |
Im Informatik-Studium lernt man unter anderem einen Beweis kennen, dass man
jeden rekursiv umgesetzten Algorithmus auch ohne Rekursion umsetzen kann. ;-)
Und auch einfach einmal logisch betrachtet:
Die Befehle bei einer Rekursion werden ja nun auch der Reihe nach abgearbeitet. Wenn man die stupide einfach hintereinander immer wiederholt, hat man den Algorithmus schon ohne Rekursion. Aber das lässt sich in aller Regel auch optimieren.
Perfektionist hat folgendes geschrieben : |
meine frage jetzt was bedeutet ineffizient. |
Wenn du mehrere Zahlen aus der Reihe haben willst, berechnest du mit Rekursion dennoch immer alle Vorgänger. Iterativ dagegen kannst du einfach alle direkt speichern, weil du die für die höheren Zahlen ohnehin brauchst.
Gausi - Mi 17.11.10 20:49
Die Fibonacci-Zahlen führen zu einer baumartigen Rekursion, d.h. die Funktion wird rekursiv zweimal aufgerufen. Das führt dann dazu, das das meiste mehrfach berechnet wird.
Beispiel: Um die Fib(10) zu berechnen, wird Fib(9) und Fib(8) aufgerufen. Um Fib(9) zu berechnen, wird Fib(8) und Fib(7) aufgerufen - Fib(8) wird also schon zweimal berechnet, Fib(7) dann dreimal usw. DAS ist ineffizient, weil Zwischenergebnisse, die man wiederverwenden könnte, einfach wieder vergessen werden. ;-)
Perfektionist - Mi 17.11.10 20:54
danke für die vielen Antworten. habe noch eine Frage und zwar habe ich hier gerade eine Prozedur vor mir liegen und was auch was die "allgemein" macht, allerdings verstehe ich nicht so ganz die Vorgehensweise. wär echt super, wenn jmd. mit seinen eigenen Worten das beschreiben könnte :)
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| procedure TF_Wort.Wort(n: Integer; w: string); var i: char; begin if n = 0 then M_Ausgabe.Lines.Add(w) else begin for i:= 'A' to 'F' do Wort(n-1,w+i) end; end; |
die funktionsweise von rekursionen scheint mir anscheind doch nocht nicht 100% klar zu sein :(
Kha - Mi 17.11.10 21:03
jaenicke hat folgendes geschrieben : |
Wenn du mehrere Zahlen aus der Reihe haben willst, berechnest du mit Rekursion dennoch immer alle Vorgänger. Iterativ dagegen kannst du einfach alle direkt speichern, weil du die für die höheren Zahlen ohnehin brauchst. |
Bevor jetzt noch jemand daraus den Schluss zieht, Rekursion würde die asymptotische Laufzeit verändern, will ich noch anmerken: Das tut sie nie ;) . Spricht man bei der Fibonacci-Folge von
der rekursiven und
der iterativen Methode, meint man eigentlich zwei
ganz [
http://de.wikipedia.org/wiki/Fibonacci-Folge#Definition_der_Fibonacci-Folge]
unterschiedliche [
http://de.wikipedia.org/wiki/Fibonacci-Folge#Herleitung_der_Formel_von_Moivre-Binet] Algorithmen/Definitionen. Beide können auch mit der jeweils anderen Methode umgesetzt werden, ohne dass sich der Zeit- oder Speicherbedarf verändert (die baumartig rekursive Definition iterativ umzusetzen wäre allerdings ziemlich sinnlos und das Ergebnis haarsträubend ;) ).
alzaimar - Mi 17.11.10 23:32
Ich finde die Türme von Hanoi immer wieder schön, um Rekursion zu veranschaulichen.
Ein Turm, bestehend aus N nach oben hin kleiner werdenden Scheiben soll von einer Position A mit Hilfe einer Position B zur Position C getragen werden. Dabei darf immer nur eine Scheibe bewegt werden. Scheiben darf man übereinander stapeln, aber nie so, das eine Scheibe auf einer kleineren liegt.
Lösung:
Um einen Turm aus N Scheiben von A mit Hilfe von B nach C zu verschieben,
verschiebt man den oberen Turm von N-1 Scheiben von A mit Hilfe von C nach B,
dann eine Scheibe von A nach C, und dann
verschiebt man den Turm aus N-1 Scheiben von B mit Hilfe von A nach C.
Kann man fast so 1:1 auskodieren.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!