1) generování n-té permutace v lexikografickém pořadí
Vstupem byla čísla N a K a výstupem měla být K-tá permutace N čísel v lexikografickém pořadí. Př:
perm(4,3,P).
P = [1,3,4,2]
Plný počet bodů byl jen za řešení které postupně negeneruje všechny permutace (za to byly maximálně 4 body, ale když jste měli to řešení, co chtěli, tak to podle mě docela ocenili u ústní - alespoň u mě)
2) maximální párování obsahující hranu
Vstupem byl graf zadaný seznamem sousedů a jedna jeho hrana. Výstupem mělo být nějaké maximální párování, obsahující danou hranu.
Haskell
3) Generování pascalova trojúhelníku
Př: take 5 pascal
[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]
4) Postavení BVS
Byla zadaná datová struktura:
data Bt a = Void | Node (Bt a) a (Bt a)
Vstupem byl seznam vrcholů, které vznikly procházením BVS v preorder (podle mě se to ale je inorder) průchodu. Výstupem měl být BVS patřící k tomuto seznamu vrcholů (BVS je seznamem určen jednoznačně).
Seznamu [5,2,4,9] odpovídal strom
Kód: Vybrat vše
5
/ \
2 9
\
4Node (Node Void 2 (Node Void 4 Void)) 5 (Node Void 9 Void)
Vzhledem k tomu, že to byl poslední termín, tak řikali, že by mohlo z první části stačit na postup 12 bodů místo 13ti.
Velký příklad
Byly zadány rozměry n-dimenzionální mřížky a několik uzlů ležících v ní. Dva uzly byly sousední, pokud se absolutní rozdíl jedné složky vektorů lišil o 1.
tzn (1,4,7,3,5) bylo sousední s (1,4,6,3,5).
Měli jsme vybrat množinu hran, aby mezi každými dvěma uzly existovala cesta a zároveň, aby počet vybraných hran byl nejmenší možný. Mohli jsme najít buď přesné řešení, nebo použít nějakou heuristiku. Případně jsme ještě mohli uvažovat cyklickou mřížku.