drop

Períodos de Fibonacci

PorJosé A. Alonso 9-febrero-201819-febrero-2018

Los primeros términos de la sucesión de Fibonacci son

   0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610

1	0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610

Al calcular sus restos módulo 3 se obtiene

   0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1

1	0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1

Se observa que es periódica y su período es

   0,1,1,2,0,2,2,1

1	0,1,1,2,0,2,2,1

Definir las funciones

   fibsMod                   :: Integer -> [Integer]
   periodoFibMod             :: Integer -> [Integer]
   longPeriodosFibMod        :: [Int]
   graficaLongPeriodosFibMod :: Int -> IO ()

fibsMod :: Integer -> [Integer]

periodoFibMod :: Integer -> [Integer]

longPeriodosFibMod :: [Int]

graficaLongPeriodosFibMod :: Int -> IO ()

tales que

(fibsMod n) es la lista de los términos de la sucesión de Fibonacci módulo n. Por ejemplo,

     λ> take 24 (fibsMod 3)
     [0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1]
     λ> take 24 (fibsMod 4)
     [0,1,1,2,3,1, 0,1,1,2,3,1, 0,1,1,2,3,1, 0,1,1,2,3,1]

λ> take 24 (fibsMod 3)

[0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1]

λ> take 24 (fibsMod 4)

[0,1,1,2,3,1, 0,1,1,2,3,1, 0,1,1,2,3,1, 0,1,1,2,3,1]

(periodoFibMod n) es la parte perioica de la sucesión de Fibonacci módulo n. Por ejemplo,

     periodoFibMod 3  ==  [0,1,1,2,0,2,2,1]
     periodoFibMod 4  ==  [0,1,1,2,3,1]
     periodoFibMod 7  ==  [0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1]

periodoFibMod 3 == [0,1,1,2,0,2,2,1]

periodoFibMod 4 == [0,1,1,2,3,1]

periodoFibMod 7 == [0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1]

longPeriodosFibMod es la sucesión de las longitudes de los períodos de las sucesiones de Fibonacci módulo n, para n > 0. Por ejemplo,

     λ> take 20 longPeriodosFibMod
     [1,3,8,6,20,24,16,12,24,60,10,24,28,48,40,24,36,24,18,60]

1 2	λ> take 20 longPeriodosFibMod [1,3,8,6,20,24,16,12,24,60,10,24,28,48,40,24,36,24,18,60]

(graficaLongPeriodosFibMod n) dibuja la gráfica de los n primeros términos de la sucesión longPeriodosFibMod. Por ejemplo, (graficaLongPeriodosFibMod n) dibuja

Soluciones

import Graphics.Gnuplot.Simple

fibsMod :: Integer -> [Integer]
fibsMod n = map (`mod` n) fibs

-- fibs es la sucesión de Fibonacci. Por ejemplo,
--    λ> take 20 fibs
--    [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181]
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

periodoFibMod :: Integer -> [Integer]
periodoFibMod 1 = [0]
periodoFibMod n = 0 : 1 : aux (drop 2 (fibsMod n))
  where aux (0:1:xs) = []
        aux (a:b:xs) = a : aux (b:xs)

longPeriodosFibMod :: [Int]
longPeriodosFibMod =
  [length (periodoFibMod n) | n <- [1..]]

-- 2ª definición de longPeriodosFibMod
-- ===================================

longPeriodosFibMod2 :: [Int]
longPeriodosFibMod2 = map longPeriodoFibMod [1..]

longPeriodoFibMod :: Integer -> Int
longPeriodoFibMod 1 = 1
longPeriodoFibMod n = aux 1 (tail (fibsMod n)) 0
  where aux 0 (1 : xs) k = k
        aux _ (x : xs) k = aux x xs (k + 1)

graficaLongPeriodosFibMod :: Int -> IO ()
graficaLongPeriodosFibMod n =
  plotList [ Key Nothing
           , Title ("graficaLongPeriodosFibMod " ++ show n)
           , PNG ("Periodos_de_Fibonacci " ++ show n ++ ".png")]
           (take n longPeriodosFibMod)

