Felhasználói eszközök

Eszközök a webhelyen


inf-prog-fszi:logaritmikus_kereses_tetele

Különbségek

A kiválasztott változat és az aktuális verzió közötti különbségek a következők.

Összehasonlító nézet linkje

Előző változat mindkét oldalon Előző változat
Következő változat
Előző változat
inf-prog-fszi:logaritmikus_kereses_tetele [2017/06/17 20:55]
beistvan
inf-prog-fszi:logaritmikus_kereses_tetele [2017/06/21 12:25] (aktuális)
beistvan
Sor 1: Sor 1:
 +====== Logaritmikus keresés tétele ======
  
 +
 +**Általános feladat**: N elemű rendezett sorozat; egy keresett elem (X). Szerepel-e a keresett elem a sorozatban és ha igen, akkor mi a sorszáma.
 +Kihasználjuk, hogy a sorozat rendezett, így el tudjuk dönteni, hogy a keresett elem az éppen vizsgált elemhez képest hol helyezkedik el.\\
 +Al, F: intervallum alsó és felső végpontjai.
 +
 +<code bash logkeres.txt>
 +Eljárás:
 + Al := 1
 + F := N
 + Ciklus
 + K := INT((Al + F) / 2)
 + Ha A(K) < X akkor Al := K + 1
 + Ha A(K) > X akkor F := K - 1
 + amíg Al <= F és A(K) != X (amíg Al > F vagy A(K) = X)
 + Ciklus vége
 + VAN := Al <= F
 + Ha VAN akkor SORSZ := K
 +Eljárás vége.
 +</code>
 +
 +**Megjegyzés:**
 +azért hívják logaritmikus keresésnek, mert a ciklus lépésszáma kb. log N
 +sokkal hatékonyabb rendezett sorozatra, mint a lineáris keresés.
 +
 +
 +Pascal forráskód
 +
 +<code pascal binaris_logaritmikus_kereses.pas>
 +program binaris_logaritmikus_kereses;
 +const n = 10;
 +var a: array [1..n] of integer;
 +    i, j, c, x, als, fel, k: integer;
 +    van: boolean;
 +begin
 +  randomize;
 +  //A tömb elkészítése
 +  for i:=1 to n do
 +    a[i]:=random(9);
 +  //Tömb rendezése
 +  for i:=1 to n-1 do
 +    for j:=i+1 to n do
 +      if a[j]<a[i] then begin
 +        c:=a[j];
 +        a[j]:=a[i];
 +        a[i]:=c;
 +      end;
 +  //A rendezett tomb kiiratasa
 +  for i:=1 to n do
 +    write(a[i], ' ');
 +  Writeln;
 +  //Binaris kereses
 +  als:=1;
 +  fel:=n;
 +  x:=random(11);
 +  writeln('a keresett elem: ', x);
 +  repeat
 +    k:=(als+fel) div 2;
 +    if a[k]<x then als:=k+1;
 +    if a[k]>x then fel:=k-1;
 +  until (als>fel) or (a[k]=x);
 +  van:=als<=fel;
 +  if van then
 +    writeln('megtalaltam, a sorszama: ', k)
 +  else
 +    writeln('nincsen meg');
 +  readln;
 +end.
 +
 +</code>
 +
 +[[https://ideone.com/u5EiEy | A <binaris_logaritmikus_kereses.pas> forráskódjának futtatása online ]]
 +
 +Órai gyakorlat
 +
 +<code pascal logaritmikus_kereses.pas>
 +program logaritmikus_kereses;
 +const n=8;
 +var i,j,al,fel,keresendo,koz, cs : integer;
 +    van:boolean;
 +    a: array [1..n] of integer;
 +begin
 +  writeln('Kerem a tomb elemeit: ');
 +  for i:=1 to n do
 +  begin
 +    write('a[',i,'] = '); readln(a[i]);
 +  end;
 +  for i:=1 to n-1 do
 +    for j:=i+1 to n do
 +      if a[j]<a[i] then
 +      begin
 +        cs:=a[j];
 +        a[j]:=a[i];
 +        a[i]:=cs;
 +      end;
 +  write('A rendezett tomb elemei: ');
 +  for i:=1 to n do
 +    write(a[i]:3);
 +  writeln;
 +  //logaritmikus kereses
 +  al:=1;
 +  fel:=n;
 +  write('A keresendo szam: '); readln(keresendo);
 +  repeat
 +    koz := (al+fel) div 2;
 +    if a[koz]<keresendo then al:=koz+1;
 +    if a[koz]>keresendo then fel:=koz-1;
 +  until (al>fel) or (a[koz]=keresendo);
 +  van := al<=fel;
 +  if van then write('Megvan, sorszama: ',koz)else write('Nincs meg');
 +  readln;
 +end.
 +</code>