Menu Close

Etiqueta: zipWith

Suma de números de Fibonacci con índice impar

La sucesión de Fibonacci, F(n), es la siguiente sucesión infinita de números naturales:

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

La sucesión comienza con los números 0 y 1. A partir de estos, cada término es la suma de los dos anteriores.

Definir la función

   sumaFibsIndiceImpar :: Int -> Integer

tal que (sumaFibsIndiceImpar n) es la suma de los n primeros términos de la sucesión de Fibonacci no índice impar; es decir,

   sumaFibsIndiceImpar n = F(1) + F(3) + ... + F(2*n-1)

Por ejemplo,

   sumaFibsIndiceImpar 1  ==  1
   sumaFibsIndiceImpar 2  ==  3
   sumaFibsIndiceImpar 3  ==  8
   sumaFibsIndiceImpar 4  ==  21
   sumaFibsIndiceImpar 5  ==  55
   sumaFibsIndiceImpar (10^4) `rem` (10^9)  ==  213093125

En los ejemplos anteriores se observa que

   sumaFibsIndiceImpar 1  ==  F(2)
   sumaFibsIndiceImpar 2  ==  F(4)
   sumaFibsIndiceImpar 3  ==  F(6)
   sumaFibsIndiceImpar 4  ==  F(8)
   sumaFibsIndiceImpar 5  ==  F(10)

Comprobar con QuickCheck que (sumaFibsIndiceImpar n) es F(2n); es decir, el 2n-ésimo número de Fibonacci

Soluciones

import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
sumaFibsIndiceImpar :: Int -> Integer
sumaFibsIndiceImpar n = sum [fib (2*k-1) | k <- [1..n]]
 
-- (fib n) es el n-ésimo término de la sucesión de Fibonacci. Por
-- ejemplo,
--    fib 6  ==  8
fib :: Int -> Integer
fib n = fibs !! n
 
-- fibs es la lista de términos de 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)
 
-- 2ª solución
-- ============
 
sumaFibsIndiceImpar2 :: Int -> Integer
sumaFibsIndiceImpar2 n =
  sum [a | (a,b) <- zip fibs [0..2*n], odd b]
 
-- Comparación de eficiencia
-- =========================
 
--    λ> sumaFibsIndiceImpar (10^4) `rem` (10^9)
--    213093125
--    (0.98 secs, 13,889,312 bytes)
--    λ> sumaFibsIndiceImpar2 (10^4) `rem` (10^9)
--    213093125
--    (0.05 secs, 18,047,720 bytes)
 
-- Comprobación
-- ============
 
-- La propiedad es
prop_sumaFibsIndiceImpar :: Int -> Property
prop_sumaFibsIndiceImpar n =
  n >= 0 ==> sumaFibsIndiceImpar n == fib (2*n)
 
-- La comprobación es
--    λ> quickCheck prop_sumaFibsIndiceImpar
--    +++ OK, passed 100 tests.

Referencia

Pensamiento

El corazón del poeta, tan rico en sonoridades, es casi un insulto a la afonía cordial de la masa.

Antonio Machado

Sumas alternas de factoriales

Las primeras sumas alternas de los factoriales son números primos; en efecto,

   3! - 2! + 1! = 5
   4! - 3! + 2! - 1! = 19
   5! - 4! + 3! - 2! + 1! = 101
   6! - 5! + 4! - 3! + 2! - 1! = 619
   7! - 6! + 5! - 4! + 3! - 2! + 1! = 4421
   8! - 7! + 6! - 5! + 4! - 3! + 2! - 1! = 35899

son primos, pero

   9! - 8! + 7! - 6! + 5! - 4! + 3! - 2! + 1! = 326981

no es primo.

Definir las funciones

   sumaAlterna         :: Integer -> Integer
   sumasAlternas       :: [Integer]
   conSumaAlternaPrima :: [Integer]

