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:

Č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í:

Vstupní řetězec retezec.
Řetězec vysledek, zpočátku prázdný, do kterého metoda ukládá vznikající podřetězec.
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.

Článek pro vás napsal Jan Hnilica

Uživatelské hodnocení:

16 hlasů

Autor se věnuje hlavně programování v C a v Pythonu

Aktivity

Lekce 2 - Stromová rekurze - Generování všech možností

Binární čísla

Strom volání

Podřetězce

Znaménka + a -

Znaménka `+` a `-`