Pouze tento týden sleva až 80 % na e-learning týkající se C# .NET. Zároveň využij akci až 30 % zdarma při nákupu e-learningu - Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Lekce 1 - Hledání extrému (minima a maxima) v poli

Algoritmus pro nalezení největšího nebo nejmenšího prvku v poli je sice zřejmý, ale pro jistotu i úplnost jsem se ho rozhodl uvést.

Budu zde popisovat vyhledání maxima, vyhledání minima bude potom analogické. Algoritmus bude mít zpočátku v proměnné uložené výchozí maximum. Potom projede pole prvek po prvku a pokud je nějaký prvěk větší, než toto maximum, bude novým maximem tento prvek. Po projetí pole bude v proměnné jistě maximum z daných hodnot v poli.

Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

Teď jak je to s tím výchozím maximem. Některé z vás jistě napadlo dát mu hodnotu 0. Co když ale budeme mít pole plné záporných čísel? Naše maximum bude maximem i po průchodu polem (protože nic nebude větší než 0) a jeho hodnota je naprosto chybná, protože se v poli ani nevyskytuje. Dáme mu tedy nějakou hodnotu z pole, vůbec nezáleží jakou. Nabízí se např. první prvek, protože k němu máme nejsnažší přístup.

V praxi se také do proměnné neukládá maximální hodnota, ale index s maximálním prvkem (v případě výchozího prvního prvku by byl tedy 0). Mnohdy nás totiž zajímá index, pod kterým se maximální hodnota skrývá, více, než kolik maximální hodnota číselně je. Když např. budeme mít v poli zaměstnance (objekty) a budeme chtít vypsat toho s nejvyšším platem, nebude nás zajímat jeho plat, ale jeho jméno. Když budeme mít index toho zaměstnance, můžeme si potom vypsat jeho libovolný údaj včetně jeho platu nebo jeho jména.

Na závěr lze dodat, že časová složitost algoritmu je O(n) a neměli bychom tedy operaci provádět příliš často. Pokud tomu tak bude, měli bychom se zamyslet nad vhodnější datovou strukturou, než je pole. Nabízí se například setříděné pole nebo halda.

Zdrojové kódy

Ve zdrojových kódech program v jednom průchodu spočítá minimum i maximum z daného pole.

  • // vrátí pozici minima ze zadaného pole
    public static int minimum (int[] list) {
      int min = 0;
      for (int i = 0; i < list.length; i++)
      if (list[i] < list[min])
      min = i;
      return min;
    }
    
    // vrátí pozici maxima ze zadaného pole
    public static int maximum (int[] list) {
      int max = 0;
      for (int i = 0; i < list.length; i++)
      if (list[i] > list[max])
      max = i;
      return max;
    }
  • // vrátí pozici minima ze zadaného pole
    public static int minimum (int[] list) {
      int min = 0;
      for (int i = 0; i < list.Length; i++)
      if (list[i] < list[min])
      min = i;
      return min;
    }
    
    // vrátí pozici maxima ze zadaného pole
    public static int maximum (int[] list) {
      int max = 0;
      for (int i = 0; i < list.Length; i++)
      if (list[i] > list[max])
      max = i;
      return max;
    }
  • // vrati minumum ze zadaneho pole
    function minimum(var list: array of integer): integer;
    var min, i: integer;
    begin
      min:=0;
      for i:=0 to (length(list) - 1) do
      if (list[i] < list[min]) then
      min:=i;
      result:=min;
    end;
    
    // vrati minumum ze zadaneho pole
    function maximum(var list: array of integer): integer;
    var max, i: integer;
    begin
      max:=0;
      for i:=0 to (length(list) - 1) do
      if (list[i] > list[max]) then
      max:=i;
      result:=max;
    end;
  • # vrati pozici minima ze zadaneho pole
    def minimum(list)
      min = 0
      list.length.times { |i| min = i if (list[i] < list[min]) }
      return min
    end
    
    # vrati pozici maxima ze zadaneho pole
    def maximum(list)
      max = 0
      list.length.times { |i| max = i if (list[i] > list[max]) }
      return max
    end
  • // vrátí pozici minima ze zadaného pole
    function minimum(array $list) {
      $min = 0;
      for ($i = 0; $i < count($list); $i++)
          if ($list[$i] < $list[$min])
            $min = $i;
      return $min;
    }
    
    // vrátí pozici maxima ze zadaného pole
    function maximum(array $list) {
      $max = 0;
      for ($i = 0; $i < count($list); $i++)
        if ($list[$i] > $list[$max])
            $max = $i;
      return $max;
    }
    
    

