Umíte pascalsky - 18.lekce ...

Umíte pascalsky?
18.lekce
Vytisknout  

Vyhledávání v poli

Při hromadném zpracování dat často potřebujeme najít informace, které nás zajímají. Ukážeme si vyhledávání prvků daných vlastností v poli. Nechť je dáno pole prvků a určitá vlastnost V, kterou má mít hledaný prvek. Nejpoužívanějšími metodami jsou

A. Lineární vyhledávání
B. Vyhledávání s nárazníkem
C. Binární vyhledávání

Příklad:
Mezi čísly 2 , 5 , 7 , 15 , 7 , 32 , 7 , 42 , 50 hledáme zvolené číslo, např. 7.

Lineární vyhledávání

Při tomto typu vyhledávání procházíme postupně prvky za sebou, dokud nenalezneme
- první . . . na posici 3
- poslední . . . na posici 7
- všechny . . . na posici 3 , 5 , 7
prvky, mající požadovanou vlastnost.

Myšlenka (hrubý algoritmus):
- první:
<opakuj dokud (nemá prvek požadovanou vlastnost V) a (není konec pole)>
    <přejdi na další prvek pole>
<jestliže (má vlastnost V)>
    <napiš jeho index>
    <jinak nenalezen>

- poslední:
obdobně, s tím rozdílem, že začínáme od posledního prvku pole a postupujeme směrem k začátku

- všechny:
<od prvního do posledního prvku pole prováděj
    <jestliže má vlastnost V, napiš jeho index>
    <přejdi na další prvek pole>

Vyhledávání s nárazníkem

Tato metoda je modifikací lineárního vyhledávání (první, poslední), kdy dvě podmínky setrvání v cyklu - (nemá prvek požadovanou vlastnost V) a (není konec pole) - nahradíme jednou.
Prvek s požadovanou vlastností totiž uložíme za poslední prvek pole - říkáme mu nárazník - a toto nové pole prohledáváme tak dlouho, dokud prvek s požadovanou vlastností nenalezneme. Potom podle indexu nalezeného prvku rozhodneme, zda to je prvek původního pole a vyhledávání bylo úspěšné nebo je to nárazník a tedy původní pole tento prvek neobsahuje.

Příklad:
V devítiprvkovém poli čísel 2 , 5 , 7 , 15 , 21 , 32 , 35 , 42 , 50 hledáme číslo 7.

Přidáme jako desátý prvek hledané číslo 7 (nárazník).
2 , 5 , 7 , 15 , 21 , 32 , 35 , 42 , 50 , 7
Při hledání čísla se zastavíme na čísle 7 (s indexem 3) a to je skutečně první nalezené číslo dělitelné 7 v zadaném poli.

Příklad:
V devítiprvkovém poli čísel 2 , 5 , 6 , 15 , 20 , 32 , 34 , 42 , 50 hledáme číslo 7.

Přidáme jako desátý prvek hledané číslo 7 (nárazník).
2 , 5 , 6 , 15 , 20 , 32 , 34 , 42 , 50 , 7
Při hledání čísla se zastavíme na čísle 7 (s indexem 10). Ale ten je větší než původní počet prvků, proto se v původním poli číslo 7 nenachází.

Myšlenka (hrubý algoritmus):
<uložení nárazníku za poslední prvek>
<opakuj dokud (nemá prvek požadovanou vlastnost V)>
    <přejdi na další prvek pole>
<jestliže index je větší než počet prvků pole>
    < napiš nenalezen>
    <jinak napiš jeho index>

Binární vyhledávání

V uspořádaném úseku pole lze použít efektivnějšího způsobu vyhledávání (než lineární), který odpovídá hledání ve slovníku. Ukážeme si to na příkladě:

příklad Příklad:
V úseku čísel: 1 , 3 , 4 , 5 , 7 , 9 , 10 hledáme číslo 7.
Úsek rozpůlíme (najdeme střed)
1 , 3 , 4 , 5 , 7 , 9 , 10
a zjistíme, zda 7 leží v levé nebo pravé půlce.
Protože 7 > 5 , leží sedmička v pravé půlce. Novým zkoumaným úsekem bude úsek:
7 , 9 , 10
Opět úsek rozpůlíme (najdeme střed)
7 , 9 , 10
Protože 7 < 9 , leží sedmička v levé půlce. Novým zkoumaným úsekem bude úsek:
7
Opět úsek rozpůlíme (najdeme střed)
7
Protože 7 = 7 (hledaný prvek je střed úseku), hledání se ukončí, číslo 7 bylo nalezeno.

