Autor Beitrag
hibbert
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1007

WinServer2003, Win XP, Linux
D6 Pers, D05
BeitragVerfasst: So 07.05.06 14:04 
Hi,
ich habe ein Problem bei meiner Binärsuche. Ich habe ein Array daten: array[0..n] of integer;. Nun sagen wir mal n := 10 und ich suche nach der 5. Dann erhalte ich als Ergebnis, dass die 5 nicht vorhanden ist, obwohl ich weiß, dass die 5 vorhanden ist.

Hier der Aufbau des arrays und der restlichen Globalen Variablen:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
const max :integer = 100;//max anzahl der Zufallszahlen...
var daten: array of integer;
log:boolean; // soll geloggt werden
erg:integer; //liefert das endgültige ergebnis zurück...


So wird das Array gefüllt und angezeigt:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
procedure TForm1.FormCreate(Sender: TObject);
var i : integer;
begin
  randomize;
  // erstellt die einträge, logischerweise gleich geordnet ^^
  for i:= 0 to random(max) do
    begin
      SetLength(daten, i+1);
      daten[i]:=i+1;
    end;
    
// auflisten ...just for fun ;)
  for i := 0 to high(daten) do
  memo1.lines.add(inttostr(daten[i]));
end;


Nun zu dem Teil, der die suche startet:
Um zu überrüfen ob die Zahl gefunden wurede oder nicht, hänge ich die Zahl an das Ende des arrays, das sieht so aus:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
procedure TForm1.Button1Click(Sender: TObject);
var ergebnis,suche,max:integer;
begin
  suche:=strtoint(edit1.Text);
  // zahl ans ende hängen... START
  setLength(daten,high(daten)+2); //weil array ab 0 beginnt...
  max:=high(daten);
  daten[max] := suche; // das ans ende hängen...
  // zahl ans ende hängen ENDE
{ da kommt gleich noch was...}

So nun starte ich die suche mit:
ausblenden Delphi-Quelltext
1:
2:
3:
{fortsetzung von Button1.click}
ergebnis:=search(suche,0,max);
{da kommt noch was...}


Also wird diese Prozedur aufgerufen, mitder ich rekursiv suche:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
function search(suche,links,rechts:integer):integer;
var mitte:integer;
begin
  mitte:= (links + rechts) div 2;
  if daten[mitte] = suche then
    begin // erfolg...
     search:= mitte;
     erg:=mitte;
     end else
     If daten[mitte] < suche then
      search(suche,mitte+1,rechts)  // gehe nach rechts...
      else
      search(suche,links,mitte-1); // gehe nach links...
end;


So, die Auswertung mache ich am ende so: (+ das löschen der letzten Zahl)
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
  //auswerten
{fortsetzung von Button1.click}
  if erg = max then
  label1.Caption:='Die Zahl '+inttostr(suche)+' wurde nicht gefunden !' else
  label1.Caption:='Die Zahl '+inttostr(suche)+' wurde gefunden !'+#13+'Sie befindet sich an Position '+inttostr(erg);

  // letzte zahl löschen..., weil sonst immer mehr ans ende geschrieben werden...
  setlength(daten,max);
end; //ende von Button1.click


SO nun habe ich in der Rekursion etwas markiert. Hier ist das eigentliche Problem. Ich weise der Funktion ein Ergebnis zu, nämlich die richtige Position. Im Compiler steht da auch die rcihtige Position der 5, nämlich 4.
Bei der Auswertung allerding bekommt die Variable ergebnis den letzten Wert des Arrays zugewiesen. Daraus folgt, dass das Programm sagt, dass die Zahl nicht gefunden wurde, obwol die Rekursion das richtige Ergebis hat. Deswegen verwende ich zZt. eine Hilfvariable (erg).

Warum liefert mir die Rekursion nicht das korrekte Ergebnis? warum muss ich diesen "Umweg" gehen?

kann mir jemand evtl n Tipp geben?

danke, hibbert.

_________________
I kunnen väl svara endast ja eller nej
Om i viljen eller nej
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: So 07.05.06 14:37 
So sollte es gehen. Du musst das Ergebnis in die höheren Rekursionsstufen "durchreichen"
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
function search(suche,links,rechts:integer):integer;   
var mitte:integer;   
begin   
  mitte:= (links + rechts) div 2;   
  if daten[mitte] = suche then   
  begin // erfolg...   
     search:= mitte;   
     erg:=mitte;   
  end else   
    If daten[mitte] < suche then   
      search := search(suche,mitte+1,rechts)  // gehe nach rechts...   
    else   
      search := search(suche,links,mitte-1); // gehe nach links...   
end;

_________________
We are, we were and will not be.
hibbert Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1007

WinServer2003, Win XP, Linux
D6 Pers, D05
BeitragVerfasst: So 07.05.06 14:53 
man sieht den Wald vor lauter Bäumen nicht mehr :lol:

stimmt ja, hab ich vollkommen vergessen :oops:

danke für die Antwort, jetzt geht es.

hibbert

_________________
I kunnen väl svara endast ja eller nej
Om i viljen eller nej