Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. 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 2 - Stromová rekurze - Generování všech možností

V předchozí lekci, Úvod do rekurze, jsme se seznámili s pojmem rekurze a procvičili si tvorbu jednoduchých rekurzivních metod.

V dnešním tutoriálu o rekurzivních algoritmech se naučíme, jak využít rekurzi pro vygenerování všech možností při řešení nějakého problému.

Úlohy tohoto typu se obvykle na první pohled tváří složitě, ale právě rekurze zde představuje stručný a elegantní nástroj, kterým je lze rozlousknout na pár řádcích kódu. Řešení těchto typů úloh si ukážeme na třech praktických příkladech pro

  • binární čísla,
  • podřetězce,
  • znaménka + a -.

Binární čísla

Napišme si metodu, která na monitor vypíše všechna k-místná binární čísla. Protože jde o binární čísla, může být na každém z k míst buďto 0 nebo 1. Budeme pracovat s k-prvkovým polem, které bude parametrem metody, a do kterého budeme vznikající čísla zapisovat. Jako druhý parametr dostane metoda index, na který do pole postupně zapíše 0 a 1 a po každém zápisu zavolá svého rekurzivního potomka, aby stejným způsobem zpracoval další index. Pokud je pole plné, metoda ho pouze vypíše:

  • def bin_cisla(pole, index = 0):
        if index == len(pole): # hotovo, vypisujeme
            print(*pole, sep = "")
        else:
            pole[index] = 0
            bin_cisla(pole, index + 1)
            pole[index] = 1
            bin_cisla(pole, index + 1)
  • static void bin_cisla(int[] pole, int index = 0)
    {
        if (index == pole.Length) // hotovo, vypisujeme
            Console.WriteLine(String.Join("", pole));
        else
        {
            pole[index] = 0;
            bin_cisla(pole, index + 1);
            pole[index] = 1;
            bin_cisla(pole, index + 1);
        }
    }
  • public static function bin_cisla(array $pole, int $index = 0): void
    {
        if ($index == count($pole)) // hotovo, vypisujeme
            echo(implode("", $pole) . "<br>");
        else
        {
            $pole[$index] = 0;
            bin_cisla($pole, $index + 1);
            $pole[$index] = 1;
            bin_cisla($pole, $index + 1);
        }
    }
  • public static void bin_cisla(int[] pole, int index)
    {
        if (index == pole.length) // hotovo, vypisujeme
        {
            for (int i = 0; i < pole.length; i++)
                System.out.print(pole[i]);
            System.out.println();
        }
        else
        {
            pole[index] = 0;
            bin_cisla(pole, index + 1);
            pole[index] = 1;
            bin_cisla(pole, index + 1);
        }
    }

Strom volání

Je důležité si uvědomit, v jakém pořadí jsou jednotlivé metody volány, jak postupně dochází k zaplňování a později také k přepisování hodnot na jednotlivých pozicích. Pro dvoumístná binární čísla dostaneme toto schéma:

Strom volání pro binární čísla - Rekurzivní algoritmy

Červená čísla na obrázku ukazují pořadí, ve kterém jsou metody volány. Vidíme, že schéma tvoří strom.

Začínáme prázdným polem, které představuje kořen stromu, a do kterého zapisujeme na první pozici. Vždy nejdříve zapíšeme nulu a zavoláme tutéž metodu, aby ve spodním patře stromu zpracovala další prvek pole (index + 1). Tím vzniká levý podstrom. Potom na danou pozici zapíšeme jedničku a necháme stejným způsobem rekurzivně rozvinout pravý podstrom. Pokud metoda dostane zaplněné pole, pouze ho vypíše na monitor a rekurzivní rozvoj končí.

Kreslete si obrázky, když se snažíte něco pochopit nebo vyřešit. Tato rada platí obecně, nejen pro nácvik rekurze. Tužka a papír jsou užitečnou součástí výbavy programátora.

Podřetězce

Nyní si napišme metodu, která přebírá řetězec a vygeneruje všechny podřetězce, které můžou vzniknout vyškrtáním jednotlivých znaků.

Nejdříve se nad úlohou krátce zamyslíme. Abychom dostali všechny podřetězce, budeme postupně ošetřovat jeden znak po druhém. Začneme u prvního znaku v kořeni pomyslného stromu a rozdělíme generování na dvě větve. V levé větvi znak do podřetězců nezařadíme, v pravé větvi naopak ano. Obě větve necháme dál rozvíjet ve spodních patrech stromu podle dalších znaků úplně stejným postupem – rekurzivním voláním.

