Rekurzia, rekurzívne algoritmy

1. Popíšte, čo je to rekurzia. Aké typy rekurzie poznáte? Aké zásady treba dodržiavať pri programovaní rekurzívnych algoritmov? Výhody a nevýhody rekurzie.
2. Napíšte program na výpočet N! (faktoriál). Použite rekurzívny aj nerekurzívny algoritmus.
3. Napíšte program na výpočet FIB(n) (n-tý člen Fibbnacciho postupnosti). Použite rekurzívny aj nerekurzívny algoritmus. Je rekurzia v tomto prípade vhodná? Prečo?

Rekurzívne krivky.

4. Vytvorte program, ktorý kreslí nasledovné rekurzívne krivky. Môžete použiť UNIT kori.pas. V ukážkach sú prvé tri úrovne (okrem C-krivky, Dračej krivky, krivky Kochovej a Sierpinského krivky).

Triomino

Pokúste sa vygenerovať "troj strom" s istou úrovňou chýb. Napr.: nemusia existovať všetky ramená stromu a uhly ktoré zvierajú jednotlivé ramená nemusia byť rovnaké.

Tu treba použiť nepriamu rekurziu. Nemusíte nutne použiť unit kori.

Kochovej krivka

. . . C-krivka

. . .  Dračia krivka

. . . Sierpinského krivka

Backtracking

5. Popíšte princíp stratégie prehľadávania s návratom - backtracking.
6. Majme šachovnicu s rozmermi n´n, t.j. celkový počet políčok je n². Kôň, ktorý má pohyby predpísané pravidlami šachu, sa na šachovnici nachádza v pozícii určenej začiatočnými súradnicami x₀, y₀. Nájdite pokrytie celej šachovnice, ak existuje čo len jediné, t.j. vypočítajte dráhu  n²-1 takých pohybov, pomocou ktorých sa kôň dostane do každého políčka šachovnice iba jediný raz.
   zdroj: Wirth, N.: Algoritmy a štruktúry údajov, Alfa 1989
7. Napíšte program, ktorý na šachovnici rozmiestni čo najviac šachových dám tak, aby sa navzájom neohrozovali. Úlohu riešte aj pre klasickú šachovnicu 8´8 aj pre všeobecnú šachovnicu n´m.
8. Napíšte program, ktorý nájde všetky cesty (ktoré existujú tie vypíše) cez bludisko. Bludisko je zadané v textovom súbore, ktorý má nasledovný formát:
   n m odr ods dor dos {n - počet riadkov, m - počet stĺpcov, odr a ods - vstup do bludiska, dor a dos - výstup z bludiska}
   bludisko zapísané ako matica znakov: "X"-stena, "."-voľná cesta.
   Napríklad:
   10 10 2 2 9 9
XXXXXXXXXX
X.......XX
X.XX.XX.XX
X.XX.XX...
X.XX.XXXXX
X.XX.XXXXX
X.XX.XXXXX
X......XXX
X.XXXX...X
XXXXXX.XXX
Testovací súbor s bludiskom si môžete stiahnuť tu: bludisko.dat.
9. Problém súčtu podmnožiny (Sum-of-subset problem).
   Daná je množina čísel S. Je možné nájsť podmnožinu množiny S tak, aby súčet čísel tejto podmnožiny bol n?
10. Problém obchodného cestujúceho.
    Obchodný cestujúci musí navštíviť n miest na svojom zozname a vrátiť sa do mesta, z ktorého začal. Nájdite všetky cesty (resp. tú najkratšiu) obchodného cestujúceho. Vstup do programu (pre počet miest 6) vyzerá napr. takto:
    pozn. hodnota 0 znamená že cesta medzi mestami neexistuje (ak sú rôzne), alebo nemá zmysel (ak je to jedno a to isté mesto)
    6
    0 0 2 4 5 1
    0 0 8 2 3 6 
    2 8 0 2 0 0 
    4 2 2 0 5 0
    5 3 0 5 0 3
    1 6 0 0 3 0

Rekurzívne triedenie

11.  Je dané pole prvkov a[1] .. [n]. Vytvorte algoritmus, ktorý dané pole utriedi. Použite triedenie rozdeľovaním (Quicksort).