Úloha 1.u2: Zahradnická (3 b)

Zadáno v čísle 22.1.

Řešeno v čísle 22.3.

Zadání

Lišák Riki se pustil do zahradničení. Má záhonek a pěstuje tři druhy zeleniny: artyčoky, brambory a celer. Na jejich pěstování se ale vztahují určitá pravidla:

V záhonku nesmí být dva artyčoky hned vedle sebe.

Brambor nemůže růst mezi dvěma stejnými rostlinami.

Celer nevyroste, pokud má za jednoho souseda artyčok a za druhého brambor.

Určete, kolika různými způsoby může Riki naplnit svůj záhonek, pokud se mu do něj vejde právě jedna řada s dvaceti rostlinami.

Řešení

Jak několik z vás předvedlo, 3^20 je ještě pořád dost malé číslo na to, aby bylo možné tuto úlohu za pomoci počítače řešit hrubou silou. Generoval tedy všechna možná vysazení rostlinek a následně kontroloval, zda neobsahují zakázané kombinace. Existuje ale i mnohem efektivnější metoda, která by například fungovala (v rozumném čase) i pro záhonek délky 50, a byla o něco málo lépe bodově ohodnocena.
Pro zkrácení zápisu zaveďme, že písmeno "A" představuje artyčok, "B" brambor a "C" celer.
Postřehneme, že to, jakou rostlinku můžeme zasadit jako příští, závisí pouze na předchozích dvou rostlinkách. Přesněji řečeno:
    Žádný záhonek nemůže končit AA
    Pokud záhonek končí AB, můžeme jako další vysadit B nebo C
    Pokud záhonek končí AC, můžeme jako další vysadit A nebo C
    Pokud záhonek končí BA, můžeme jako další vysadit B nebo C
    Pokud záhonek končí BB, můžeme jako další vysadit A nebo C
    Pokud záhonek končí BC, můžeme jako další vysadit B nebo C
    Pokud záhonek končí CA, můžeme jako další vysadit B nebo C
    Pokud záhonek končí CB, můžeme jako další vysadit A nebo B
    Pokud záhonek končí CC, můžeme jako další vysadit A, B nebo C
Tohle už by představovalo jisté zlepšení, algoritmus využívající jen toho pozorování by prošel přibližně 2^20 místo 3^20 možností a nepotřeboval trávit tolik času kontrolováním výsledku, čímž by výrazně předčil algoritmus používající hrubou sílu. (Zájemci si můžou zkusit obojí naprogramovat a srovnat čas běhu algoritmu)

Dalšího zrychlení ale dosáhneme tím, když vypozorujeme, že VŠECHNY záhonku končící danou dvojicí se nadále budou chovat stejně.
Označme si počet záhonků délky n (kde n je nějaké přirozené číslo >= 2) končících na XY (kde X,Y \in {A,B,C}} jako XY_n.
Tedy počet záhonků délky 2 končících na AB je AB_2 = 1.
Dále si musíme všimnout, že počty (jednotlivými dvojicemi končících) záhonků o délce n+1 umíme spočítat z počtů pro délku n.
Ku příkladu:
    AB_{n+1} = BA_n + CA_n
Pro ostatní konce tyto (takzvané rekurentní) vzorce si již jistě umíte odvodit sami.
Je důležité si všimnout, že pro n=2 už správné výsledky máme: AA_2 = 0 a pro všechna ostatní XY se XY_2 = 1
Pokud bychom využili jen tohoto a postupně se pokoušeli zpočítat XY_20 pro každé XY, tak se žádného zlepšení oproti předchozímu algoritmu nedočkáme.
Chce to ještě si všimnout toho, že takhle bychom pořád dokola počítali, kolik nám vyjdou XY_n pro n < 20.
Využijeme tedy takzvané dynamické programování - budeme líní a když už jednou XY_n spočítáme, tak si ten výsledek zapamatujeme a už nikdy to nebudeme počítat znovu.
Nebo - a tohle bylo nejjednodušší a nejlépe hodnocené řešení - si uvědomíme, že známe jednotlivá XY_2, a tak z nich spočítáme všechny XY_3, z těch pak spočítáme všechny XY_4 a tak dále až po spočítání všech XY_20, které pak sečteme.
Jistě se mnou budete souhlasit, že toto řešení je na papíře poněkud pracné, ale proveditelné. S pomocí počítače (není potřeba programovat, stačí Calc nebo Excel) je to ale již zcela triviální výpočet.