Exercitium

Árboles con todas sus ramas con algún elemento que cumple una propiedad

PorJosé A. Alonso 19-marzo-20151-mayo-2015

En lógica temporal, la expresión AFp significa que en algún momento en el futuro se cumple la propiedad p. Trasladado a su interpretación en forma de árbol lo que quiere decir es que en todas las ramas (desde la raíz hasta una hoja) hay un nodo que cumple la propiedad p.

Consideramos el siguiente tipo algebraico de los árboles binarios:

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
                  deriving (Show,Eq)

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show,Eq)

y el siguiente árbol

   a1 :: Arbol Int
   a1 = N 9 (N 3 (H 2) (N 4 (H 1) (H 5))) (H 8)

1 2	a1 :: Arbol Int a1 = N 9 (N 3 (H 2) (N 4 (H 1) (H 5))) (H 8)

En este árbol se cumple (AF par); es decir, en todas las ramas hay un número par; pero no se cumple (AF primo); es decir, hay ramas en las que no hay ningún número primo. Donde una rama es la secuencia de nodos desde el nodo inicial o raíz hasta una hoja.

Definir la función

   propiedadAF :: (a -> Bool) -> Arbol a -> Bool

1	propiedadAF :: (a -> Bool) -> Arbol a -> Bool

tal que (propiedadAF p a) se verifica si se cumple (AF p) en el árbol a; es decir, si en todas las ramas hay un nodo (interno u hoja) que cumple la propiedad p. Por ejemplo

   propiedadAF even a1  ==  True
   propiedadAF (<7) a1  ==  False

1 2	propiedadAF even a1 == True propiedadAF (<7) a1 == False

Soluciones

[schedule expon=’2015-03-26′ expat=»06:00″]

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
             deriving (Show,Eq)

a1 :: Arbol Int
a1 = N 9 (N 3 (H 2) (N 4 (H 1) (H 5))) (H 8)

propiedadAF :: (a -> Bool) -> Arbol a -> Bool
propiedadAF p (H a)     = p a
propiedadAF p (N a i d) = p a || (propiedadAF p i && propiedadAF p d)

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show,Eq)

a1 :: Arbol Int

a1 = N 9 (N 3 (H 2) (N 4 (H 1) (H 5))) (H 8)

propiedadAF :: (a -> Bool) -> Arbol a -> Bool

propiedadAF p (H a) = p a

propiedadAF p (N a i d) = p a || (propiedadAF p i && propiedadAF p d)

Cociente entero de polinomios

PorJosé A. Alonso 18-marzo-20151-mayo-2015

El cociente entero de un polinomio P(x) por un monomio axⁿ es el polinomio que se obtiene a partir de los términos de P(x) con un grado mayor o igual que n, realizando la división entera entre sus coeficientes y el coeficiente del monomio divisor y restando el valor de n al de sus grados. Por ejemplo,

El cociente entero de 4x⁴ + 6x³ + 7x² + 5x + 2 por el monomio 3x² se obtiene a partir de los términos 4x⁴ + 6x³ + 7x² realizando la división entera entre sus coeficientes y el número 3 y restando 2 a sus grados. De esta forma se obtiene x² + 2x + 2
El cociente entero de 6x⁵ + 2x⁴ + 8x³ + 5x² + 8x + 4 por el monomio 4x³ se obtiene a partir de los términos 6x⁵ + 2x⁴ + 8x³ realizando la división entera entre sus coeficientes y el número 4 y restando 3 a sus grados. De esta forma se obtiene x² + 2

Definir la función

   cocienteEntero :: Polinomio Int -> Int -> Int -> Polinomio Int

1	cocienteEntero :: Polinomio Int -> Int -> Int -> Polinomio Int

tal que (cocienteEntero p a n) es el cociente entero del polinomio p por el monomio de grado n y coeficiente a. Por ejemplo,

   ghci> let listaApol xs = foldr (\(n,b) -> consPol n b) polCero xs
   ghci> cocienteEntero (listaApol [(4,4),(3,6),(2,7),(1,5),(0,2)]) 3 2
   x^2 + 2*x + 2
   ghci> cocienteEntero (listaApol [(5,6),(4,2),(3,8),(2,5),(1,8),(0,4)]) 4 3
   x^2 + 2

ghci> let listaApol xs = foldr (\(n,b) -> consPol n b) polCero xs