tales que

  • (sumaAlterna n) es la suma alterna de los factoriales desde n hasta 1. Por ejemplo,
     sumaAlterna 3  ==  5
     sumaAlterna 4  ==  19
     sumaAlterna 5  ==  101
     sumaAlterna 6  ==  619
     sumaAlterna 7  ==  4421
     sumaAlterna 8  ==  35899
     sumaAlterna 9  ==  326981
  • sumasAlternas es la sucesión de las sumas alternas de factoriales. Por ejemplo,
     λ> take 10 sumasAlternas
     [0,1,1,5,19,101,619,4421,35899,326981]
  • conSumaAlternaPrima es la sucesión de los números cuya suma alterna de factoriales es prima. Por ejemplo,
     λ> take 8 conSumaAlternaPrima
     [3,4,5,6,7,8,10,15]

Soluciones

import Data.List (cycle, genericTake)
import Data.Numbers.Primes (isPrime)
 
Definiciones de sumaAlterna                                      --
===========================
 
-- 1ª definición
-- -------------
 
sumaAlterna1 :: Integer -> Integer
sumaAlterna1 1 = 1
sumaAlterna1 n = factorial n - sumaAlterna1 (n-1)
 
factorial :: Integer -> Integer
factorial n = product [1..n]
 
-- 2ª definición
-- -------------
 
sumaAlterna2 :: Integer -> Integer
sumaAlterna2 n = sum (zipWith (*) signos (tail factoriales))
    where
      signos | odd n     = 1 : concat (replicate (m `div` 2) [-1,1])
             | otherwise = concat (replicate (m `div` 2) [-1,1])
      m = fromIntegral n
 
-- factoriales es la lista de los factoriales. Por ejemplo,
--    take 7 factoriales  ==  [1,1,2,6,24,120,720]
factoriales :: [Integer]
factoriales = 1 : scanl1 (*) [1..]
 
-- 3ª definición
-- -------------
 
sumaAlterna3 :: Integer -> Integer
sumaAlterna3 n = 
    sum (genericTake n (zipWith (*) signos (tail factoriales)))
    where signos | odd n     = cycle [1,-1]
                 | otherwise = cycle [-1,1]
 
-- Comparación de eficiencia
-- -------------------------
 
--    λ> sumaAlterna1 3000 `mod` (10^6)
--    577019
--    (5.33 secs, 7,025,937,760 bytes)
--    λ> sumaAlterna2 3000 `mod` (10^6)
--    577019
--    (0.03 secs, 15,738,480 bytes)
--    λ> sumaAlterna3 3000 `mod` (10^6)
--    577019
--    (0.05 secs, 16,520,896 bytes)
 
-- En lo que sigue se usa la 2ª definición
sumaAlterna :: Integer -> Integer
sumaAlterna = sumaAlterna2
 
sumasAlternas                                                    --
=============
 
-- 1ª definición
-- -------------
 
sumasAlternas1 :: [Integer]
sumasAlternas1 = [sumaAlterna n | n <- [0..]]
 
-- 2ª definición
-- -------------
 
sumasAlternas2 :: [Integer]
sumasAlternas2 = 0 : zipWith (-) (tail factoriales) sumasAlternas2
 
Definiciones de conSumaAlternaPrima
===================================
 
-- 1ª definición
-- -------------
 
conSumaAlternaPrima1 :: [Integer]
conSumaAlternaPrima1 =
    [n | n <- [0..], isPrime (sumaAlterna n)]
 
-- 2ª definición
-- -------------
 
conSumaAlternaPrima2 :: [Integer]
conSumaAlternaPrima2 =
    [x | (x,y) <- zip [0..] sumasAlternas2, isPrime y]

Pensamiento

¡Fiat umbra! Brotó el pensar humano.
Y el huevo universal alzó, vacío,
ya sin color, desustanciado y frío.

Antonio Machado

Descomposiciones con sumandos 1 o 2