V další lekci, Sekvenční vyhledávání, si ukážeme velmi jednoduchý algoritmus pro vyhledávání prvku v nesetříděné datové struktuře (poli, seznamu) a jeho následné vylepšení malým trikem.


 

Všechny články v sekci
Vyhledávací algoritmy
Přeskočit článek
(nedoporučujeme)
Sekvenční vyhledávání
Článek pro vás napsal David Čápka
Avatar
Uživatelské hodnocení:
12 hlasů
David je zakladatelem ITnetwork a programování se profesionálně věnuje 13 let. Má rád Nirvanu, sushi a svobodu podnikání.
Unicorn university David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity

 

 

Komentáře
Zobrazit starší komentáře (24)

Avatar
DarkCoder
Člen
Avatar
DarkCoder:10. února 20:29

Prkotina, no nevím zda bych to tak nazval. Pořád lepší začátečník než někdo kdo v PHP nenapsal jedinou řádku kódu. 😀 Pouze zkušenosti. Někdy nastanou při provádění vícero úkonů najednou vedlejší efekty, kde to nedělá to co bychom chtěli. Pak je dobré si to celé rozdělit na dílčí části, které se snáze ladí.

Odpovědět
10. února 20:29
"Chceš-li předávat své znalosti, měj kvalitní podklady."
Avatar
Odpovídá na DarkCoder
Petra Petty Kunzová:10. února 21:13

Tak děkuji, že jsi se podělil o svou zkušenost :D Koukala jsem a ptala se různě po netu, ale všude bylo pole definované . Jen jeden kamarád mi udělal aspoň osnovu, ovšem v basic :D . Od toho vyplynulo přiřazení náhodného čísla v echu ;) Polovina se mi povedla samotné, ale to max a min s náhodnými čísly už mi nešlo do hlavy . Takže opravdu moc díky. Posouvá mne to o kousek dál v odhodlání ;)

Editováno 10. února 21:14
Odpovědět
10. února 21:13
Kam míří naše pozornost, tam energie a tam se i objeví naše výsledky .
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Petra Petty Kunzová
DarkCoder:10. února 21:41

Je důležité k tomu takto přistupovat a pokusit se vyřešit úlohu vlastními silami a překonat překážku. Jen tak se člověk posune dál. Pokud si z toho všeho lze něco vzít a využít toho v další práci, pak debata měla smysl. 😊

Odpovědět
10. února 21:41
"Chceš-li předávat své znalosti, měj kvalitní podklady."
Avatar
Odpovídá na DarkCoder
Petra Petty Kunzová:17. února 14:54

To máš pravdu. :) A mám ještě dotaz. Chtěla bych taky vyřešit, jak barevně označit pole, kde se vyskytuje minimální prvek nebo maximální (to je jedno). Nechci řešení tady v diskuzi, ale aspoň tip kde se můžu podívat . Zatím bez souboru stylů. Potřebuji jen vědět kam to přiřadit. Zatím se mi pole barvilo mimo nebo na více místech. Jsem vděčná za jakoukoliv radu ;) Děkuji.

Odpovědět
17. února 14:54
Kam míří naše pozornost, tam energie a tam se i objeví naše výsledky .
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Petra Petty Kunzová
DarkCoder:17. února 15:25

Pro barevné zvýraznění minima a maxima je třeba pozměnit stávající kód. Je to z důvodu toho, že minimum a maximum lze určit až po projetí všech prvků a vyžaduje to zpětný zásah do vygenerovaného kódu. V tomto případě je třeba nejprve najít minimum a maximum bez HTML formátování, tedy čistě programátorsky. Nestačí pouze hodnota, ale je třeba si uchovat i indexy. Po získání indexů již lze vygenerovat tabulku. Uvnitř obou for cyklů se bude testovat na indexy minima a maxima. Pokud iterační proměnné budou odpovídat pozici minima, nastaví se styl pro barevný text. Vypíše se hodnota a ukončí vypisování daným barevným stylem. Ještě je třeba testovat zda minimum a maximum jsou si rovny. To proto, že bude barva textu odlišná. Pro minimum např. červená, maximum modrá, pokud minimum bude rovno maximu tak fialová.