ghci> cocienteEntero (listaApol [(4,4),(3,6),(2,7),(1,5),(0,2)]) 3 2

x^2 + 2*x + 2

ghci> cocienteEntero (listaApol [(5,6),(4,2),(3,8),(2,5),(1,8),(0,4)]) 4 3

x^2 + 2

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería I1M.Pol que se encuentra aquí y se describe aquí.

Soluciones

import I1M.Pol

cocienteEntero :: Polinomio Int -> Int -> Int -> Polinomio Int
cocienteEntero p a n
    | grado p < n = polCero
    | otherwise   = consPol (grado p - n) (coefLider p `div` a)
                            (cocienteEntero (restoPol p) a n)

import I1M.Pol

cocienteEntero :: Polinomio Int -> Int -> Int -> Polinomio Int

cocienteEntero p a n

| grado p < n = polCero

| otherwise = consPol (grado p - n) (coefLider p `div` a)

(cocienteEntero (restoPol p) a n)

Sucesión de números parientes

PorJosé A. Alonso 17-marzo-20151-mayo-2016

Se dice que dos números naturales son parientes sitienen exactamente un factor primo en común, independientemente de su multiplicidad. Por ejemplo,

Los números 12 (2²·3) y 40 (2³·5) son parientes, pues tienen al 2 como único factor primo en común.
Los números 49 (7²) y 63 (3²·7) son parientes, pues tienen al 7 como único factor primo en común.
Los números 12 (2²·3) y 30 (2·3·5) no son parientes, pues tienen dos factores primos en común.
Los números 49 (7²) y 25 (5²) no son parientes, pues no tienen factores primos en común.

Se dice que una lista de números naturales es una secuencia de parientes si cada par de números consecutivos son parientes. Por ejemplo,

La lista [12,40,35,28] es una secuencia de parientes.
La lista [12,30,21,49] no es una secuencia de parientes.

Definir la función

   secuenciaParientes :: [Integer] -> Bool

1	secuenciaParientes :: [Integer] -> Bool

tal que (secuenciaParientes xs) se verifica si xs es una secuencia de parientes. Por ejemplo,

   secuenciaParientes [12,40,35,28]           ==  True
   secuenciaParientes [12,30,21,49]           ==  False
   secuenciaParientes [2^n | n <- [1..2000]]  ==  True

secuenciaParientes [12,40,35,28] == True

secuenciaParientes [12,30,21,49] == False

secuenciaParientes [2^n | n <- [1..2000]] == True

Soluciones

import Data.List (intersect, nub)
import Data.Numbers.Primes (primes, primeFactors)

-- (parientes x y) se verifica si x e y son parientes. Por ejemplo,
--    parientes 12 40  ==  True
--    parientes 49 63  ==  True
--    parientes 12 30  ==  False
--    parientes 49 25  ==  False

-- 1ª definición (con gcd)
parientes1 :: Integer -> Integer -> Bool
parientes1 x y =
    length [p | p <- takeWhile (<= d) primes, d `mod` p == 0] == 1 
    where d = gcd x y

-- 2ª definición (con primeFactors)
parientes2 :: Integer -> Integer -> Bool
parientes2 0 0 = False
parientes2 x y = 
    length (nub (primeFactors x `intersect` primeFactors y)) == 1

-- Comparación de eficiencia
--    ghci> parientes1 (2^25) (2^25)
--    True
--    (34.34 secs, 15974866184 bytes)
--    ghci> parientes2 (2^25) (2^25)
--    True
--    (0.01 secs, 3093024 bytes)

-- Usaremos la 2ª definición
parientes :: Integer -> Integer -> Bool
parientes = parientes2

-- Definiciones de secuenciaParientes 
-- ==================================

-- 1ª definición (por recursión)
secuenciaParientes :: [Integer] -> Bool
secuenciaParientes []         = True
secuenciaParientes [x]        = True
secuenciaParientes (x1:x2:xs) =
    parientes x1 x2 && secuenciaParientes (x2:xs)

-- 2ª definición (por recursión con 2 ecuaciones)
secuenciaParientes2 :: [Integer] -> Bool
secuenciaParientes2 (x1:x2:xs) =
    parientes x1 x2 && secuenciaParientes2 (x2:xs)
secuenciaParientes2 _         = True

-- 3ª definición (sin recursión):
secuenciaParientes3 :: [Integer] -> Bool
secuenciaParientes3 xs = all (\(x,y) -> parientes x y) (zip xs (tail xs)) 

