# Zkouška 13.9.

<{ForumPost(poster="Jookyn", timestamp=2010-09-14 13:10:48)}>
Prolog  
  
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

        5
      /  \
      2    9
      \
       4

Př: readBt \[5,2,4,9]   
Node (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.
<{/ForumPost}>