import Graphics.Gnuplot.Simple

fibsMod :: Integer -> [Integer]

fibsMod n = map (`mod` n) fibs

-- fibs es la sucesión de Fibonacci. Por ejemplo,

-- λ> take 20 fibs

-- [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181]

fibs :: [Integer]

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

periodoFibMod :: Integer -> [Integer]

periodoFibMod 1 = [0]

periodoFibMod n = 0 : 1 : aux (drop 2 (fibsMod n))

where aux (0:1:xs) = []

aux (a:b:xs) = a : aux (b:xs)

longPeriodosFibMod :: [Int]

longPeriodosFibMod =

[length (periodoFibMod n) | n <- [1..]]

-- 2ª definición de longPeriodosFibMod

-- ===================================

longPeriodosFibMod2 :: [Int]

longPeriodosFibMod2 = map longPeriodoFibMod [1..]

longPeriodoFibMod :: Integer -> Int

longPeriodoFibMod 1 = 1

longPeriodoFibMod n = aux 1 (tail (fibsMod n)) 0

where aux 0 (1 : xs) k = k

aux _ (x : xs) k = aux x xs (k + 1)

graficaLongPeriodosFibMod :: Int -> IO ()

graficaLongPeriodosFibMod n =

plotList [ Key Nothing

, Title ("graficaLongPeriodosFibMod " ++ show n)

, PNG ("Periodos_de_Fibonacci " ++ show n ++ ".png")]

(take n longPeriodosFibMod)

Búsqueda en los dígitos de pi

PorJosé A. Alonso 15-febrero-201726-marzo-2022

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

   3.1415926535897932384626433832 ... 83996346460422090106105779458151

1	3.1415926535897932384626433832 ... 83996346460422090106105779458151

Definir la función

   posicion :: String -> IO (Maybe Int)

1	posicion :: String -> IO (Maybe Int)

tal que (posicion n) es (Just k) si k es la posición de n en la sucesión formada por un millón dígitos decimales del número pi y Nothing si n no ocurre en dicha sucesión. Por ejemplo,

   λ> posicion "15"
   Just 3
   λ> posicion "2017"
   Just 8897
   λ> posicion "022017"
   Just 382052
   λ> posicion "14022017"
   Nothing
   λ> posicion "999999"
   Just 762
   λ> posicion "458151"
   Just 999995

λ> posicion "15"

Just 3

λ> posicion "2017"

Just 8897

λ> posicion "022017"

Just 382052

λ> posicion "14022017"

Nothing

λ> posicion "999999"

Just 762

λ> posicion "458151"

Just 999995

Nota. Se puede comprobar la función mediante The pi-search page o Pi search engine.

Soluciones

import Data.List (isPrefixOf)

posicion :: String -> IO (Maybe Int)
posicion ns = do
  ds <- readFile "Digitos_de_pi.txt"
  return (posicionEnLista (drop 2 ds) ns)

posicionEnLista :: Eq a => [a] -> [a] -> Maybe Int
posicionEnLista xs ys = aux xs 1
  where aux [] _ = Nothing
        aux (x:xs) n | ys `isPrefixOf` (x:xs) = Just n
                     | otherwise              = aux xs (n+1)

import Data.List (isPrefixOf)

posicion :: String -> IO (Maybe Int)

posicion ns = do

ds <- readFile "Digitos_de_pi.txt"

return (posicionEnLista (drop 2 ds) ns)

posicionEnLista :: Eq a => [a] -> [a] -> Maybe Int

posicionEnLista xs ys = aux xs 1

where aux [] _ = Nothing

aux (x:xs) n | ys `isPrefixOf` (x:xs) = Just n

| otherwise = aux xs (n+1)

Particiones de una lista

PorJosé A. Alonso 2-febrero-20179-febrero-2017