-- 4ª definición
secuenciaParientes4 :: [Integer] -> Bool
secuenciaParientes4 xs = all (uncurry parientes) (zip xs (tail xs))

import Data.List (intersect, nub)

import Data.Numbers.Primes (primes, primeFactors)

-- (parientes x y) se verifica si x e y son parientes. Por ejemplo,

-- parientes 12 40 == True

-- parientes 49 63 == True

-- parientes 12 30 == False

-- parientes 49 25 == False

-- 1ª definición (con gcd)

parientes1 :: Integer -> Integer -> Bool

parientes1 x y =

length [p | p <- takeWhile (<= d) primes, d `mod` p == 0] == 1

where d = gcd x y

-- 2ª definición (con primeFactors)

parientes2 :: Integer -> Integer -> Bool

parientes2 0 0 = False

parientes2 x y =

length (nub (primeFactors x `intersect` primeFactors y)) == 1

-- Comparación de eficiencia

-- ghci> parientes1 (2^25) (2^25)

-- True

-- (34.34 secs, 15974866184 bytes)

-- ghci> parientes2 (2^25) (2^25)

-- True

-- (0.01 secs, 3093024 bytes)

-- Usaremos la 2ª definición

parientes :: Integer -> Integer -> Bool

parientes = parientes2

-- Definiciones de secuenciaParientes

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

-- 1ª definición (por recursión)

secuenciaParientes :: [Integer] -> Bool

secuenciaParientes [] = True

secuenciaParientes [x] = True

secuenciaParientes (x1:x2:xs) =

parientes x1 x2 && secuenciaParientes (x2:xs)

-- 2ª definición (por recursión con 2 ecuaciones)

secuenciaParientes2 :: [Integer] -> Bool

secuenciaParientes2 (x1:x2:xs) =

parientes x1 x2 && secuenciaParientes2 (x2:xs)

secuenciaParientes2 _ = True

-- 3ª definición (sin recursión):

secuenciaParientes3 :: [Integer] -> Bool

secuenciaParientes3 xs = all (\(x,y) -> parientes x y) (zip xs (tail xs))

-- 4ª definición

secuenciaParientes4 :: [Integer] -> Bool

secuenciaParientes4 xs = all (uncurry parientes) (zip xs (tail xs))

Números como sumas de primos consecutivos

PorJosé A. Alonso 11-marzo-201525-abril-2021

En el artículo Integers as a sum of consecutive primes in 2,3,4,.. ways se presentan números que se pueden escribir como sumas de primos consecutivos de varias formas. Por ejemplo, el 41 se puede escribir de dos formas distintas

   41 =  2 +  3 +  5 + 7 + 11 + 13
   41 = 11 + 13 + 17

1 2	41 = 2 + 3 + 5 + 7 + 11 + 13 41 = 11 + 13 + 17

el 240 se puede escribir de tres formas

   240 =  17 +  19 + 23 + 29 + 31 + 37 + 41 + 43
   240 =  53 +  59 + 61 + 67
   240 = 113 + 127

240 = 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43

240 = 53 + 59 + 61 + 67

240 = 113 + 127

y el 311 se puede escribir de 4 formas

   311 =  11 +  13 +  17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47
   311 =  31 +  37 +  41 + 43 + 47 + 53 + 59
   311 =  53 +  59 +  61 + 67 + 71
   311 = 101 + 103 + 107

311 = 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47

311 = 31 + 37 + 41 + 43 + 47 + 53 + 59

311 = 53 + 59 + 61 + 67 + 71

311 = 101 + 103 + 107

Definir la función

   sumas :: Integer -> [[Integer]]

1	sumas :: Integer -> [[Integer]]

tal que (sumas x) es la lista de las formas de escribir x como suma de dos o más números primos consecutivos. Por ejemplo,

   ghci> sumas 41
   [[2,3,5,7,11,13],[11,13,17]]
   ghci> sumas 240
   [[17,19,23,29,31,37,41,43],[53,59,61,67],[113,127]]
   ghci> sumas 311
   [[11,13,17,19,23,29,31,37,41,43,47],[31,37,41,43,47,53,59],
    [53,59,61,67,71],[101,103,107]]
   ghci> maximum [length (sumas n) | n <- [1..600]]
   4

ghci> sumas 41

[[2,3,5,7,11,13],[11,13,17]]

