Menu Close

Generadores de números de Gabonacci

José A. Alonso,

Los números de Gabonacci generados por (a,b) son los elementos de la sucesión de Gabonacci definida por

   G(0) = a
   G(1) = b
   G(n) = G(n-2) + G(n-1), si n > 1

Por ejemplo, la sucesión de Gabonacci generada por (2,5) es 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, …

Un número pertenece a distintas sucesiones de Gabonacci. Por ejemplo, el 9 pertenece a las sucesiones de Gabonacci generados por (3,3), (1,4) y (4,5).

El menor generador de Gabonacci de un número x es el par (a,b), con 1 ≤ a ≤ b, tal que (a,b) es un generador de Gabonacci de x y no existe ningún generador de Gabonacci de x (a’,b’) tal que b’ < b ó b’ = b y a’ < a. Por ejemplo, el menor generador de Gabonacci de 9 es (3,3).

Definir la función

   menorGenerador :: Integer -> (Integer,Integer)

tal que (menorGenerador x) es el menor generador de Gabonacci de x. Por ejemplo,

   menorGenerador 9          ==  (3,3)
   menorGenerador 7          ==  (1,3)
   menorGenerador 5          ==  (1,1)
   menorGenerador 27         ==  (3,7)
   menorGenerador 57         ==  (4,9)
   menorGenerador 218        ==  (10,21)
   menorGenerador 1121       ==  (20,41)
   menorGenerador 89         ==  (1,1)
   menorGenerador 123        ==  (1,3)
   menorGenerador 1000       ==  (2,10)
   menorGenerador 842831057  ==  (2,7)
   menorGenerador 1573655    ==  (985,1971)

Soluciones

menorGenerador :: Integer -> (Integer,Integer)
menorGenerador = head . generadores
 
generadores :: Integer -> [(Integer,Integer)]
generadores x = [(a,b) | b <- [1..x]
                       , a <- [1..b]
                       , pertenece x (gabonacci a b)]
 
gabonacci :: Integer -> Integer -> [Integer]
gabonacci a b = aux
  where aux = a : scanl (+) b aux
 
pertenece :: Integer -> [Integer] -> Bool
pertenece x ys =
  x == head (dropWhile (<x) ys)
Avanzado
, , , , ,

10 soluciones de “Generadores de números de Gabonacci”

  1. Responder
    enrnarbej 
    gabonacci :: Integer -> Integer -> [Integer]
gabonacci a b = fs
  where (xs,ys,fs) = (zipWith (+) ys fs, b:xs, a:ys)
 
 
menorGenerador :: Integer -> (Integer, Integer)
menorGenerador n = head [(a,b) | b <- [1..n]
                               , a <- [1..b]
                               , n == (head . dropWhile (<n) . gabonacci a) b]
  2. Responder
    albcercid 
    -- Primera definición: consiste en ver el mínimo valor que, tras aplicar
-- f, obtenemos de los pares (a,b) con a + b = x 
menorGenerador x =  v (minimum (map f (generadores1 x)))
  where v (a,b) = (b,a)
        f (a,b) | b < a-b || a == b = (a,b)
                | otherwise = f (b,a-b)
        generadores1 x = [(x-a,a) | a <- [div x 3..div x 2]]
 
-- Segunda definición: probar si un cierto generador (a,b) nos lleva a x.
menorGenerador2 x = aux (1,1) (1,1) x
  where aux (a,b) (c,d) x | c + d == x = (a,b)
                          | c + d < x = aux (a,b) (d,c+d) x
                          | a < b = aux (a+1,b) (a+1,b) x
                          | otherwise = aux (1,b+1) (1,b+1) x
 
 
-- Tercera definición: se obtiene demostrando que el menor generador es
-- el par (a,b) con a+b = x y (número de oro)*a = b
-- 
-- Este par (a,b) admite mayor número de recursiones de f, y a mayor
-- número de recursiones, menor es el generador. 
menorGenerador3 x = f (a,b)
  where b = round (fromIntegral (x)/1.61803398875)
        a = x-b
        f (a,b) | a < b-a || a == b = (a,b)
                | otherwise = f (b-a,a)
    • Responder
      albcercid 
      -- Elimina los errores de menorGenerador3