Definir la función

   particiones :: [a] -> [[[a]]]

1	particiones :: [a] -> [[[a]]]

tal que (particiones xs) es la lista de las particiones de xs en segmentos de elementos consecutivos. Por ejemplo,

   λ> particiones [1..3]
   [[[1],[2],[3]],[[1],[2,3]],[[1,2],[3]],[[1,2,3]]]
   λ> mapM_ print (particiones "abcd")
   ["a","b","c","d"]
   ["a","b","cd"]
   ["a","bc","d"]
   ["a","bcd"]
   ["ab","c","d"]
   ["ab","cd"]
   ["abc","d"]
   ["abcd"]
   λ> length (particiones [1..22])
   2097152

λ> particiones [1..3]

[[[1],[2],[3]],[[1],[2,3]],[[1,2],[3]],[[1,2,3]]]

λ> mapM_ print (particiones "abcd")

["a","b","c","d"]

["a","b","cd"]

["a","bc","d"]

["a","bcd"]

["ab","c","d"]

["ab","cd"]

["abc","d"]

["abcd"]

λ> length (particiones [1..22])

2097152

Comprobar con QuickCheck que la concatenación de cada uno de los elementos de (particiones xs) es igual a xs.

Nota: En la comprobación usar ejemplos pequeños como se indica a continuación

   quickCheckWith (stdArgs {maxSize=10}) prop_particiones

1	quickCheckWith (stdArgs {maxSize=10}) prop_particiones

Soluciones

import Test.QuickCheck

particiones :: [a] -> [[[a]]]
particiones [] = [[]]
particiones xs =
  [(take k xs) : yss | k <- [1..n], yss <- particiones (drop k xs)]
  where n = length xs

-- La propiedad es
prop_particiones :: [Int] -> Bool
prop_particiones xs =
  all (\yss -> concat yss == xs) (particiones xs)

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=10}) prop_particiones
--    +++ OK, passed 100 tests.

import Test.QuickCheck

particiones :: [a] -> [[[a]]]

particiones [] = [[]]

particiones xs =

[(take k xs) : yss | k <- [1..n], yss <- particiones (drop k xs)]

where n = length xs

-- La propiedad es

prop_particiones :: [Int] -> Bool

prop_particiones xs =

all (\yss -> concat yss == xs) (particiones xs)

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=10}) prop_particiones

-- +++ OK, passed 100 tests.

Posiciones de equilibrio

PorJosé A. Alonso 15-diciembre-201622-diciembre-2016

Se dice que k es una posición de equilibrio de una lista xs si la suma de los elementos de xs en las posiciones menores que k es igual a la suma de los elementos de xs en las posiciones mayores que k. Por ejemplo, en la lista [-7,1,5,2,-4,3,0] el 3 es una posición de equilibrio ya que -7+1+5 = -4+3+0; también lo es el 6 ya que -7+1+5+2+(-4)+3 = 0.

Definir la función,

   equilibrios :: (Num a, Eq a) => [a] -> [Int]

1	equilibrios :: (Num a, Eq a) => [a] -> [Int]

tal que (equilibrios xs) es la lista de las posiciones de equilibrio de xs. Por ejemplo,

   equilibrios [-7,1,5,2,-4,3,0]  ==  [3,6]
   equilibrios [1..10^6]          ==  []

1 2	equilibrios [-7,1,5,2,-4,3,0] == [3,6] equilibrios [1..10^6] == []

Soluciones

-- 1ª definición
-- =============

equilibrios1 :: (Num a, Eq a) => [a] -> [Int]
equilibrios1 xs =
  [n | n <- [0..length xs - 1]
     , sum (take n xs) == sum (drop (n+1) xs)]

-- 2ª definición
-- =============

equilibrios2 :: (Num a, Eq a) => [a] -> [Int]
equilibrios2 xs =
  [n | (n,x,y) <- zip3 [0..] (sumasI xs) (sumasD xs)
     , x == y]