ghci> sumas 240

[[17,19,23,29,31,37,41,43],[53,59,61,67],[113,127]]

ghci> sumas 311

[[11,13,17,19,23,29,31,37,41,43,47],[31,37,41,43,47,53,59],

[53,59,61,67,71],[101,103,107]]

ghci> maximum [length (sumas n) | n <- [1..600]]

Soluciones

import Data.Numbers.Primes (primes)
import Data.List (span)

sumas :: Integer -> [[Integer]]
sumas x = [ys | n <- takeWhile (< x) primes, 
                let ys = sumaDesde x n,
                not (null ys)]

-- (sumaDesde x n) es la lista de al menos dos números primos
-- consecutivos a partir del número primo n cuya suma es x, si existen y
-- la lista vacía en caso contrario. Por ejemplo,
--    sumaDesde 15 3  ==  [3,5,7]
--    sumaDesde  7 3  ==  []
sumaDesde :: Integer -> Integer -> [Integer]
sumaDesde x n | x == y    = take (1 + length us) ys
              | otherwise = []
    where ys       = dropWhile (<n) primes
          (us,y:_) = span (<x) (scanl1 (+) ys)

import Data.Numbers.Primes (primes)

import Data.List (span)

sumas :: Integer -> [[Integer]]

sumas x = [ys | n <- takeWhile (< x) primes,

let ys = sumaDesde x n,

not (null ys)]

-- (sumaDesde x n) es la lista de al menos dos números primos

-- consecutivos a partir del número primo n cuya suma es x, si existen y

-- la lista vacía en caso contrario. Por ejemplo,

-- sumaDesde 15 3 == [3,5,7]

-- sumaDesde 7 3 == []

sumaDesde :: Integer -> Integer -> [Integer]

sumaDesde x n | x == y = take (1 + length us) ys

| otherwise = []

where ys = dropWhile (<n) primes

(us,y:_) = span (<x) (scanl1 (+) ys)

Actualización de una lista

PorJosé A. Alonso 10-marzo-20152-mayo-2016

Definir la función

   actualiza :: [a] -> [(Int,a)] -> [a]

1	actualiza :: [a] -> [(Int,a)] -> [a]

tal que (actualiza xs ps) es la lista obtenida sustituyendo en xs los elementos cuyos índices son las primeras componentes de ps por las segundas. Por ejemplo,

   actualiza [3,5,2,4] [(2,1),(0,7)]  ==  [7,5,1,4]
   sum (actualiza [1..10^4] [(i,2*i) | i <- [0..10^4-1]]) == 99990000

1 2	actualiza [3,5,2,4] [(2,1),(0,7)] == [7,5,1,4] sum (actualiza [1..10^4] [(i,2*i) \| i <- [0..10^4-1]]) == 99990000

Soluciones

import qualified Data.Vector as V
import Data.Array 

-- 1ª solución (por recursión)
-- ===========================

actualiza :: [a] -> [(Int,a)] -> [a]
actualiza xs []         = xs
actualiza xs ((n,y):ps) = actualiza (actualizaE xs (n,y)) ps

-- (actualizaE xs (n,y)) es la lista obtenida sustituyendo el  elemento
-- n-ésimo de xs por y. Por ejemplo, 
--    actualiza [3,5,2,4] (2,1) ==  [3,5,1,4]
actualizaE :: [a] -> (Int,a) -> [a]
actualizaE xs (n,y) =
    take n xs ++ y : drop (n+1) xs

-- 2ª solución (por tablas)
-- ========================

