Haskell - Programació dinàmica P27104


Statement
 

pdf   zip

thehtml

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≤ kn, 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 v1,…,vn 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 vi>0 per a tot i.
  5. Donades dues matrius amb dimensions n1 × n2 i n2 × n3, el cost de l’algorisme habitual per multiplicar-les és Θ(n1 n2 n3). Per senzillesa, considerem que el cost és exactament n1 n2 n3.

    Suposem que hem de calcular M1 × M2 × … × Mm, on cadascuna de les Mi és una matriu amb dimensions ni × ni+1. Com que el producte de matrius és associatiu, es pot triar en quin ordre es fan les multiplicacions. Per exemple, per calcular M1 × M2 × M3 × M4, es podria fer (M1 × M2) × (M3 × M4), amb cost n1 n2 n3 + n3 n4 n5 + n1 n3 n5, o bé M1 × ((M2 × M3) × M4), amb cost n2 n3 n4 + n2 n4 n5 + n1 n2 n5, o bé tres altres ordres possibles.

    Feu una funció mult :: [Int] -> Int que trobi el cost mínim de calcular M1 × M2 × … × Mm, donades les dimensions n1, n2, … , nm, nm+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.

Public test cases
  • Input

    map fib [0..6]
    map (binomial 6) [0..6]
    map bst [0..6]
    coins [1,3,5] 11
    coins [4,6] 11
    mult [10,20,30,40]
    mult [9000,4000,3500,8000,2000,7500,6000,1000,8500,5500,7000]
    

    Output

    [0,1,1,2,3,5,8]
    [1,6,15,20,15,6,1]
    [1,1,2,5,14,42,132]
    Just 3
    Nothing
    18000
    302250000000
    
  • Information
    Author
    Jordi Petit i Salvador Roura
    Language
    Catalan
    Official solutions
    Haskell
    User solutions
    Haskell