A kiválasztott változat és az aktuális verzió közötti különbségek a következők.
Következő változat | Előző változat | ||
inf-prog-fszi:logaritmikus_kereses_tetele [2017/06/15 11:57] beistvan létrehozva |
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, | ||
+ | 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. | ||
+ | </ | ||
+ | |||
+ | **Megjegyzés: | ||
+ | azért hívják logaritmikus keresésnek, | ||
+ | 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]: | ||
+ | //Tömb rendezése | ||
+ | for i:=1 to n-1 do | ||
+ | for j:=i+1 to n do | ||
+ | if a[j]< | ||
+ | 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: | ||
+ | writeln(' | ||
+ | repeat | ||
+ | k: | ||
+ | if a[k]<x then als:=k+1; | ||
+ | if a[k]>x then fel:=k-1; | ||
+ | until (als> | ||
+ | van: | ||
+ | if van then | ||
+ | writeln(' | ||
+ | else | ||
+ | writeln(' | ||
+ | readln; | ||
+ | end. | ||
+ | |||
+ | </ | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | Órai gyakorlat | ||
+ | |||
+ | <code pascal logaritmikus_kereses.pas> | ||
+ | program logaritmikus_kereses; | ||
+ | const n=8; | ||
+ | var i, | ||
+ | van: | ||
+ | a: array [1..n] of integer; | ||
+ | begin | ||
+ | writeln(' | ||
+ | for i:=1 to n do | ||
+ | begin | ||
+ | write(' | ||
+ | end; | ||
+ | for i:=1 to n-1 do | ||
+ | for j:=i+1 to n do | ||
+ | if a[j]< | ||
+ | begin | ||
+ | cs:=a[j]; | ||
+ | a[j]:=a[i]; | ||
+ | a[i]:=cs; | ||
+ | end; | ||
+ | write(' | ||
+ | for i:=1 to n do | ||
+ | write(a[i]: | ||
+ | writeln; | ||
+ | // | ||
+ | al:=1; | ||
+ | fel:=n; | ||
+ | write(' | ||
+ | repeat | ||
+ | koz := (al+fel) div 2; | ||
+ | if a[koz]< | ||
+ | if a[koz]> | ||
+ | until (al>fel) or (a[koz]=keresendo); | ||
+ | van := al<=fel; | ||
+ | if van then write(' | ||
+ | readln; | ||
+ | end. | ||
+ | </ |