actualiza2 :: [a] -> [(Int,a)] -> [a]
actualiza2 xs ps = 
    elems (listArray (0,length xs - 1) xs // ps)

-- 3ª solución (por vectores)
-- ==========================

actualiza3 :: [a] -> [(Int,a)] -> [a]
actualiza3 xs ps = 
    V.toList (V.fromList xs V.// ps)

-- Comparación de eficiencia
--    ghci> let n = 10^2 in sum $ actualiza [1..n] [(i,2*i) | i <- [0..n-1]]
--    9900
--    (0.02 secs, 4668984 bytes)
--    ghci> let n = 10^3 in sum $ actualiza [1..n] [(i,2*i) | i <- [0..n-1]]
--    999000
--    (0.28 secs, 77454496 bytes)
--    ghci> let n = 10^4 in sum $ actualiza [1..n] [(i,2*i) | i <- [0..n-1]]
--    99990000
--    (63.46 secs, 8769501704 bytes)
--    
--    ghci> let n = 10^2 in sum $ actualiza2 [1..n] [(i,2*i) | i <- [0..n-1]]
--    9900
--    (0.02 secs, 4147304 bytes)
--    ghci> let n = 10^3 in sum $ actualiza2 [1..n] [(i,2*i) | i <- [0..n-1]]
--    999000
--    (0.02 secs, 4694784 bytes)
--    ghci> let n = 10^4 in sum $ actualiza2 [1..n] [(i,2*i) | i <- [0..n-1]]
--    99990000
--    (0.05 secs, 12276800 bytes)
--    
--    ghci> let n = 10^2 in sum $ actualiza3 [1..n] [(i,2*i) | i <- [0..n-1]]
--    9900
--    (0.01 secs, 4147304 bytes)
--    ghci> let n = 10^3 in sum $ actualiza3 [1..n] [(i,2*i) | i <- [0..n-1]]
--    999000
--    (0.02 secs, 4682680 bytes)
--    ghci> let n = 10^4 in sum $ actualiza3 [1..n] [(i,2*i) | i <- [0..n-1]]
--    99990000
--    (0.04 secs, 12595224 bytes)

import qualified Data.Vector as V

import Data.Array

-- 1ª solución (por recursión)

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

actualiza :: [a] -> [(Int,a)] -> [a]

actualiza xs [] = xs

actualiza xs ((n,y):ps) = actualiza (actualizaE xs (n,y)) ps

-- (actualizaE xs (n,y)) es la lista obtenida sustituyendo el elemento

-- n-ésimo de xs por y. Por ejemplo,

-- actualiza [3,5,2,4] (2,1) == [3,5,1,4]

actualizaE :: [a] -> (Int,a) -> [a]

actualizaE xs (n,y) =

take n xs ++ y : drop (n+1) xs

-- 2ª solución (por tablas)

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

actualiza2 :: [a] -> [(Int,a)] -> [a]

actualiza2 xs ps =

elems (listArray (0,length xs - 1) xs // ps)

-- 3ª solución (por vectores)

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

actualiza3 :: [a] -> [(Int,a)] -> [a]

actualiza3 xs ps =

V.toList (V.fromList xs V.// ps)

-- Comparación de eficiencia

-- ghci> let n = 10^2 in sum $ actualiza [1..n] [(i,2*i) | i <- [0..n-1]]

-- 9900

-- (0.02 secs, 4668984 bytes)

-- ghci> let n = 10^3 in sum $ actualiza [1..n] [(i,2*i) | i <- [0..n-1]]

-- 999000

-- (0.28 secs, 77454496 bytes)

-- ghci> let n = 10^4 in sum $ actualiza [1..n] [(i,2*i) | i <- [0..n-1]]

-- 99990000

-- (63.46 secs, 8769501704 bytes)

-- ghci> let n = 10^2 in sum $ actualiza2 [1..n] [(i,2*i) | i <- [0..n-1]]

-- 9900

-- (0.02 secs, 4147304 bytes)

-- ghci> let n = 10^3 in sum $ actualiza2 [1..n] [(i,2*i) | i <- [0..n-1]]

-- 999000

-- (0.02 secs, 4694784 bytes)

-- ghci> let n = 10^4 in sum $ actualiza2 [1..n] [(i,2*i) | i <- [0..n-1]]

-- 99990000

-- (0.05 secs, 12276800 bytes)

-- ghci> let n = 10^2 in sum $ actualiza3 [1..n] [(i,2*i) | i <- [0..n-1]]

-- 9900

-- (0.01 secs, 4147304 bytes)

-- ghci> let n = 10^3 in sum $ actualiza3 [1..n] [(i,2*i) | i <- [0..n-1]]

-- 999000

-- (0.02 secs, 4682680 bytes)

-- ghci> let n = 10^4 in sum $ actualiza3 [1..n] [(i,2*i) | i <- [0..n-1]]

-- 99990000

-- (0.04 secs, 12595224 bytes)

Árboles con todas sus ramas con algún elemento que cumple una propiedad

Soluciones

Cociente entero de polinomios

Soluciones

Sucesión de números parientes

Soluciones

Números como sumas de primos consecutivos

Soluciones

Actualización de una lista

Soluciones

Entradas recientes

Buscar

Correo electrónico