Jedna z možných implementací algoritmu vypadá takto:

  • def podretezce(retezec, vysledek = "", index = 0):
        if index == len(retezec):
            print(vysledek)
        else:
            podretezce(retezec, vysledek, index + 1)
    
            # pravý podstrom - znak použijeme
            vysledek += retezec[index]
            podretezce(retezec, vysledek, index + 1)
  • static void podretezce(string retezec, string vysledek = "", int index = 0)
    {
        if (index == retezec.Length)
            Console.WriteLine(vysledek);
        else
        {
            podretezce(retezec, vysledek, index + 1);
    
            // pravý podstrom - znak použijeme
            vysledek += retezec[index];
            podretezce(retezec, vysledek, index + 1);
        }
    }
  • public static function podretezce(string $retezec, string $vysledek = "", int $index = 0): void
    {
        if ($index == mb_strlen($retezec))
            echo($vysledek . "<br>");
        else
        {
            podretezce($retezec, $vysledek, $index + 1);
    
            // pravý podstrom - znak použijeme
            $vysledek .= $retezec[$index];
            podretezce($retezec, $vysledek, $index + 1);
        }
    }
  • public static void podretezce(String retezec, String vysledek, int index)
    {
        if (index == retezec.length())
            System.out.println(vysledek);
        else
        {
            podretezce(retezec, vysledek, index + 1);
    
            // pravý podstrom - znak použijeme
            vysledek += retezec.charAt(index);
            podretezce(retezec, vysledek, index + 1);
        }
    }

Metoda přebírá tři parametry v tomto pořadí:

  1. Vstupní řetězec retezec.
  2. Řetězec vysledek, zpočátku prázdný, do kterého metoda ukládá vznikající podřetězec.
  3. Index znaku index, který ošetřuje (buďto ho zahrne nebo nezahrne do vznikajícího podřetězce).

Podívejme se opět na strom volání, pokud vstupem bude např. řetězec ABC:

Strom volání pro podřetězce - Rekurzivní algoritmy

Na obrázku je každé volání vyznačeno dvojicí údajů:

  • pořadí volání (červeně)
  • stav řetězce vysledek (zeleně).

Hodnota indexu pak odpovídá patru stromu.

Znaménka + a -

Jako poslední příklad si napišme metodu, která přebírá pole celých čísel a vypíše všechny způsoby, jak před jednotlivá čísla umístit znaménka + nebo - tak, aby součet všech zadaných čísel byl 0. Princip úlohy je stejný jako u úloh předchozích. Budeme generovat všechny možnosti, teď ale vypíšeme pouze ty, které vyhovují dané podmínce nulového součtu.

Kód je následující:

  • def znamenka(cisla, index = 0):
        if index == len(cisla):
            if sum(cisla) == 0:
                print(*cisla)
        else:
            znamenka(cisla, index + 1)
            cisla[index] *= -1
            znamenka(cisla, index + 1)
  • static void znamenka(int[] cisla, int index = 0)
    {
        if (index == cisla.Length)
        {
            if (cisla.Sum() == 0)
                Console.WriteLine(String.Join(" ", cisla));
        }
        else
        {
            znamenka(cisla, index + 1);
            cisla[index] *= -1;
            znamenka(cisla, index + 1);
        }
    }
  • public static function znamenka(array $cisla, int $index = 0): void
    {
        if ($index == count($cisla))
        {
            if (array_sum($cisla) == 0)
                echo(implode(" ", $cisla) . "<br>");
        }
        else
        {
            znamenka($cisla, $index + 1);
            $cisla[$index] *= -1;
            znamenka($cisla, $index + 1);
        }
    }
  • public static void znamenka(int[] cisla, int index)
    {
        if (index == cisla.length)
        {
            int sum = 0;
            for (int i = 0; i < cisla.length; i++)
                sum += cisla[i];
            if (sum == 0)
            {
                for (int i = 0; i < cisla.length; i++)
                    System.out.print(cisla[i] + " ");
                System.out.println();
            }
        }
        else
        {
            znamenka(cisla, index + 1);
            cisla[index] *= -1;
            znamenka(cisla, index + 1);
        }
    }

Metoda u znamének + a - by šly zefektivnit a trochu zkomplikovat 😁 pomocí tzv. prořezávání, ale o tom až někdy jindy.

V následujícím článku, Stromová rekurze – Obecné stromy, si předvedeme tvorbu metod, ve kterých schéma rekurzivních volání tvoří obecné stromy.


 

Předchozí článek
Úvod do rekurze
Všechny články v sekci
Rekurzivní algoritmy
Přeskočit článek
(nedoporučujeme)
Stromová rekurze – Obecné stromy
Článek pro vás napsal Jan Hnilica
Avatar
Uživatelské hodnocení:
17 hlasů
Autor se věnuje hlavně programování v C a v Pythonu
Aktivity