import Data.Matrix (Matrix, fromList, nrows, ncols, toList)
ej1, ej2 :: Matrix Int
ej1 = fromList 33[0,0,4,0,5,0,0,0,0]
ej2 = fromList 23[0,1,4,0,5,1]
dispersion ::(Num a, Eq a)=> Matrix a ->Double
dispersion p =
fi nCeros /(fi nrows * fi ncols)where fi f =(fromIntegral . f) p
-- (nCeros p) es el número de ceros de la matriz p. Por ejemplo,-- nCeros ej1 == 7-- nCeros ej2 == 2
nCeros ::(Num a, Eq a)=> Matrix a ->Int
nCeros p =length(filter(==0)(toList p))-- La función anterior se puede definir sin argumentos:
nCeros2 ::(Num a, Eq a)=> Matrix a ->Int
nCeros2 =length . filter(==0) . toList
esDispersa ::(Num a, Eq a)=> Matrix a ->Bool
esDispersa p = dispersion p >0.5-- La función anterior se puede definir sin argumentos:
esDispersa2 ::(Num a, Eq a)=> Matrix a ->Bool
esDispersa2 =(>0.5) . dispersion
import Data.Matrix (Matrix, fromList, nrows, ncols, toList)
ej1, ej2 :: Matrix Int
ej1 = fromList 3 3 [0,0,4,0,5,0,0,0,0]
ej2 = fromList 2 3 [0,1,4,0,5,1]
dispersion :: (Num a, Eq a) => Matrix a -> Double
dispersion p =
fi nCeros / (fi nrows * fi ncols)
where fi f = (fromIntegral . f) p
-- (nCeros p) es el número de ceros de la matriz p. Por ejemplo,
-- nCeros ej1 == 7
-- nCeros ej2 == 2
nCeros :: (Num a, Eq a) => Matrix a -> Int
nCeros p = length (filter (== 0) (toList p))
-- La función anterior se puede definir sin argumentos:
nCeros2 :: (Num a, Eq a) => Matrix a -> Int
nCeros2 = length . filter (== 0) . toList
esDispersa :: (Num a, Eq a) => Matrix a -> Bool
esDispersa p = dispersion p > 0.5
-- La función anterior se puede definir sin argumentos:
esDispersa2 :: (Num a, Eq a) => Matrix a -> Bool
esDispersa2 = (> 0.5) . dispersion
Un árbol binario completo es un árbol en el que cada nodo tiene cero o dos hijos. Por ejemplo, el primero de los siguientes árboles es un árbol binario completo pero los otros no lo son
data Arbol a = N a [Arbol a]derivingShow
ej1, ej2, ej3 :: Arbol Int
ej1 = N 1[N 2[N 4[], N 5[]], N 3[]]
ej2 = N 1[N 2[N 4[]], N 3[]]
ej3 = N 1[N 2[N 4[], N 5[]], N 7[], N 3[]]
esBinarioCompleto :: Arbol t ->Bool
esBinarioCompleto (N _ [])= True
esBinarioCompleto (N x as)=lengthas `elem` [0,2]&&all esBinarioCompleto as
data Arbol a = N a [Arbol a]
deriving Show
ej1, ej2, ej3 :: Arbol Int
ej1 = N 1 [N 2 [N 4 [], N 5 []], N 3 []]
ej2 = N 1 [N 2 [N 4 []], N 3 []]
ej3 = N 1 [N 2 [N 4 [], N 5 []], N 7 [], N 3 []]
esBinarioCompleto :: Arbol t -> Bool
esBinarioCompleto (N _ []) = True
esBinarioCompleto (N x as) = length as `elem` [0,2]
&& all esBinarioCompleto as
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]
λ> 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 (drop2(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))0where 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)
Los huecos binarios de un número natural n son las listas de cer0 entre dos unos en la representación binaria de n. Por ejemplo, puesto que la representación binaria de 20 es 10100 tiene dos huecos binarios de longitudes 1 y 2. La longitud del mayor hueco binario de 529 es 4 ya que la representación binaria de 529 es 1000010001.
Definir las funciones
longMayorHuecoBinario :: Int -> Int
graficaLongMayorHuecoBinario :: Int -> IO ()
longMayorHuecoBinario :: Int -> Int
graficaLongMayorHuecoBinario :: Int -> IO ()
tales que
(longMayorHuecoBinario n) es la longitud del mayor hueco binario de n. Por ejemplo,
(graficaLongMayorHuecoBinario n) dibuja la gráfica de las longitudes de los mayores huecos binarios de los n primeros números naturales. Por ejemplo, (graficaLongMayorHuecoBinario 200) dibuja
Soluciones
import Data.List (group)import Graphics.Gnuplot.Simple
-- 1ª solución-- ===========
longMayorHuecoBinario ::Int->Int
longMayorHuecoBinario n =maximum(0:maplength(huecosBinarios (decimalAbinario n)))-- (decimalAbinario x) es la representación binaria del número c. Por-- ejemplo, -- decimalAbinario 20 == [0,0,1,0,1]-- decimalAbinario 529 == [1,0,0,0,1,0,0,0,0,1]
decimalAbinario ::Int->[Int]
decimalAbinario x
| x <2=[x]|otherwise= x `mod` 2: decimalAbinario (x `div` 2)-- (huecosBinarios xs) es la lista de los ceros consecutivos de xs entre-- dos elementos distintos de cero. Por ejemplo,-- huecosBinarios [0,0,1,0,1] == [[0,0],[0]]-- huecosBinarios [1,0,0,0,1,0,0,0,0,1] == [[0,0,0],[0,0,0,0]]
huecosBinarios ::[Int]->[[Int]]
huecosBinarios xs =[ys | ys <- group xs, 0 `elem` ys]-- 2ª solución-- ===========
longMayorHuecoBinario2 ::Int->Int
longMayorHuecoBinario2 =maximum . (0:) . maplength . huecosBinarios . decimalAbinario
-- 3ª solución-- ===========
longMayorHuecoBinario3 ::Int->Int
longMayorHuecoBinario3 =maximum . longHuecosBinarios
-- (longHuecosBinarios n) es la lista de las longitudes de los huecos-- binarios de n. Por ejemplo,-- longHuecosBinarios 20 == [2,1,0]-- longHuecosBinarios 529 == [3,4,0]
longHuecosBinarios ::Int->[Int]
longHuecosBinarios 1=[0]
longHuecosBinarios n |mod n 2==1= longHuecosBinarios (div n 2)|mod n 4==2=1: h : t
|otherwise=1+ h : t
where(h : t)= longHuecosBinarios (div n 2)-- Comparación de eficiencia-- =========================-- λ> maximum [longMayorHuecoBinario x | x <- [1..100000]]-- 16-- (5.51 secs, 941,090,272 bytes)-- λ> maximum [longMayorHuecoBinario2 x | x <- [1..100000]]-- 16-- (5.54 secs, 933,093,168 bytes)-- λ> maximum [longMayorHuecoBinario3 x | x <- [1..100000]]-- 16-- (6.00 secs, 966,584,848 bytes)
graficaLongMayorHuecoBinario ::Int->IO()
graficaLongMayorHuecoBinario n =
plotList [ Key Nothing
, Title ("graficaLongMayorHuecoBinario "++show n)
, PNG ("Huecos_binarios_"++show n ++".png")][longMayorHuecoBinario k | k <-[0..n-1]]
import Data.List (group)
import Graphics.Gnuplot.Simple
-- 1ª solución
-- ===========
longMayorHuecoBinario :: Int -> Int
longMayorHuecoBinario n =
maximum (0 : map length (huecosBinarios (decimalAbinario n)))
-- (decimalAbinario x) es la representación binaria del número c. Por
-- ejemplo,
-- decimalAbinario 20 == [0,0,1,0,1]
-- decimalAbinario 529 == [1,0,0,0,1,0,0,0,0,1]
decimalAbinario :: Int -> [Int]
decimalAbinario x
| x < 2 = [x]
| otherwise = x `mod` 2 : decimalAbinario (x `div` 2)
-- (huecosBinarios xs) es la lista de los ceros consecutivos de xs entre
-- dos elementos distintos de cero. Por ejemplo,
-- huecosBinarios [0,0,1,0,1] == [[0,0],[0]]
-- huecosBinarios [1,0,0,0,1,0,0,0,0,1] == [[0,0,0],[0,0,0,0]]
huecosBinarios :: [Int] -> [[Int]]
huecosBinarios xs =
[ys | ys <- group xs, 0 `elem` ys]
-- 2ª solución
-- ===========
longMayorHuecoBinario2 :: Int -> Int
longMayorHuecoBinario2 =
maximum . (0 :) . map length . huecosBinarios . decimalAbinario
-- 3ª solución
-- ===========
longMayorHuecoBinario3 :: Int -> Int
longMayorHuecoBinario3 = maximum . longHuecosBinarios
-- (longHuecosBinarios n) es la lista de las longitudes de los huecos
-- binarios de n. Por ejemplo,
-- longHuecosBinarios 20 == [2,1,0]
-- longHuecosBinarios 529 == [3,4,0]
longHuecosBinarios :: Int -> [Int]
longHuecosBinarios 1 = [0]
longHuecosBinarios n | mod n 2 == 1 = longHuecosBinarios (div n 2)
| mod n 4 == 2 = 1 : h : t
| otherwise = 1 + h : t
where (h : t) = longHuecosBinarios (div n 2)
-- Comparación de eficiencia
-- =========================
-- λ> maximum [longMayorHuecoBinario x | x <- [1..100000]]
-- 16
-- (5.51 secs, 941,090,272 bytes)
-- λ> maximum [longMayorHuecoBinario2 x | x <- [1..100000]]
-- 16
-- (5.54 secs, 933,093,168 bytes)
-- λ> maximum [longMayorHuecoBinario3 x | x <- [1..100000]]
-- 16
-- (6.00 secs, 966,584,848 bytes)
graficaLongMayorHuecoBinario :: Int -> IO ()
graficaLongMayorHuecoBinario n =
plotList [ Key Nothing
, Title ("graficaLongMayorHuecoBinario " ++ show n)
, PNG ("Huecos_binarios_" ++ show n ++ ".png")
]
[longMayorHuecoBinario k | k <- [0..n-1]]
Comprobar con QuickCheck que el número de celdas interiores de la retícula cuadrada de lado n, con n > 1, es (n-2)^2.
Soluciones
import Test.QuickCheck
import Data.List.Split (divvy)-- 1ª solución
interiores ::Int->[Int]
interiores n =[i | i <-[n..n*n-n], i `mod` n >1]-- 2ª solución
interiores2 ::Int->[Int]
interiores2 n = aux [n+1..n^2-n]where aux xss@(x:xs)=take(n-2) xs ++ aux (drop n xss)
aux []=[]-- 3ª solución
interiores3 ::Int->[Int]
interiores3 n =concat(divvy (n-2) n [n+2..n*(n-1)-1])-- 4ª solución
interiores4 ::Int->[Int]
interiores4 n =concat[map(+(n*k))[2..n-1]| k <-[1..n-2]]-- 5ª solución
interiores5 ::Int->[Int]
interiores5 n =concat(take(n-2)(iterate(map(+n))[n+2..2*n-1]))-- La propiedad es
prop_interiores ::Int-> Property
prop_interiores n =
n >1==>length(interiores n)==(n-2)^2-- La comprobación es-- λ> quickCheck prop_interiores-- +++ OK, passed 100 tests.
import Test.QuickCheck
import Data.List.Split (divvy)
-- 1ª solución
interiores :: Int -> [Int]
interiores n = [i | i <- [n..n*n-n], i `mod` n > 1]
-- 2ª solución
interiores2 :: Int -> [Int]
interiores2 n = aux [n+1..n^2-n]
where aux xss@(x:xs) = take (n-2) xs ++ aux (drop n xss)
aux [] = []
-- 3ª solución
interiores3 :: Int -> [Int]
interiores3 n = concat (divvy (n-2) n [n+2..n*(n-1)-1])
-- 4ª solución
interiores4 :: Int -> [Int]
interiores4 n = concat [map (+(n*k)) [2..n-1] | k <- [1..n-2]]
-- 5ª solución
interiores5 :: Int -> [Int]
interiores5 n = concat (take (n-2) (iterate (map (+n)) [n+2..2*n-1]))
-- La propiedad es
prop_interiores :: Int -> Property
prop_interiores n =
n > 1 ==> length (interiores n) == (n-2)^2
-- La comprobación es
-- λ> quickCheck prop_interiores
-- +++ OK, passed 100 tests.