Definir la funciones

   sumas  :: Int -> [[Int]]
   nSumas :: Int -> Integer

tales que

  • (sumas n) es la lista de las descomposiciones de n como sumas cuyos sumandos son 1 ó 2. Por ejemplo,
      sumas 1            ==  [[1]]
      sumas 2            ==  [[1,1],[2]]
      sumas 3            ==  [[1,1,1],[1,2],[2,1]]
      sumas 4            ==  [[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]]
      length (sumas 26)  ==  196418
      length (sumas 33)  ==  5702887
  • (nSumas n) es el número de descomposiciones de n como sumas cuyos sumandos son 1 ó 2. Por ejemplo,
      nSumas 4                      ==  5
      nSumas 123                    ==  36726740705505779255899443
      length (show (nSumas 123456)) ==  25801

Soluciones

import Data.List  (genericIndex, genericLength)
import Data.Array ((!), array)
 
-- 1ª definición de sumas
sumas1 :: Int -> [[Int]]
sumas1 0 = [[]]
sumas1 1 = [[1]]
sumas1 n = [1:xs | xs <- sumas1 (n-1)] ++ [2:xs | xs <- sumas1 (n-2)]
 
-- 2ª definición de sumas
sumas2 :: Int -> [[Int]]
sumas2 0 = [[]]
sumas2 1 = [[1]]
sumas2 n = map (1:) (sumas2 (n-1)) ++ map (2:) (sumas2 (n-2))
 
-- 3ª definición de sumas
sumas3 :: Int -> [[Int]]
sumas3 n = v ! n
  where v = array (0,n) [(i, f i) | i <- [0..n]]
        f 0 = [[]]
        f 1 = [[1]]
        f n = map (1:) (v!(n-1)) ++ map (2:) (v!(n-2))
 
-- 4ª definición de sumas
sumas4 :: Int -> [[Int]]
sumas4 n = aux !! n
  where aux     = [[]] : [[1]] : zipWith f (tail aux) aux
        f xs ys = map (1:) xs ++ map (2:) ys
 
-- Comparación de las definiciones de sumas
--    λ> length (sumas1 28)
--    514229
--    (2.79 secs, 1,739,784,512 bytes)
--    λ> length (sumas2 28)
--    514229
--    (1.33 secs, 1,512,291,248 bytes)
--    λ> length (sumas3 28)
--    514229
--    (0.20 secs, 165,215,800 bytes)
--    λ> length (sumas4 28)
--    514229
--    (0.17 secs, 165,201,592 bytes)
--
--    λ> length (sumas3 33)
--    5702887
--    (2.16 secs, 1,830,761,864 bytes)
--    λ> length (sumas4 33)
--    5702887
--    (1.44 secs, 1,830,749,832 bytes)
 
-- La cuarta definición es más eficiente y es la que usaremos en lo
-- sucesivo:
sumas :: Int -> [[Int]]
sumas = sumas4
 
-- 1ª definición de nSumas
nSumas1 :: Int -> Integer
nSumas1 = genericLength . sumas2
 
-- 2ª definición de nSumas
nSumas2 :: Int -> Integer
nSumas2 0 = 1
nSumas2 1 = 1
nSumas2 n = nSumas2 (n-1) + nSumas2 (n-2)
 
-- 3ª definición de nSumas
nSumas3 :: Int -> Integer
nSumas3 n = v ! n
  where v = array (0,n) [(i,f i) | i <- [0..n]]
        f 0 = 1
        f 1 = 1
        f n = v ! (n-1) + v ! (n-2)
 
-- 4ª definición de nSumas
nSumas4 :: Int -> Integer
nSumas4 n = aux `genericIndex` n
  where aux = 1 : 1 : zipWith (+) aux (tail aux) 
 