sumasI :: (Num a, Eq a) => [a] -> [a]
sumasI xs = [sum (take n xs) | n <- [0..length xs - 1]] 

sumasD :: (Num a, Eq a) => [a] -> [a]
sumasD xs = [sum (drop (n+1) xs) | n <- [0..length xs - 1]] 

-- 3ª definición
-- =============

equilibrios3 :: (Num a, Eq a) => [a] -> [Int]
equilibrios3 xs =
  [n | (n,x,y) <- zip3 [0..] (sumasI' xs) (sumasD' xs)
     , x == y]

sumasI' :: (Num a, Eq a) => [a] -> [a]
sumasI'  = init . scanl (+) 0 

sumasD' :: (Num a, Eq a) => [a] -> [a]
sumasD' = tail . scanr (+) 0

-- 4ª definición
-- =============

equilibrios4 :: (Num a, Eq a) => [a] -> [Int]
equilibrios4 xs =
  [n | (n,x,y) <- zip3 [0..] (scanl1 (+) xs) (scanr1 (+) xs)
     , x == y]

-- Comparación de eficiencia
--    λ> let xs = [1..10^4] in equilibrios1 (xs ++ [5] ++ reverse xs)
--    [10000]
--    (20.92 secs, 46,240,541,256 bytes)
--    λ> let xs = [1..10^4] in equilibrios2 (xs ++ [5] ++ reverse xs)
--    [10000]
--    (21.12 secs, 46,249,562,520 bytes)
--    λ> let xs = [1..10^4] in equilibrios3 (xs ++ [5] ++ reverse xs)
--    [10000]
--    (0.02 secs, 11,858,768 bytes)
--    λ> let xs = [1..10^4] in equilibrios4 (xs ++ [5] ++ reverse xs)
--    [10000]
--    (0.02 secs, 13,963,952 bytes)

-- 1ª definición

-- =============

equilibrios1 :: (Num a, Eq a) => [a] -> [Int]

equilibrios1 xs =

[n | n <- [0..length xs - 1]

, sum (take n xs) == sum (drop (n+1) xs)]

-- 2ª definición

-- =============

equilibrios2 :: (Num a, Eq a) => [a] -> [Int]

equilibrios2 xs =

[n | (n,x,y) <- zip3 [0..] (sumasI xs) (sumasD xs)

, x == y]

sumasI :: (Num a, Eq a) => [a] -> [a]

sumasI xs = [sum (take n xs) | n <- [0..length xs - 1]]

sumasD :: (Num a, Eq a) => [a] -> [a]

sumasD xs = [sum (drop (n+1) xs) | n <- [0..length xs - 1]]

-- 3ª definición

-- =============

equilibrios3 :: (Num a, Eq a) => [a] -> [Int]

equilibrios3 xs =

[n | (n,x,y) <- zip3 [0..] (sumasI' xs) (sumasD' xs)

, x == y]

sumasI' :: (Num a, Eq a) => [a] -> [a]

sumasI' = init . scanl (+) 0

sumasD' :: (Num a, Eq a) => [a] -> [a]

sumasD' = tail . scanr (+) 0

-- 4ª definición

-- =============

equilibrios4 :: (Num a, Eq a) => [a] -> [Int]

equilibrios4 xs =

[n | (n,x,y) <- zip3 [0..] (scanl1 (+) xs) (scanr1 (+) xs)

, x == y]

-- Comparación de eficiencia

-- λ> let xs = [1..10^4] in equilibrios1 (xs ++ [5] ++ reverse xs)

-- [10000]

-- (20.92 secs, 46,240,541,256 bytes)

-- λ> let xs = [1..10^4] in equilibrios2 (xs ++ [5] ++ reverse xs)

-- [10000]

-- (21.12 secs, 46,249,562,520 bytes)

-- λ> let xs = [1..10^4] in equilibrios3 (xs ++ [5] ++ reverse xs)

-- [10000]

