Autor Beitrag
Perfektionist
Hält's aus hier
Beiträge: 10



BeitragVerfasst: 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)

ausblenden volle Höhe 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mi 17.11.10 19:38 
user profile iconPerfektionist hat folgendes geschrieben Zum zitierten Posting springen:
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.

_________________
We are, we were and will not be.
Perfektionist Threadstarter
Hält's aus hier
Beiträge: 10



BeitragVerfasst: Mi 17.11.10 19:43 
ah ok :s. ehm welche Fehler habe ich denn gemacht?
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mi 17.11.10 19:53 
Ich würde da ein paar Variablen sparen und das so machen

ausblenden 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// ungültiger index

repeat
  Idx_mitte := (Idx_links + Idx_rechts) Div 2;
  if MeinArray[Idx_Mitte] = SuchWert then
  begin
      result := Idx_Mitte; // Treffer, gefunden
      rechts := -1// Abbruch erzwingen
  end else
  if MeinArray[Idx_Mitte] > SuchWert then
  begin
    // Suchwert liegt links von der Mitte
    Idx_rechts := Idx_Mitte - 1
  end else
  if MeinArray[Idx_Mitte] < SuchWert then
  begin
    // Suchwert liegt rechts von der Mitte
    Idx_links := Idx_Mitte + 1
  end;
until (Idx_links > Idx_rechts)

// wenn result dann noch -1 ist, gibt es das gesuchte Element nicht

_________________
We are, we were and will not be.
Perfektionist Threadstarter
Hält's aus hier
Beiträge: 10



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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 Threadstarter
Hält's aus hier
Beiträge: 10



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 19312
Erhaltene Danke: 1747

W11 x64 (Chrome, Edge)
Delphi 11 Pro, Oxygene, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
BeitragVerfasst: Mi 17.11.10 20:38 
user profile iconPerfektionist hat folgendes geschrieben Zum zitierten Posting springen:
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.

user profile iconPerfektionist hat folgendes geschrieben Zum zitierten Posting springen:
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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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 Threadstarter
Hält's aus hier
Beiträge: 10



BeitragVerfasst: 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 :)
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Mi 17.11.10 21:03 
user profile iconjaenicke hat folgendes geschrieben Zum zitierten Posting springen:
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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: 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.