Příklad:
V úseku čísel: 2 , 3 , 5 , 6 , 7 , 10 , 12 , 13 hledáme číslo 4.
Úsek rozpůlíme (najdeme střed)
2 , 3 , 5 , 6 , 7 , 10 , 12 , 13 a zjistíme, zda 4 leží v levé nebo pravé půlce.
Protože 4 < 6 , leží čtyřka v levé půlce. Novým zkoumaným úsekem bude úsek:
2 , 3 , 5
Opět úsek rozpůlíme (najdeme střed)
2 , 3 , 5
Protože 4 > 3 , leží čtyřka v pravé půlce. Novým zkoumaným úsekem bude úsek:
5
Opět úsek rozpůlíme (najdeme střed)
5
Protože 4 < 5 , leží čtyřka v levé půlce. Ale tento úsek je prázdný. Nelze dále pokračovat. Číslo 7 nebylo nalezeno.

Myšlenka (hrubý algoritmus):
<zkoumaným úsekem je celé pole>
<opakuj
   <urči střed zkoumaného úseku>
   <jestliže je hledaný prvek menší než střed>
       < pak novýn zkoumaným úsekem bude levá část od středu>
       < jinak novýn zkoumaným úsekem bude pravá část od středu>
<až bude střed=hledaný prvek nebo zkoumaný úsek prázdný>
<jestliže střed=hledaný prvek>
    <pak napiš index nalezeného prvku>
    < jinak prvek nebyl nalezen>

Příklad: Sestavte program Vyhledavani, umožňující podle volby uživatele:
1) Zadat zvolený počet celých čísel
2) Zvolit hledané číslo mezi zadanými čísly
3) Najít první výskyt hledaného čísla mezi zadanými čísly
4) Najít poslední výskyt hledaného čísla
5) Najít všechny výskyty hledaného čísla
6) Najít první výskyt hledaného čísla pomocí nárazníku
7) Najít výskyt hledaného čísla binárním vyhledáváním
Všechny úkoly řešte užitím procedur s parametry.

Program Vyhledavani může vypadat takto:

program Vyhledavani;
  const Max = 50;
  type TCisla=array[1..Max] of integer;
  var cisla:TCisla;
         pocet,volba,hledam,tam,numer,pom:integer;

{globální proměnné}
 
procedure Nacti_cisla(var kolik:integer;var cisilka:TCisla);
  var ktere : integer;
  begin
    writeln('Zadejte pocet cisel:');readln(kolik);
    for ktere:=1 to pocet do
        begin
           writeln('Zadej ',ktere,'. cislo:');
           readln(cisilka[ktere]);
        end;
{zadání počtu čísel}


{načítání čísel}

  end;

procedure Tisk_cisel(kolik:integer;cisilka:TCisla);
  var ktere : integer;
  begin
    for ktere:=1 to kolik do
           write(cisilka[ktere],' ');
    writeln;
{tisk zadaných čísel}


  end;

procedure Nacti_hledane(var hledej:integer);
  begin
    writeln('Zadejte hledane cislo:');
    readln(hledej);
{zadání hledaného čísla}
  end;

procedure Najdi_prvni(kolik:integer;cislicka:TCisla);
  var posice:integer;
  begin
    Tisk_cisel(kolik,cislicka);
    posice:=1;
    while ((cislicka[posice] <> hledam) and (posice < kolik)) do
      posice:=posice+1;
    if (cislicka[posice]) = hledam
         then writeln('Cislo je na posici ',posice)
         else writeln('Cislo nenalezeno');
{Kontrolní tisk čísel)
{prohledávání od začátku)
{dokud to není hledané č. a není konec pole)
{přejdi na další číslo)
{je-li to hledané číslo)
{napiš jeho posici)
{napiš nenalezeno)
  end;

procedure Najdi_posledniho(kolik:integer;cislicka:TCisla);
  var posice:integer;
  begin
    Tisk_cisel(kolik,cislicka);
    posice:=kolik;
    while ((cislicka[posice] <> hledam) and (posice>1)) do
      posice:=posice-1;
    if (cislicka[posice]) = hledam
         then writeln('Cislo je na posici ',posice)
         else writeln('Cislo nenalezeno');
{Kontrolní tisk čísel)
{prohledávání od konce)
{dokud to není hledané č. a není začátek pole)
{přejdi na předchozí číslo)
{je-li to hledané číslo)
{napiš jeho posici)
{napiš nenalezeno)
  end;