-- Comparación de las definiciones de nSumas
--    λ> nSumas1 33
--    5702887
--    (17.32 secs, 23,140,562,600 bytes)
--    λ> nSumas2 33
--    5702887
--    (3.48 secs, 1,870,676,904 bytes)
--    λ> nSumas3 33
--    5702887
--    (0.00 secs, 152,960 bytes)
--    λ> nSumas4 33
--    5702887
--    (0.00 secs, 139,456 bytes)
--    
--    λ> length (show (nSumas3 (2*10^5)))
--    41798
--    (1.41 secs, 1,895,295,528 bytes)
--    λ> length (show (nSumas4 (2*10^5)))
--    41798
--    (2.39 secs, 1,834,998,800 bytes)
 
-- Nota. El valor de (nSumas n) es el n-ésimo término de la sucesión de
-- Fibonacci 1, 1, 2, 3, 5, 8, ...

Pensamiento

Concepto mondo y lirondo
suele ser cáscara hueca;
puede ser caldera al rojo.

Antonio Machado

Operaciones con series de potencias

Una serie de potencias es una serie de la forma

   a₀ + a₁x + a₂x² + a₃x³ + ...

Las series de potencias se pueden representar mediante listas infinitas. Por ejemplo, la serie de la función exponencial es

   e^x = 1 + x + x²/2! + x³/3! + ...

y se puede representar por [1, 1, 1/2, 1/6, 1/24, 1/120, …]

Las operaciones con series se pueden ver como una generalización de las de los polinomios.

En lo que sigue, usaremos el tipo (Serie a) para representar las series de potencias con coeficientes en a y su definición es

   type Serie a = [a]

Definir las siguientes funciones

   opuesta      :: Num a => Serie a -> Serie a
   suma         :: Num a => Serie a -> Serie a -> Serie a
   resta        :: Num a => Serie a -> Serie a -> Serie a
   producto     :: Num a => Serie a -> Serie a -> Serie a
   cociente     :: Fractional a => Serie a -> Serie a -> Serie a
   derivada     :: (Num a, Enum a) => Serie a -> Serie a
   integral     :: (Fractional a, Enum a) => Serie a -> Serie a
   expx         :: Serie Rational