-- (0.02 secs, 11,858,768 bytes)

-- λ> let xs = [1..10^4] in equilibrios4 (xs ++ [5] ++ reverse xs)

-- [10000]

-- (0.02 secs, 13,963,952 bytes)

Mayores que la mitad

PorJosé A. Alonso 12-diciembre-201619-diciembre-2016

Definir la función

   mayoresMitad :: Ord a => [a] -> [a]

1	mayoresMitad :: Ord a => [a] -> [a]

tal que (mayoresMitad xs) es la lista de los elementos de xs que son mayores que la mitad de los elementos de xs, suponiendo que los elementos de xs son distintos. Por ejemplo,

   sort (mayoresMitad [1,6,3,4])    ==  [4,6]
   sort (mayoresMitad [1,6,3,4,7])  ==  [4,6,7]
   sort (mayoresMitad [1,6,3,4,2])  ==  [3,4,6]
   length (mayoresMitad3 [1..10^6]) ==  500000

sort (mayoresMitad [1,6,3,4]) == [4,6]

sort (mayoresMitad [1,6,3,4,7]) == [4,6,7]

sort (mayoresMitad [1,6,3,4,2]) == [3,4,6]

length (mayoresMitad3 [1..10^6]) == 500000

Nota: Se considera que si la lista tiene 2n+1 elementos, su mitad tiene n elementos.

Soluciones

import Data.List (sort)

-- 1ª solución:
mayoresMitad1 :: Ord a => [a] -> [a]
mayoresMitad1 xs =
  [x | x <- xs
     , length (filter (<=x) xs) > k]
  where k = length xs `div` 2 

-- 2ª solución
mayoresMitad2 :: Ord a => [a] -> [a]
mayoresMitad2 xs = aux xs
  where aux [] = []
        aux (y:ys) | length [x | x <- xs, x <= y] > k = y : aux ys
                   | otherwise                        = aux ys
        k = length xs `div` 2 

-- 3ª solución
mayoresMitad3 :: Ord a => [a] -> [a]
mayoresMitad3 xs = drop k (sort xs)
  where k = length xs `div` 2 

-- Comprobación de eficiencia
--    λ> length (mayoresMitad1 [1..4*10^3])
--    2000
--    (3.79 secs, 442,631,712 bytes)
--    λ> length (mayoresMitad2 [1..4*10^3])
--    2000
--    (11.82 secs, 1,463,762,192 bytes)
--    λ> length (mayoresMitad3 [1..4*10^3])
--    2000
--    (0.02 secs, 0 bytes)

import Data.List (sort)

-- 1ª solución:

mayoresMitad1 :: Ord a => [a] -> [a]

mayoresMitad1 xs =

[x | x <- xs

, length (filter (<=x) xs) > k]

where k = length xs `div` 2

-- 2ª solución

mayoresMitad2 :: Ord a => [a] -> [a]

mayoresMitad2 xs = aux xs

where aux [] = []

aux (y:ys) | length [x | x <- xs, x <= y] > k = y : aux ys

| otherwise = aux ys

k = length xs `div` 2

-- 3ª solución

mayoresMitad3 :: Ord a => [a] -> [a]

mayoresMitad3 xs = drop k (sort xs)

where k = length xs `div` 2

-- Comprobación de eficiencia

-- λ> length (mayoresMitad1 [1..4*10^3])

-- 2000

-- (3.79 secs, 442,631,712 bytes)

-- λ> length (mayoresMitad2 [1..4*10^3])

-- 2000

-- (11.82 secs, 1,463,762,192 bytes)

-- λ> length (mayoresMitad3 [1..4*10^3])

-- 2000

-- (0.02 secs, 0 bytes)

Períodos de Fibonacci

Soluciones

Búsqueda en los dígitos de pi

Soluciones

Particiones de una lista

Soluciones

Posiciones de equilibrio

Soluciones

Mayores que la mitad

Soluciones

Entradas recientes

Buscar

Correo electrónico