Autor |
Beitrag |
Perfektionist
Hält's aus hier
Beiträge: 10
|
Verfasst: Mi 17.11.10 19:31
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)
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
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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.
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.
_________________ We are, we were and will not be.
|
|
Perfektionist 
Hält's aus hier
Beiträge: 10
|
Verfasst: Mi 17.11.10 19:43
ah ok :s. ehm welche Fehler habe ich denn gemacht?
|
|
Gausi
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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)
|
_________________ We are, we were and will not be.
|
|
Perfektionist 
Hält's aus hier
Beiträge: 10
|
Verfasst: 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
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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.
_________________ We are, we were and will not be.
|
|
Perfektionist 
Hält's aus hier
Beiträge: 10
|
Verfasst: 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  .
meine frage jetzt was bedeutet ineffizient.
|
|
jaenicke
      
Beiträge: 19312
Erhaltene Danke: 1747
W11 x64 (Chrome, Edge)
Delphi 11 Pro, Oxygene, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
|
Verfasst: 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
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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. ;-)
_________________ We are, we were and will not be.
|
|
Perfektionist 
Hält's aus hier
Beiträge: 10
|
Verfasst: Mi 17.11.10 20:54
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: 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 unterschiedliche 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
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: 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.
_________________ Na denn, dann. Bis dann, denn.
|
|