Autor Beitrag
Tristan
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 106



BeitragVerfasst: Sa 05.04.08 10:27 
Hallo vielleicht könnt Ihr mir einen Tipp geben wo der Fehler in meinem Algorithmus liegt. Ich möchte von einer Internetseite die Zahlengrenze zwischen zwei Seiten herausfinden.
Beispiel: dass heißt die Seiten 1315605.html - 1516705.html geben beim Aufruf den Text 'Beispiel 2007' zurück die Seiten danach also 1516705.html - 1714605.html geben beim Aufruf 'Beispiel 2008' zurück.

Nun möchte ich genau die Grenze zwischen diesen beiden Bereichen herausfinden: 1516705.html
Ich habe versucht dies mit der Binären Suche zu lösen, bin mir aber nicht sicher ob man das damit überhaupt realisieren kann, da man ja hier zwei Zahlenbereiche hat. Dies müsste man als Bedingung mit einbauen!?

Die function in dem nachfolgenden Code simuliert die Rückgabe des Browsers, true steht für 'Beispiel 2007' false steht für 'Beispiel 2008'

ausblenden volle Höhe 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:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
procedure TMain.bokClick(Sender: TObject);
begin
repeat
inc(anzahl);
If (egun_test(mitte)=true) THEN rechts:=mitte
 ELSE links:=mitte+1;

 mitte:=(links+rechts) DIV 2;
 emitte.Text:=INTTOSTR(mitte);

until (egun_test(mitte)=true) and (egun_test(mitte+1)=false);
eergebnis.Text:=INTTOSTR(rechts);
eanzahl.Text:=INTTOSTR(anzahl);
end;

procedure TMain.bobClick(Sender: TObject);
begin
 links:=1;
 anzahl:=0;
 n:=rgOG.itemindex; rechts:=STRTOINT(rgOG.items[n]);
 mitte:=(links+rechts) DIV 2;
 emitte.Text:=INTTOSTR(mitte);
 eergebnis.Text:='-';
 eanzahl.Text:='-';
end;

function TMain.egun_test(Artikel:integer):bool;
Begin
 case Artikel of
  1013601..1613601:result:=true;
  1613602..1715605:result:=false;
  else result:=false;
  end;
End;


Gruß Tristan
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Sa 05.04.08 11:42 
Hallo,

Du suchst die Grenze also musst Du diese auch abfragen.
Zuerst einmal musst Du Dir sicher sein, das die Daten sortiert und eine Grenze existiert.
Sind die Daten sortiert, reicht ja schon der Test, ob Datum[rechts] <>Datum[links].
Wenn dem so ist dann testest Du ganz simpel

mitte = (rechts+links) DIV 2;
If Datum[mitte]<> Datum[mitte+1] => Gefunden!
If Datum[mitte]= Datum[rechts] => rechts= mitte+1, da Datum[mitte]=Datum[mitte+1] ist
else links= mitte;

ICh habe es mal schnell in Pascal getestet::
ausblenden volle Höhe 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:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
program test2;

var
  Anzahl,rechts,mitte,links:integer;
  emitte: string;

  function egun_test(Artikel:integer):bool;
Begin
 case Artikel of
  1013601..1613601:result:=true;
  1613602..1715605:result:=false;
  else result:=false;
  end;
end;

function GrenzFind(rechts,links:integer):integer;
begin
while links > rechts do
  begin
  result :=(links+rechts) DIV 2;
  str(result,emitte);
  writeln(emitte);
  inc(anzahl);
  If egun_test(result)<>egun_test(result+1) then
    begin
    writeln('Heureka');
    exit;
    end;
  If (egun_test(result)=true) THEN
    rechts:=result+1
  ELSE
    links:=result;
  end;
writeln(anzahl);
result := -1;
end;


begin
rechts :=1013601;
links := 1715605;
Anzahl :=0;
mitte := GrenzFind(rechts,links);
writeln('Anzahl ',Anzahl);
If Mitte > 0 then
  writeln('Die Grenze ist bei ',mitte,' und ',mitte+1)
else
  writeln('War wohl nichts');
readln;


End.
Tristan Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 106



BeitragVerfasst: Sa 05.04.08 12:35 
Vielen Dank du hast das Super erklärt, ich bin jetzt auch dahinter gestiegen. Ich sitze an dem Problem schon seit gestern Nachmittag und bin einfach nicht drauf gekommen. Meine erste Idee war gewesen rekursiv immer durch 10 zu dividieren und in diesen Schritten zu subtrahieren. Also 1714605 - 100000, wenn Bereich gefunden weiter eingrenzen mit 10000, 1000 100, 10, 1. Und dann bin ich noch über die Binäre Suche gestolpert, ein wirklich interessantes Verfahren.

Euch nen schönes Wochenende
Ich markiere das mal als gelöst.
Tristan