2. diel - Stromová rekurzia - Generovanie všetkých možností

V predchádzajúcom článku, Úvod do rekurzie , sme sa zoznámili s pojmom rekurzie a precvičili si tvorbu jednoduchých rekurzívnych funkcií.

V dnešnom tutoriále o rekurzívnych algoritmoch sa naučíme, ako využiť rekurziu na vygenerovanie všetkých možností pri riešení nejakého problému.

Úlohy tohto typu sa obvykle na prvý pohľad tvária zložito, ale práve rekurzia tu predstavuje stručný a elegantný nástroj, ktorým ich možno rozlúsknuť na pár riadkoch kódu. Riešenie týchto typov úloh si ukážeme na troch praktických príkladoch pre

binárne čísla,
podreťazce,
znamienka + a -.

Binárne čísla

Napíšme si funkciu, ktorá ako parameter preberá celé číslo k a na monitor vypíše všetky k -miestne binárne čísla. Pretože ide o binárne čísla, môže byť na každom z k miest buď 0 alebo 1. Budeme pracovať s k -prvkovým poľom, ktoré bude parametrom funkcie, a do ktorého budeme vznikajúce čísla zapisovať. Ako druhý parameter dostane funkcia index, na ktorý do poľa postupne zapíše 0 a 1 a po každom zápise zavolá svojho rekurzívneho potomka, aby rovnakým spôsobom spracoval ďalší index. Ak je pole plné, funkcia ho iba 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($pole, $index = 0)
{
    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 volania

Je dôležité si uvedomiť, v akom poradí sú jednotlivé funkcie volané, ako postupne dochádza k zaplňovaniu a neskôr aj k prepisovaniu hodnôt na jednotlivých pozíciách. Pre dvojmiestne binárne čísla dostaneme túto schému:

Červené čísla na obrázku ukazujú poradie, v ktorom sú funkcie volané. Vidíme, že schéma tvorí strom.

Začíname prázdnym poľom, ktoré predstavuje koreň stromu, a do ktorého zapisujeme na prvú pozíciu. Vždy najskôr zapíšeme nulu a zavoláme tú istú funkciu, aby na spodnom poschodí stromu spracovala ďalší prvok poľa (index + 1). Tým vzniká ľavý podstrom. Potom na danú pozíciu zapíšeme jedničku a necháme rovnakým spôsobom rekurzívne rozvinúť pravý podstrom. Pokiaľ funkcia dostane zaplnené pole, iba ho vypíše na monitor a rekurzívny rozvoj končí.

Podreťazca

Teraz si napíšme funkciu, ktorá preberá reťazec a vygeneruje všetkých podreťazcov, ktoré môžu vzniknúť vyškrtaním jednotlivých znakov.

Najskôr sa nad úlohou krátko zamyslíme. Aby sme dostali všetkých podreťazcov, budeme postupne ošetrovať jeden znak po druhom. Začneme pri prvom znaku v koreni pomyselného stromu a rozdelíme generovanie na dve vetvy. V ľavej vetve znak do podreťazcov nezaradíme, v pravej vetve naopak áno. Obe vetvy necháme ďalej rozvíjať na spodných poschodiach stromu podľa ďalších znakov úplne rovnakým postupom – rekurzívnym volaním.

Jedna z možných implementácií algoritmu vyzerá 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($retezec, $vysledek = "", $index = 0)
{
    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);
    }
}

Funkcia preberá tri parametre v tomto poradí:

Vstupný reťazec retezec.
Reťazec výsledek, spočiatku prázdny, do ktorého funkcie ukladá vznikajúci podreťazec.
Index znaku index + 1, ktorý ošetruje (buď ho zahrnie alebo nezahrnie do vznikajúceho podreťazca).

Pozrime sa opäť na strom volania, ak vstupom bude napr. reťazec ABC:

Strom volaní pre podreťazca - Rekurzívne algoritmy

Na obrázku je každé volanie vyznačené dvojicou údajov:

poradie volania (červeno) a stav reťazca výsledek (zelene),
hodnota indexu index potom zodpovedá poschodiu stromu.

Znamienka + a -

Ako posledný príklad si napíšme funkciu, ktorá preberá pole celých čísel a vypíše všetky spôsoby, ako pred jednotlivé čísla umiestniť znamienka + alebo - tak, aby súčet všetkých zadaných čísel bol 0. Princíp úlohy je rovnaký ako pri predchádzajúcich úlohách. Budeme generovať všetky možnosti, teraz ale vypíšeme iba tie, ktoré vyhovujú danej podmienke nulového súčtu.

Kód je nasledujúci:

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($cisla, $index = 0)
{
    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);
    }
}

Funkcie u znamienok + a - by išli zefektívniť a trochu skomplikovať 😁 pomocou tzv. prerezávania, ale o tom až niekedy inokedy.

V nasledujúcom článku, Stromová rekurzia – Všeobecné stromy , si predvedieme tvorbu metód, v ktorých schému rekurzívnych volaní tvoria všeobecné stromy.

Článok pre vás napísal Jan Hnilica

Užívateľské hodnotenie:

Ešte nikto nehodnotil, buď prvý!

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

Aktivity