Algoritmi in podatkovne strukture (2021-22)

1. Za ogrevanje sprogramiraj funkcijo, ki vrne binomski koeficient (n, k). Rekurzivno.

2. Za še malo ogrevanja sprogramiraj funkcijo, ki sestavi Pascalov trikotnik. Računaj navzdol - vsako vrstico računa iz prejšnje. Vrne naj takšen seznam:

    [[1],
     [1, 1],
     [1, 2, 1],
     [1, 3, 3, 1],
     [1, 4, 6, 4, 1],
     [1, 5, 10, 10, 5, 1]]

3. Sprogramiraj rekurzivno čebelo. Za razliko od tega, kar smo počeli na predavanjih, vrni tudi pot in ne le rezultata.

    vrt = [[9],
           [6, 5],
           [4, 8, 4],
           [7, 4, 3, 3],
           [8, 4, 1, 9, 7],
           [2, 2, 5, 7, 1, 8]
           ]

4. Sprogramiraj čebelo navzdol, s postopnim računanjem vrstic. Vrni tudi pot in ne le rezultata.

5. Oglej si problem verižnega množenja matrik (matrix chain multiplication): sprogramiraj funkcijo, ki prejme dimenzije matrik in pove, v kakšnem vrstnem redu jih je potrebno množiti. Dimenzije matrik so podane s seznamom, kot je, na primer [4, 10, 3, 12, 20, 7]. To bi pomenilo, da množimo matrike dimenzij (4, 10), (10, 3), (3, 12), (12, 20), (20, 7).