Odpovědět
17. února 15:25
"Chceš-li předávat své znalosti, měj kvalitní podklady."
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Petra Petty Kunzová
DarkCoder:19. února 22:37

Jinými slovy, zkus následující kód:

<?php
$r = $_POST['radek'];
$s = $_POST['sloupec'];
$matice = [[]];
$minElement = PHP_INT_MAX;
$maxElement = PHP_INT_MIN;
$imin = $imax = -1;
$jmin = $jmax = -1;

for ($i = 0; $i < $r; $i++){
    for ($j = 0; $j < $s; $j++) {
        $matice[$i][$j] = rand(-100, 100);
        if ($matice[$i][$j] < $minElement) {
            $minElement = $matice[$i][$j];
            $imin = $i;
            $jmin = $j;
        }
        if ($matice[$i][$j] > $maxElement) {
            $maxElement = $matice[$i][$j];
            $imax = $i;
            $jmax = $j;
        }
    }
}

echo('<table border="1">');
for ($i = 0; $i < $r; $i++){
    echo('<tr>');
    for ($j = 0; $j < $s; $j++) {
        if(($i == $imin)&&($j == $jmin)){
            if(($imin == $imax)&&($jmin == $jmax)){
                echo('<td style="color:#ff00ff">' . $matice[$i][$j] . '</td>');
            }
            else echo('<td style="color:#ff0000">' . $matice[$i][$j] . '</td>');
        }
        elseif(($i == $imax)&&($j == $jmax)){
            echo('<td style="color:#0000ff">' . $matice[$i][$j] . '</td>');
        }
        else echo('<td>' . $matice[$i][$j] . '</td>');
    }
    echo('</tr>');
}
echo('</table>');

echo("Maximus v poli je " . $maxElement . " a minimus je " . $minElement . " .<br />")
?>
Odpovědět
19. února 22:37
"Chceš-li předávat své znalosti, měj kvalitní podklady."
Avatar
Odpovídá na DarkCoder
Petra Petty Kunzová:20. února 21:52

Konečně jsem se k tomu zase dostala a mockrát ti děkuji. Funguje to parádně. 👍 Získala jsem nejen radu nad zlato, ale zase další vědomost . Je o něčem jiném napsat kód s jasně zadanými hodnotami, ale na základě náhodných je to pro začátečníka docela oříšek. Tedy pro mne určitě.

Odpovědět
20. února 21:52
Kam míří naše pozornost, tam energie a tam se i objeví naše výsledky .
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Petra Petty Kunzová
DarkCoder:20. února 22:46

Není zač, vypadá to dobře. I já se něčemu novému přiučil ikdyž na vytvoření byť i primitivní webové aplikace to stále není. 😀 Práce s náhodnými čísly se nijak neliší od klasického vstupu uživatele. To nejnáročnější na tom je, že i malá změna v chování programu může způsobit velkou změnu v zápisu implementace. Což byl i tento případ. Samozřejmě stále je co vylepšovat, vymýšlet nové věci. Na tom se člověk nejvíc naučí, neboť to vytváří myšlenky jak co realizovat, což je pro další práci neocenitelné. Například pokud bude více minim nebo maxim, vybrat náhodně z nich, ne jen to první nebo je vyznačit všechny, atd. Čím více úspěšně dokončených dílčích úkolů, tím více motivace do další práce. 😊

Odpovědět
20. února 22:46
"Chceš-li předávat své znalosti, měj kvalitní podklady."
Avatar
Odpovídá na DarkCoder
Petra Petty Kunzová:21. února 8:32

Je zač :D . Tahle malá aplikace byla původně úloha od jisté firmy a odměnou za vyřešení byla pozvánka k pohovoru. Věděla jsem že to nestíhám, ale i tak jsem se ji snažila vyřešit. Více minim a maxim je dobrá výzva :) Teď se ale přesouvám zase na další plán k dořešení ;)

Odpovědět
21. února 8:32
Kam míří naše pozornost, tam energie a tam se i objeví naše výsledky .
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Petra Petty Kunzová
DarkCoder:21. února 11:19

a odměnou za vyřešení byla pozvánka k pohovoru. Věděla jsem že to nestíhám, ale i tak jsem se ji snažila vyřešit.

Správný přístup. Odměnou za vyřešení úlohy byl posun ve vlastním rozvoji, který je mnohem hodnotnější. :-)

Odpovědět
21. února 11:19
"Chceš-li předávat své znalosti, měj kvalitní podklady."
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 34. Zobrazit vše