Haskell - Programació dinàmica P27104

Aquest exercici explora l’ús de vectors per resoldre problemes de programació dinàmica.

1. Oh, no... Un altre cop! Feu una funció fib :: Int -> Integer que, donat un n≥0, retorni l’n-èsim nombre de Fibonaci.
2. Feu una funció binomial :: Int -> Int -> Integer que, donat un enter n≥0 i un enter 0≤ k≤ n, retorni el coeficient binomial (

   n

   k

   ), és a dir, el nombre de formes en què es poden escollir k objectes d’entre un conjunt de n sense tenir en compte l’ordre.
3. Feu una funció bst :: Int -> Integer que, donat un n≥0, retorni el nombre d’arbres binaris de cerca amb nodes 1,…,n.

   Per exemple, bst 3 és 5, perquè hi ha 5 arbres binaris de cerca amb nodes 1,2,3:

               1          1         2         3        3
                \          \       / \       /        /
                 2          3     1   3     1        2
                  \        /                 \      /
                   3      2                   2    1
   

4. Feu una funció coins :: [Int] -> Int -> Int que, donada una llista de n valors de monedes v₁,…,v_n i donat un valor s, trobi el mínim nombre de monedes que sumen s. Cada moneda es pot fer servir diversos (o cap) cops, s≥0 i v_i>0 per a tot i.
5. Donades dues matrius amb dimensions n₁ × n₂ i n₂ × n₃, el cost de l’algorisme habitual per multiplicar-les és Θ(n₁ n₂ n₃). Per senzillesa, considerem que el cost és exactament n₁ n₂ n₃.

   Suposem que hem de calcular M₁ × M₂ × … × M_m, on cadascuna de les M_i és una matriu amb dimensions n_i × n_i+1. Com que el producte de matrius és associatiu, es pot triar en quin ordre es fan les multiplicacions. Per exemple, per calcular M₁ × M₂ × M₃ × M₄, es podria fer (M₁ × M₂) × (M₃ × M₄), amb cost n₁ n₂ n₃ + n₃ n₄ n₅ + n₁ n₃ n₅, o bé M₁ × ((M₂ × M₃) × M₄), amb cost n₂ n₃ n₄ + n₂ n₄ n₅ + n₁ n₂ n₅, o bé tres altres ordres possibles.

   Feu una funció mult :: [Int] -> Int que trobi el cost mínim de calcular M₁ × M₂ × … × M_m, donades les dimensions n₁, n₂, … , n_m, n_m+1.

Puntuació

Per a cada apartat, hi ha dos tipus de jocs de proves segons la talla de la seva entrada: els petits i els grans. Els petits es poden resoldre recursivament i dónen 5 punts cadascún. Els grans requereixen programació dinàmica i dónen 15 punts cadascún.