menorGenerador4 :: Integer -> (Integer,Integer)
menorGenerador4 x =  (
  v.minimum.map v) ([fst (f (x-z,z) 1) | z <- [b..b+t]] ++
                    [fst (f (x-z,z) 1) | z <- [b-q..b]])
  where v (a,b) = (b,a)
        b = round (fromIntegral (x)/1.61803398875)
        a = x-b
        f (a,b) n | a < b-a || a == b = ((a,b),n)
                  | otherwise = f (b-a,a) (n+1)
        t = head [ n | n <- [1..], snd (f (a-n,b+n) 1) < snd p]
        q = head [ n | n <- [1..], snd (f (a+n,b-n) 1) < snd p]
        p = f (a,b) 1
  3. Responder
    monlagare 
     
-- menorGenerador :: Integer -> (Integer,Integer)
-- gabonacci :: Integer -> Integer -> [Integer]
 
gabonacci x y = x : y : zipWith (+) xs ys
    where ys = tail (gabonacci x y)
          xs = gabonacci x y 
 
menorGenerador x = head [(a,b) | b <- [1..x], a <- [1..b],
                                 x == head (dropWhile (< x) (gabonacci a b))]
  4. Responder
    glovizcas

    Sólo da resultado para los tres primeros ejemplos.

    sucGabonacci (a,b) = [ g(x) | x <- [0..]]
                    where g(0) = a
                          g(1) = b
                          g(x) = g(x-1)+g(x-2)
 
menorGenerador :: Integer -> (Integer,Integer)
menorGenerador n = vuelta (minimum [ (b,a) | b <- [1..n],
                                             a <- [1..b],
                          n `elem` take (fromInteger n) ( sucGabonacci (a,b))])
 
vuelta (a,b) = (b,a)
  5. Responder
    antdursan 
    gabonacci :: (Integer,Integer) -> [Integer]
gabonacci (a,b) = a:b:(a+b):(drop 2 (gabonacci (b,(a+b)))) 
 
menorGenerador :: Integer -> (Integer, Integer)
menorGenerador n = head [(a,b) | b <- [1..n]
                               , a <- [1..b]
                               , n == head (dropWhile (<n) (gabonacci (a,b)))]
  6. Responder
    paumacpar 
    gib :: Integer -> Integer -> [Integer]
gib a b= gs
  where (xs,ys,gs) = (zipWith (+) ys gs, b:xs, a:ys)
 
menorGenerador :: Integer -> (Integer,Integer)
menorGenerador x = aux (sucPares) 
  where aux ((a,b):ys) | pertenece x (gib a b) = (a,b)
                       | otherwise = aux ys 
 
sucPares :: [(Integer,Integer)]
sucPares = zip (concatMap (n -> [1..n]) [1..])
             (concatMap (n -> replicate (fromInteger n+1) n) [1..]) 
 
pertenece :: Integer -> [Integer] -> Bool
pertenece x xs = head (dropWhile (<x) xs) == x
  7. Responder
    natalia 
    gabonacci :: (Int,Int)-> [Int]
gabonacci (a,b) = g(0) : g(1) : [g (n) | n <- [2..]]
  where g 0 = a
        g 1 = b
        g n = g(n-1) + g(n-2)
 
menorg :: Int -> (Int,Int)
menorg x =
  head [(a,b) | (a,b)<-ys x
              , null [(c,t) | (c,t) <-ys x
                            , t == b && c < a || t < b]]
 
ys x = [(a,b) | a <- [1..x]
              , b <- [1..x]
              , elem x (takeWhile (<=x) (gabonacci (a,b)))
              , a <= b]
  8. Responder
    eliguivil 
    menorGenerador :: Integer -> (Integer,Integer)
menorGenerador n = head $ dropWhile (notElem n . f) $ [(a,b) | b <- [1..], a <- [1..b]]
  where
    f (a,b) = xs 
      where xs = takeWhile (<=n) $ a:scanl (+) b xs
  9. Responder
    cescarde 
    menorGenerador :: Integer -> (Integer,Integer)
menorGenerador = head.pares
 
gabonacci :: (Integer,Integer) -> [Integer]
gabonacci (a,b) = a : b : gabonacci (a+b,a+2*b)
 
pares :: Integer -> [(Integer,Integer)]
pares x = [(a,b) | b <- [1..x], a <- [1..b], x `elem` (t $ g a b)]
        where t = take $ fromInteger x
              g a b = gabonacci (a,b)

Escribe tu solución

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