procedure Najdi_vsechny(kolik:integer;cislicka:TCisla);
  var posice:integer;
  begin
    Tisk_cisel(kolik,cislicka);
    write('Cislo bylo nalezeno na techto posicich: ');
    for posice:=1 to kolik do
      if (cislicka[posice]) = hledam then write(posice,' ');
    writeln;
{Kontrolní tisk čísel)

{opakuje pro všechna čísla)
{je-li to hledané číslo, vytiskne jeho posici)

  end;

function Naraznik(kolik:integer;cislicka:TCisla):integer;
  var posice:integer;
  begin
    Tisk_cisel(kolik,cislicka);
    cislicka[kolik+1]:=hledam;
    posice:= 1;
    while cislicka[posice] <> hledam do
        posice:=posice+1;
    if posice > kolik
         then Naraznik:=0
         else Naraznik:=posice;
{Kontrolní tisk čísel)
{vložení nárazníku za poslední číslo)
{hledáme od začátku)
{dokud číslo není hledané číslo)
{přejdi na další číslo)
{je-li posice větší než počet čísel)
{funkce Naraznik vrátí 0)
{jinak vrátí posici nalezeného čísla)
  end;

procedure Najdi_binarne(kolik:integer;cislicka:TCisla);
  var dolni,horni,stred:integer;
  begin
    Tisk_cisel(kolik,cislicka);
    dolni:=1;horni:=kolik;
    repeat
      stred:=(dolni+horni) div 2;
      if hledam < cislicka[stred] then horni:=stred-1
                                                     else dolni:=stred+1;
    until (hledam = cislicka[stred]) or (dolni>horni);
    if hledam = cislicka[stred] then writeln('Cislo nalezeno na posici ',stred)
                                                   else writeln('Cislo nenalezeno');
{Kontrolní tisk čísel)
{aktuálním úsekem je celé pole)
{opakuj)
{zjisti střed)
{je-li hledané č.vlevo,aktualní úsekem bude levá část,jinak pravá část)
{dokud střed není hledané nebo není prázdný)
{je-li střed hledané číslo,napiš posici)
{jinak napiš nenalezeno)
  end;

Begin

{Hlavní program}
 Repeat
   writeln('Program Vyhledávání umožňuje:');
   writeln('1. Zadat cisla');
   writeln('2. Zadat hledane cislo');
   writeln('3. Najit prvni cislo');
   writeln('4. Najit posledni cislo');
   writeln('5. Najit vsechny cisla');
   writeln('6. Najit prvni naraznikem');
   writeln('7. Najit cislo binarne');
   writeln('0. Ukoncit');
   writeln('Zadejte svoji volbu:');
   readln(volba);
   case volba of
     1: Nacti_cisla(pocet,cisla);
     2: Nacti_hledane(hledam);
     3: Najdi_prvni(pocet,cisla);
     4: Najdi_posledniho(pocet,cisla);
     5: Najdi_vsechny(pocet,cisla);
     6: if Naraznik(pocet,cisla)=0
                                then writeln('Toto cislo nebylo nalezeno')
                                else writeln('Cislo je na posici ', Naraznik(pocet,cisla));
     7: Najdi_binarne(pocet,cisla);
     0: writeln('Nashledanou');
   end;
 until volba = 0;
{opakuj}
    {nabídka činností}





    {vvýběr činnosti}
    {provedení zvolené činnost}


       


End.



Domácí úkol:

    Sestavte program Slovnik, který umožňuje zadat do pole Ceske zadaný počet českých slov a do pole Anglicke odpovídající anglická slova. Potom pro zvolené české slovo najde odpovídající anglické a obráceně.

On-line účast na řešení úkolu

Řešit úkol Prohlídka hodnocení úkolu Dotazy,připomínky

Pomocí volby Řešit můžete (po přihlášení) odeslat vaše řešení domácího úkolu (každý úkol smíte řešit jen jednou). Volbou Hodnocení si přečtete hodnocení a komentář od vyučujícího. Dotaz nebo připomínku můžete opakovaně zasílat pomocí tlačítka Dotazy, Komunikace (na levém okraji) zobrazuje příklad možné komunikace s vyučujícím.