Menu Close

Mínimo número de saltos para alcanzar el final

Dada una lista de enteros positivos, se interpreta cada elemento el máximo número de pasos que se puede avanzar desde dicho elemento. Por ejemplo, para la lista [1,3,5,8,9,2,6,7,6,8,9], desde sólo se puede avanzar un paso (hasta el 3), desde el 3 se puede avanzar 3 pasos (hasta el 5, 8 ó 9), y así sucesivamente. En dicha lista, el mínimo número de saltos que hay que dar para alcanzar el final es 3 (el recorrido es 1, 3, 8, 9).

Definir la función

   minimoSaltos :: [Int] -> Int

tal que (minimoSaltosxs) es el mínimo número de saltos que hay que dar en la lista xs para alcanzar el final. Por ejemplo,

   minimoSaltos [1,3,5,8,9,2,6,7,6,8,9]  ==  3
   minimoSaltos (replicate 10 1)         ==  9
   minimoSaltos [1..25]                  ==  5

Soluciones

import Data.List (tails)
 
minimoSaltos :: [Int] -> Int
minimoSaltos (x:y:xs) =
  1 + minimum [minimoSaltos ys | ys <- take x (tails (y:xs))]
minimoSaltos _ = 0

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

3 soluciones de “Mínimo número de saltos para alcanzar el final

  1. Rubén Muñoz Mkrtchian
    minimoSaltos :: [Int] -> Int
    minimoSaltos [] = 0
    minimoSaltos (x:xs) = aux1 x xs
     
    -- aux1 x xs calcula el número mínimo de saltos que se deben dar en una lista
    -- no vacía de términos. Por ejemplo,
    --   λ> aux1 1 [3,5,8,9,2,6,7,6,8,9]
    --   3
     
    aux1 :: Int -> [Int] -> Int
    aux1 n [] = 0
    aux1 n xs
      | n > length xs = 1
      | otherwise     = 1 + aux1 (elementoOpt n xs) (drop (posOpt n xs) xs)
     
    -- elementoOpt n xs es el elemento óptimo con el que continuar la recursión en
    -- aux1 n xs, es decir, el elemento a partir del cual se puede dar el mayor
    -- número de pasos. Para ello, nos ayudamos de otra función auxiliar a la que
    -- llamaremos aux2 n xs. Por ejemplo,
    --   λ> elementoOpt 3 [5,8,9,2,6,7,6,8,9]
    --   9
     
    elementoOpt :: Int -> [Int] -> Int
    elementoOpt n xs = aux2 (length xs - 1) (take n xs)
     
    aux2 :: Int -> [Int] -> Int
    aux2 _ [x] = x
    aux2 n (x1:x2:xs)
      | x1 - n <= x2 - n + 1 = aux2 (n-1) (x2:xs)
      | otherwise            = aux2 (n-1) (x1:xs)
     
    -- posOpt n xs representa la posición del elemento óptimo que hemos hallado
    -- anteriormente. Por ejemplo,
    --   λ> posOpt 3 [5,8,9,2,6,7,6,8,9]
    --   3
     
    posOpt :: Int -> [Int] -> Int
    posOpt n xs = last [i | (x,i) <- zip (take n xs) [1..], x == elementoOpt n xs]
  2. Mercedes Vega Gallo
    minimoSaltos :: [Int] -> Int
    minimoSaltos [] = 0
    minimoSaltos [x] = 0
    minimoSaltos (x:xs) = 1 + minimoSaltos (drop x (x:xs))

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.