Menu Close

Sucesión duplicadora

José A. Alonso,

Para cada entero positivo n, existe una única sucesión que empieza en 1, termina en n y en la que cada uno de sus elementos es el doble de su anterior o el doble más uno. Dicha sucesión se llama la sucesión duplicadora de n. Por ejemplo, la sucesión duplicadora de 13 es [1, 3, 6, 13], ya que

    3 = 2*1 +1
    6 = 2*3
   13 = 2*6 +1

Definir la función

   duplicadora :: Integer -> [Integer]

tal que (duplicadora n) es la sucesión duplicadora de n. Por ejemplo,

   duplicadora 13                   ==  [1,3,6,13]
   duplicadora 17                   ==  [1,2,4,8,17]
   length (duplicadora (10^40000))  ==  132878

Soluciones

-- 1ª solución
duplicadora :: Integer -> [Integer]
duplicadora x =
    reverse (takeWhile (>=1) (iterate (`div` 2) x))
 
-- 2ª definición
duplicadora2 :: Integer -> [Integer]
duplicadora2  =
    reverse . takeWhile (>=1) . iterate (`div` 2)
Medio
, , , ,

8 soluciones de “Sucesión duplicadora”

  1. Responder
    carruirui3 
    duplicadora :: Integer -> [Integer]
duplicadora = reverse . divisora
 
divisora :: Integer -> [Integer]
divisora 1 = [1]
divisora n | even n = n : divisora (n `div` 2)
           | otherwise = n : divisora ((n-1) `div` 2)
  2. Responder
    Paola Cabrera Perza 
    duplicadora :: Integer -> [Integer]
duplicadora n = reverse (sucesionDuplicadora n)
 
sucesionDuplicadora :: Integral a => a -> [a]
sucesionDuplicadora 1 = [1]
sucesionDuplicadora n | odd n  = [n] ++ sucesionDuplicadora ((n-1) `div` 2)
                      | even n = [n] ++ sucesionDuplicadora (n `div` 2)
  3. Responder
    erisan 
    duplicadora :: Integer -> [Integer]
duplicadora 1 = [1]
duplicadora n | even n = duplicadora (n `div` 2) ++ [n]
              | otherwise = duplicadora ((n-1) `div` 2) ++ [n]
  4. Responder
    alvalvdom1

    Los cocientes de la división entera de un número impar entre dos, y de su anterior (por tanto, par) entre dos, coinciden, por lo que no es necesario distinguir entre los casos par e impar.

    duplicadora :: Integer -> [Integer]
duplicadora 1 = [1]
duplicadora n = duplicadora (div n 2) ++ [n]
    • Responder
      alvalvdom1

      Una solución más eficiente sería:

      duplicadora :: Integer -> [Integer]
duplicadora = reverse . aux
            where aux 1 = [1]
                  aux n = n:aux (div n 2)
  5. Responder
    fracruzam 
    duplicadora :: Integer -> [Integer]
duplicadora = reverse . takeWhile (/= 0) . iterate (`div` 2)
  6. Responder
    javoliher 
    duplicadora :: Integer -> [Integer]
duplicadora n = aux n []
    where aux 1 xs = 1:xs
          aux n xs = aux (n `div` 2) (n:xs)
  7. Responder
    fracruzam

    Dejo una solución por búsqueda en espacios de estado, aunque es bastante más lentita

    duplicadoraEE :: Integer -> [Integer]
duplicadoraEE m = busca [[1]]
  where busca :: [[Integer]] -> [Integer]
        busca (xs@(x:_):xss) 
            | x == m = reverse xs
            | x > m  = busca xss 
            | otherwise = busca ((xx:xs):(xx + 1:xs):xss) 
          where xx = 2 * x

Escribe tu solución

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