[PASCAL] Wyszukiwanie binarne

[Tur! 0]

Witam

Mam mały problem z programem.

 

Wszystko jest OK, tylko ostatnia procedura ZNAJDZ coś nie chce działać jak powinna.

Wywala jakiś błąd. Mile widziane uwagi.

 

Program zad3;
uses
	crt;
{================================================================= DEKLARACJE}
const
	n=10;
type
	tablica=array[1..n] of integer;
var
	plik:text;
	A:tablica;
	X:integer;
{================================================================ PROC / FUNK}
Procedure DANE;												{DANE DANE.TXT}
var
	liczba,i:integer;
begin
 randomize;
 Assign(plik,'dane.txt');
 rewrite(plik);
 for i:=1 to n do
  begin
liczba:=random(100);
writeln(plik,liczba);
  end;
 close(plik);
end;

Procedure ODCZYT(var T:tablica;nazwa:string);				{ODCZYT PLIK.TXT}
var
	liczba,i:integer;
begin
 Assign(plik,nazwa);
 reset(plik);
 i:=1;
 while not eof(plik) do
  begin
readln(plik,liczba);
T[i]:=liczba;
INC(i);
  end;
 close(plik);
end;

Procedure SORT(var T:tablica);						{SORTOWANIE PRZEZ WYBOR}
var
	i,j,temp,p_min:integer;
begin
 for j:=1 to n-1 do
  begin
p_min:=j;
for i:=j+1 to n do
 if  T[i]<T[p_min] then p_min:=i;
temp:=T[p_min];
T[p_min]:=T[j];
T[j]:=temp;
  end;
end;

procedure ZNAJDZ(T:tablica);										{ZNAJDZ X}
var
	x,L,R,m,p:integer;
Begin
 writeln;
 write('PROSZE PODAC LICZBE: '); readln(x);
 L:=T[1];
 R:=T[n];
 p:=1;
 While L<=R do
  begin
m:=(L+R) div 2;
If T[m]=x then
 begin
  p:=m;
  break;
 end
		  else
 if T[m]<x then L:=m+1
		   else R:=m-1
  end;
 writeln('SZUKANA LICZBA: ',L);
 readln;
end;

Procedure ZAPIS(T:tablica);								  {ZAPIS ORDER.TXT}
var
	i,liczba:integer;
begin
 Assign(plik,'order.txt');
 rewrite(plik);
 for i:=1 to n do
  begin
liczba:=T[i];
writeln(plik,liczba);
  end;
 close(plik);
end;
{====================================================================== TRESC}
Begin
CLRSCR;
 DANE;
 ODCZYT(A,'dane.txt');
 SORT(A);
 ZAPIS(A);
 ODCZYT(A,'order.txt');
 ZNAJDZ(A);
READKEY;
End.

 

Z góry dziękuje za pomoc

 

Wprowadziłem trochę zmian, ale nadal nie działa:

procedure ZNAJDZ(T:tablica);										{ZNAJDZ X}
var
	x,L,R,m:integer;
Begin
 writeln;
 write('PROSZE PODAC LICZBE: '); readln(x);
 L:=T[1];
 R:=T[n];
 While L<=R do
  begin
m:=(L+R) div 2;
If T[m]=x then
 begin
  writeln('SZUKANA LICZBA: ',m);
  readkey;
  exit;
 end
		  else
 if T[m]<x then L:=m+1
		   else R:=m-1;
  end;
 writeln('BRAK x w tablicy');
 readkey;
end;

 

Dziwne.. dla n=100, n=1000 wszystko działa.. jakieś propozycje?

[209458 867]

Pierwszy błąd jaki znalazłem:

 

zamiast

  L:=T[1];
 R:=T[n];

powinno być

  L:=1;
 R:=n;

[spinaker 0]

ja bym jeszcze dodał R = m

zamiast R = m - 1

[Tur! 0]

Prowadzący ćwiczenia z WDI podał:

Oto algorytm:

 

DANE: T[1..n] liczby naturalne w tablicy; szukamy X

 

1. Niech L=T[1]; R=T[n]; p=1

 

2. Dopóki L<=R wykonuj 3,4,5

 

3. m:= (L+R) div 2

 

4. jeśli T[m]=X to p:=m i KONIEC ALGORYTMU

 

5. jeśli T[m] < X to L=m+1 w przeciwnym wypadku R=m-1

 

6. Brak X w tablicy T

 

7. KONIEC ALGORYTMU

 

ale zaraz wprowadzę poprawki i zobaczę jak działa.

 

Pozdrawiam

 

Pierwszy błąd jaki znalazłem:

 

zamiast

  L:=T[1];
 R:=T[n];

powinno być

  L:=1;
 R:=n;

 

Sprawdziłem i błąd naprawiony, widocznie, prowadzący popełnił gafę. Dziękuję bardzo za zainteresowanie i pomoc.

 

ja bym jeszcze dodał R = m

zamiast R = m - 1

 

R=m-1 jest poprawne, w chwili, gdy użyłem R=m program się zapętla

[209458 867]

R=m-1 jest poprawne, w chwili, gdy użyłem R=m program się zapętla

 

Aby użyć R=m trzeba by nieco zmodyfikować algorytm:

 

1. Niech L=1; R=n; p=1

 

2. Dopóki L<R wykonuj 3,4

 

3. m:= (L+R) div 2

 

4. jeśli T[m] < X to L=m+1 w przeciwnym wypadku R=m

 

6. Jeśli T[L] <> X to Brak X w tablicy T w p.p. p=L

 

7. KONIEC ALGORYTMU

 

Jest nawet statystycznie szybszy od tego, który mieliście na wykładach, ale różnica jest minimalna.

[spinaker 0]

no tak nie dopisałem, że trzeba dać L < R, przepraszam za błąd.