tales que

  • (opuesta xs) es la opuesta de la serie xs. Por ejemplo,
     λ> take 7 (opuesta [-6,-4..])
     [6,4,2,0,-2,-4,-6]
  • (suma xs ys) es la suma de las series xs e ys. Por ejemplo,
     λ> take 7 (suma [1,3..] [2,4..])
     [3,7,11,15,19,23,27]
  • (resta xs ys) es la resta de las series xs es ys. Por ejemplo,
     λ> take 7 (resta [3,5..] [2,4..])
     [1,1,1,1,1,1,1]
     λ> take 7 (resta ([3,7,11,15,19,23,27] ++ repeat 0) [1,3..])
     [2,4,6,8,10,12,14]
  • (producto xs ys) es el producto de las series xs e ys. Por ejemplo,
     λ> take 7 (producto [3,5..] [2,4..])
     [6,22,52,100,170,266,392]
  • (cociente xs ys) es el cociente de las series xs e ys. Por ejemplo,
     λ> take 7 (cociente ([6,22,52,100,170,266,392] ++ repeat 0) [3,5..])
     [2.0,4.0,6.0,8.0,10.0,12.0,14.0]
  • (derivada xs) es la derivada de la serie xs. Por ejemplo,
     λ> take 7 (derivada [2,4..])
     [4,12,24,40,60,84,112]
  • (integral xs) es la integral de la serie xs. Por ejemplo,
     λ> take 7 (integral ([4,12,24,40,60,84,112] ++ repeat 0))
     [0.0,4.0,6.0,8.0,10.0,12.0,14.0]
  • expx es la serie de la función exponencial. Por ejemplo,
     λ> take 8 expx
     [1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
     λ> take 8 (derivada expx)
     [1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
     λ> take 8 (integral expx)
     [0 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]

Soluciones

type Serie a = [a] 
 
opuesta :: Num a => Serie a -> Serie a
opuesta = map negate
 
suma :: Num a => Serie a -> Serie a -> Serie a
suma = zipWith (+)
 
resta :: Num a => Serie a -> Serie a -> Serie a
resta xs ys = suma xs (opuesta ys)
 
producto :: Num a => Serie a -> Serie a -> Serie a
producto (x:xs) zs@(y:ys) = 
    x*y : suma (producto xs zs) (map (x*) ys)
 
cociente :: Fractional a => Serie a -> Serie a -> Serie a
cociente (x:xs) (y:ys) = zs 
    where zs = x/y : map (/y) (resta xs (producto zs ys))  
 
derivada :: (Num a, Enum a) => Serie a -> Serie a
derivada (_:xs) = zipWith (*) xs [1..]
 
integral :: (Fractional a, Enum a) => Serie a -> Serie a
integral xs = 0 : zipWith (/) xs [1..]
 
expx :: Serie Rational
expx = map (1/) (map fromIntegral factoriales)
 
-- factoriales es la lista de los factoriales. Por ejemplo, 
--    take 7 factoriales  ==  [1,1,2,6,24,120,720]
factoriales :: [Integer]
factoriales = 1 : scanl1 (*) [1..]

Pensamiento

Ni mármol duro y eterno,
ni música ni pintura,
sino palabra en el tiempo.

Antonio Machado

Problema de las puertas

Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puertas (es decir, abrir las cerradas y cerrar las abiertas). El proceso es el siguiente:

  • Inicialmente todas las puertas están cerradas.
  • El primer camarero cambia de estado las puertas de todas las habitaciones.
  • El segundo cambia de estado de las puertas de las habitaciones pares.
  • El tercero cambia de estado todas las puertas que son múltiplos de 3.
  • El cuarto cambia de estado todas las puertas que son múltiplos de 4
  • Así hasta que ha pasado el último camarero.

Por ejemplo, para n = 5

   Pase    | Puerta 1 | Puerta 2 | Puerta 3 | Puerta 4 | Puerta 5
   Inicial | Cerrada  | Cerrada  | Cerrada  | Cerrada  | Cerrada
   Pase 1  | Abierta  | Abierta  | Abierta  | Abierta  | Abierta
   Pase 2  | Abierta  | Cerrada  | Abierta  | Cerrada  | Abierta
   Pase 3  | Abierta  | Cerrada  | Cerrada  | Cerrada  | Abierta
   Pase 4  | Abierta  | Cerrada  | Cerrada  | Abierta  | Abierta
   Pase 5  | Abierta  | Cerrada  | Cerrada  | Abierta  | Cerrada

Los estados de las puertas se representan por el siguiente tipo de datos

   data Estado = Abierta | Cerrada deriving Show

Definir la función

   final :: Int -> [Estado]

tal que (final n) es la lista de los estados de las n puertas después de que hayan pasado los n camareros. Por ejemplo,

   ghci> final 5
   [Abierta,Cerrada,Cerrada,Abierta,Cerrada]
   ghci> final 7
   [Abierta,Cerrada,Cerrada,Abierta,Cerrada,Cerrada,Cerrada]

Soluciones

-- 1ª solución
-- ===========
 
data Estado = Abierta | Cerrada 
              deriving (Eq, Show)
 
cambia Abierta = Cerrada
cambia Cerrada = Abierta
 
-- (inicial n) es el estado inicial para el problema de las n
-- habitaciones. Por ejemplo,
--    inicial 5  ==  [Cerrada,Cerrada,Cerrada,Cerrada,Cerrada]
inicial :: Int -> [Estado]
inicial n = replicate n Cerrada
 
-- (pase k es) es la lista de los estados de las puertas después de pasar el
-- camarero k que las encuentra en los estados es. Por ejemplo,
--    ghci> pase 1 (inicial 5)
--    [Abierta,Abierta,Abierta,Abierta,Abierta]
--    ghci> pase 2 it
--    [Abierta,Cerrada,Abierta,Cerrada,Abierta]
--    ghci> pase 3 it
--    [Abierta,Cerrada,Cerrada,Cerrada,Abierta]
--    ghci> pase 4 it
--    [Abierta,Cerrada,Cerrada,Abierta,Abierta]
--    ghci> pase 5 it
--    [Abierta,Cerrada,Cerrada,Abierta,Cerrada]
pase :: [Estado] -> Int -> [Estado] 
pase es k = zipWith cambiaK  es[1..] 
  where cambiaK e n | n `mod` k == 0 = cambia e
                    | otherwise      = e
 
final :: Int -> [Estado]
final n = aux [1..n] (inicial n) 
  where aux []     es = es  
        aux (k:ks) es = aux ks (pase es k)
 
-- 2ª solución
-- ===========
 
final2 :: Int -> [Estado]
final2 n = foldl pase (inicial n) [1..n] 
 
-- 3ª solución
-- =============
 
final3 :: Int -> [Estado]
final3 n = map f [1..n]
  where f x | even (length (divisores x)) = Cerrada
            | otherwise                   = Abierta
 
divisores :: Int -> [Int]
divisores n = [x | x <- [1..n], n `mod` x == 0]
 
-- 4ª solución
-- ===========
 
-- En primer lugar, vamos a determinar la lista de las posiciones
-- (comenzando a contar en 1) de las puertas que quedan abierta en el
-- problema de las n puertas. 
posicionesAbiertas :: Int -> [Int]
posicionesAbiertas n = 
  [x | (x,y) <- zip [1..] (final n), y == Abierta]
 
-- Al calcularlas,
--    ghci> posicionesAbiertas 200
--    [1,4,9,16,25,36,49,64,81,100,121,144,169,196]
-- Se observa las que quedan abiertas son las que sus posiciones son
-- cuadrados perfectos. Usando esta observación se construye la
-- siguiente definición
 
final4 :: Int -> [Estado]
final4 n = aux [1..n] [k*k | k <- [1..]] 
  where aux (x:xs) (y:ys) | x == y  =  Abierta : aux xs ys
        aux (x:xs) ys               =  Cerrada : aux xs ys
        aux []     _                =  []
 
-- ---------------------------------------------------------------------
-- § Comparación de eficiencia                                        --
-- ---------------------------------------------------------------------
 
--    ghci> last (final 1000)
--    Cerrada
--    (0.23 secs, 218727400 bytes)
--    ghci> last (final 2000)
--    Cerrada
--    (1.78 secs, 868883080 bytes)
--    ghci> last (final2 1000)
--    Cerrada
--    (0.08 secs, 218729392 bytes)
--    ghci> last (final2 2000)
--    Cerrada
--    (1.77 secs, 868948600 bytes)
--    ghci> last (final3 1000)
--    Cerrada
--    (0.01 secs, 1029256 bytes)
--    ghci> last (final3 2000)
--    Cerrada
--    (0.01 secs, 2121984 bytes)
--    ghci> last (final4 1000)
--    Cerrada
--    (0.01 secs, 1029328 bytes)
--    ghci> last (final4 2000)
--    Cerrada
--    (0.01 secs, 1578504 bytes)
--    ghci> last (final3 10000)
--    Abierta
--    (0.01 secs, 4670104 bytes)
--    ghci> last (final3 100000)
--    Cerrada
--    (0.09 secs, 38717032 bytes)
--    ghci> last (final3 1000000)
--    Abierta
--    (1.27 secs, 377100832 bytes)
--    ghci> last (final4 1000000)
--    Abierta
--    (1.41 secs, 273292448 bytes)

Pensamiento

… cuánto exilio en la presencia cabe.

Antonio Machado