Recursión

Números superpares

PorJosé A. Alonso 12-abril-201819-abril-2018

Definir la función

   superpar :: Int -> Bool

1	superpar :: Int -> Bool

tal que (superpar n) se verifica si n es un número par tal que todos sus dígitos son pares. Por ejemplo,

   superpar 426  ==  True
   superpar 456  ==  False

1 2	superpar 426 == True superpar 456 == False

Soluciones

-- 1ª definición (por recursión)
superpar :: Int -> Bool
superpar n | n < 10    = even n
           | otherwise = even n && superpar (n `div` 10)

-- 2ª definición (por comprensión):
superpar2 :: Int -> Bool
superpar2 n = and [even d | d <- digitos n]

digitos :: Int -> [Int]
digitos n = [read [d] | d <- show n]

-- 3ª definición (por recursión sobre los dígitos):
superpar3 :: Int -> Bool
superpar3 n = sonPares (digitos n)
    where sonPares []     = True
          sonPares (d:ds) = even d && sonPares ds

-- la función sonPares se puede definir por plegado:
superpar3' :: Int -> Bool
superpar3' n = sonPares (digitos n)
    where sonPares ds = foldr ((&&) . even) True ds

-- 4ª definición (con all):
superpar4 :: Int -> Bool
superpar4 n = all even (digitos n)

-- 5ª definición (con filter):
superpar5 :: Int -> Bool
superpar5 n = filter even (digitos n) == digitos n

-- 6ª definición (con filter):
superpar6 :: Int -> Bool
superpar6 n = all (`elem` "02468") (show n)

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

superpar :: Int -> Bool

superpar n | n < 10 = even n

| otherwise = even n && superpar (n `div` 10)

-- 2ª definición (por comprensión):

superpar2 :: Int -> Bool

superpar2 n = and [even d | d <- digitos n]

digitos :: Int -> [Int]

digitos n = [read [d] | d <- show n]

-- 3ª definición (por recursión sobre los dígitos):

superpar3 :: Int -> Bool

superpar3 n = sonPares (digitos n)

where sonPares [] = True

sonPares (d:ds) = even d && sonPares ds

-- la función sonPares se puede definir por plegado:

superpar3' :: Int -> Bool

superpar3' n = sonPares (digitos n)

where sonPares ds = foldr ((&&) . even) True ds

-- 4ª definición (con all):

superpar4 :: Int -> Bool

superpar4 n = all even (digitos n)

-- 5ª definición (con filter):

superpar5 :: Int -> Bool

superpar5 n = filter even (digitos n) == digitos n

-- 6ª definición (con filter):

superpar6 :: Int -> Bool

superpar6 n = all (`elem` "02468") (show n)

Ampliación de árboles binarios

PorJosé A. Alonso 9-abril-201816-abril-2018

Representamos los árboles binarios mediante el tipo de dato

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

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

Una forma de ampliar un árbol binario es añadiendo un nuevo nivel donde
las nuevas hojas sean iguales a la suma de los valores de los nodos
desde el padre hasta llegar a la raíz (inclusives). Por ejemplo:

      5               5       |         3                3
     / \             / \      |        / \             /   \
    2   0    ==>    2   0     |       2   4    ==>    2     4
                   / \ / \    |      / \             / \   / \
                  7  7 5  5   |     0   1           0   1 7   7
                              |                    /\   /\
                              |                   5  5 6  6

5 5 | 3 3

/ \ / \ | / \ / \

2 0 ==> 2 0 | 2 4 ==> 2 4

/ \ / \ | / \ / \ / \

7 7 5 5 | 0 1 0 1 7 7

| /\ /\

| 5 5 6 6

Definir la función

   ampliaArbol:: Num a => Arbol a -> Arbol a

1	ampliaArbol:: Num a => Arbol a -> Arbol a

tal que (ampliaArbol a) es el árbol a ampliado en un nivel. Por
ejemplo,

   λ> ampliaArbol (N 5 (H 2)(H 0))
   N 5 (N 2 (H 7) (H 7)) (N 0 (H 5) (H 5))
   λ> ampliaArbol (N 3 (N 2 (H 0) (H 1)) (H 4))
   N 3 (N 2 (N 0 (H 5) (H 5)) (N 1 (H 6) (H 6))) (N 4 (H 7) (H 7))
   λ> ampliaArbol (H 1)
   N 1 (H 1) (H 1)
   λ> ampliaArbol N 1 (H 1) (H 1)
   N 1 (N 1 (H 2) (H 2)) (N 1 (H 2) (H 2))

λ> ampliaArbol (N 5 (H 2)(H 0))

N 5 (N 2 (H 7) (H 7)) (N 0 (H 5) (H 5))

λ> ampliaArbol (N 3 (N 2 (H 0) (H 1)) (H 4))

N 3 (N 2 (N 0 (H 5) (H 5)) (N 1 (H 6) (H 6))) (N 4 (H 7) (H 7))

λ> ampliaArbol (H 1)

N 1 (H 1) (H 1)

λ> ampliaArbol N 1 (H 1) (H 1)

N 1 (N 1 (H 2) (H 2)) (N 1 (H 2) (H 2))

Soluciones

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

ampliaArbol :: Num a => Arbol a -> Arbol a
ampliaArbol a = aux 0 a
  where aux n (H x)     = N x (H (n+x)) (H (n+x))
        aux n (N x i d) = N x (aux (n+x) i) (aux (n+x) d)

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

ampliaArbol :: Num a => Arbol a -> Arbol a

ampliaArbol a = aux 0 a

where aux n (H x) = N x (H (n+x)) (H (n+x))

aux n (N x i d) = N x (aux (n+x) i) (aux (n+x) d)

Clases de equivalencia

PorJosé A. Alonso 5-abril-201812-abril-2018

Definir la función

   clasesEquivalencia :: Ord a => 
                         Set a -> (a -> a -> Bool) -> Set (Set a)

1 2	clasesEquivalencia :: Ord a => Set a -> (a -> a -> Bool) -> Set (Set a)

tal que (clasesEquivalencia xs r) es el conjunto de las clases de equivalencia de xs respecto de la relación de equivalencia r. Por ejemplo,

   ghci> let c = fromList [-3..3]
   ghci> clasesEquivalencia c (\x y -> x `mod` 3 == y `mod` 3)
   fromList [fromList [-3,0,3],fromList [-2,1],fromList [-1,2]]
   ghci> clasesEquivalencia c (\x y -> (x - y) `mod` 2 == 0)
   fromList [fromList [-3,-1,1,3],fromList [-2,0,2]]

ghci> let c = fromList [-3..3]

ghci> clasesEquivalencia c (\x y -> x `mod` 3 == y `mod` 3)

fromList [fromList [-3,0,3],fromList [-2,1],fromList [-1,2]]

ghci> clasesEquivalencia c (\x y -> (x - y) `mod` 2 == 0)

fromList [fromList [-3,-1,1,3],fromList [-2,0,2]]

Soluciones

import Data.Set as S

clasesEquivalencia :: Ord a => 
                      Set a -> (a -> a -> Bool) -> Set (Set a)
clasesEquivalencia xs r 
    | S.null xs =  empty
    | otherwise =  us `insert` clasesEquivalencia vs r
    where (y,ys)  = deleteFindMin xs
          (us,vs) = partition (r y) xs

import Data.Set as S

clasesEquivalencia :: Ord a =>

Set a -> (a -> a -> Bool) -> Set (Set a)

clasesEquivalencia xs r

| S.null xs = empty

| otherwise = us `insert` clasesEquivalencia vs r

where (y,ys) = deleteFindMin xs

(us,vs) = partition (r y) xs

La carrera de Collatz

PorJosé A. Alonso 4-abril-201811-abril-2018

Sea f la siguiente función, aplicable a cualquier número entero positivo:

Si el número es par, se divide entre 2.
Si el número es impar, se multiplica por 3 y se suma 1.

La carrera de Collatz consiste en, dada una lista de números ns, sustituir cada número n de ns por f(n) hasta que alguno sea igual a 1. Por ejemplo, la siguiente sucesión es una carrera de Collatz

   [ 3, 6,20, 49, 73]
   [10, 3,10,148,220]
   [ 5,10, 5, 74,110]
   [16, 5,16, 37, 55]
   [ 8,16, 8,112,166]
   [ 4, 8, 4, 56, 83]
   [ 2, 4, 2, 28,250]
   [ 1, 2, 1, 14,125]

[ 3, 6,20, 49, 73]

[10, 3,10,148,220]

[ 5,10, 5, 74,110]

[16, 5,16, 37, 55]

[ 8,16, 8,112,166]

[ 4, 8, 4, 56, 83]

[ 2, 4, 2, 28,250]

[ 1, 2, 1, 14,125]

En esta carrera, los ganadores son 3 y 20.

Definir la función

   ganadores :: [Int] -> [Int]

1	ganadores :: [Int] -> [Int]

tal que (ganadores ns) es la lista de los ganadores de la carrera de Collatz a partir de la lista inicial ns. Por ejmplo,

   ganadores [3,6,20,49,73]  ==  [3,20]

1	ganadores [3,6,20,49,73] == [3,20]

Soluciones

ganadores :: [Int] -> [Int]
ganadores xs = selecciona xs (final xs)

-- (final xs) es el estado final de la carrera de Collatz a partir de
-- xs. Por ejemplo,
--    final [3,6,20,49,73]  ==  [1,2,1,14,125]
final :: [Int] -> [Int]
final xs | elem 1 xs = xs
         | otherwise = final [siguiente x | x <- xs]

-- (siguiente x) es el siguiente de x en la carrera de Collatz. Por
-- ejemplo, 
--    siguiente 3  ==  10
--    siguiente 6  ==  3
siguiente :: Int -> Int
siguiente x | even x    = x `div` 2
            | otherwise = 3*x+1

-- (selecciona xs ys) es la lista de los elementos de xs cuyos tales que
-- los elementos de ys en la misma posición son iguales a 1. Por ejemplo,
--    selecciona [3,6,20,49,73] [1,2,1,14,125]  ==  [3,20]
selecciona :: [Int] -> [Int] -> [Int]
selecciona xs ys =
  [x | (x,y) <- zip xs ys, y == 1]

ganadores :: [Int] -> [Int]

ganadores xs = selecciona xs (final xs)

-- (final xs) es el estado final de la carrera de Collatz a partir de

-- xs. Por ejemplo,

-- final [3,6,20,49,73] == [1,2,1,14,125]

final :: [Int] -> [Int]

final xs | elem 1 xs = xs

| otherwise = final [siguiente x | x <- xs]

-- (siguiente x) es el siguiente de x en la carrera de Collatz. Por

-- ejemplo,

-- siguiente 3 == 10

-- siguiente 6 == 3

siguiente :: Int -> Int

siguiente x | even x = x `div` 2

| otherwise = 3*x+1

-- (selecciona xs ys) es la lista de los elementos de xs cuyos tales que

-- los elementos de ys en la misma posición son iguales a 1. Por ejemplo,

-- selecciona [3,6,20,49,73] [1,2,1,14,125] == [3,20]

selecciona :: [Int] -> [Int] -> [Int]

selecciona xs ys =

[x | (x,y) <- zip xs ys, y == 1]

Árbol de subconjuntos

PorJosé A. Alonso 30-marzo-20187-abril-2018

Definir las siguientes funciones

   arbolSubconjuntos       :: [a] -> Tree [a]
   nNodosArbolSubconjuntos :: Integer -> Integer
   sumaNNodos              :: Integer -> Integer

arbolSubconjuntos :: [a] -> Tree [a]

nNodosArbolSubconjuntos :: Integer -> Integer

sumaNNodos :: Integer -> Integer

tales que

(arbolSubconjuntos xs) es el árbol de los subconjuntos de xs. Por ejemplo.

     λ> putStrLn (drawTree (arbolSubconjuntos "abc"))
     abc
     |
     +- bc
     |  |
     |  +- c
     |  |
     |  `- b
     |
     +- ac
     |  |
     |  +- c
     |  |
     |  `- a
     |
     `- ab
        |
        +- b
        |
        `- a

λ> putStrLn (drawTree (arbolSubconjuntos "abc"))

abc

+- bc

| |

| +- c

| |

| `- b

+- ac

| |

| +- c

| |

| `- a

`- ab

+- b

`- a

(nNodosArbolSubconjuntos xs) es el número de nodos del árbol de xs. Por ejemplo

     nNodosArbolSubconjuntos "abc"  ==  10
     nNodosArbolSubconjuntos [1..4*10^4] `mod` (7+10^9) == 546503960

1 2	nNodosArbolSubconjuntos "abc" == 10 nNodosArbolSubconjuntos [1..4*10^4] `mod` (7+10^9) == 546503960

(sumaNNodos n) es la suma del número de nodos de los árboles de los subconjuntos de [1..k] para 1 <= k <= n. Por ejemplo,

     λ> sumaNNodos 3  ==  14
     sumaNNodos (4*10^4) `mod` (7+10^9)  ==  249479844

1 2	λ> sumaNNodos 3 == 14 sumaNNodos (4*10^4) `mod` (7+10^9) == 249479844

Soluciones

import Data.List (genericLength, genericTake)
import Data.Tree (Tree (Node))

-- Definición de arbolSubconjuntos
-- ===============================

arbolSubconjuntos :: [a] -> Tree [a]
arbolSubconjuntos [x] = Node [x] []
arbolSubconjuntos xs =
  Node xs (map arbolSubconjuntos (sinUno xs))

-- (sinUno xs) es la lista obtenidas eliminando un elemento de xs. Por
-- ejemplo, 
--    sinUno "abcde"  ==  ["bcde","acde","abde","abce","abcd"]
sinUno :: [a] -> [[a]]
sinUno xs =
  [ys ++ zs | n <- [0..length xs - 1]
            , let (ys,_:zs) = splitAt n xs]       

-- 1ª definición de nNodosArbolSubconjuntos
-- ========================================

nNodosArbolSubconjuntos :: [a] -> Integer
nNodosArbolSubconjuntos =
  fromIntegral . length . arbolSubconjuntos 

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

nNodosArbolSubconjuntos2 :: [a] -> Integer
nNodosArbolSubconjuntos2 = aux . genericLength
  where aux 1 = 1
        aux n = 1 + n * aux (n-1)

-- 3ª definición de nNodosArbolSubconjuntos
-- ========================================

nNodosArbolSubconjuntos3 :: [a] -> Integer
nNodosArbolSubconjuntos3 xs =
  sucNNodos !! (n-1)
  where n = length xs

-- sucNNodos es la sucesión de los números de nodos de los árboles de
-- los subconjuntos con 1, 2, ... elementos. Por ejemplo.
--    λ> take 10 sucNNodos
--    [1,3,10,41,206,1237,8660,69281,623530,6235301]
sucNNodos :: [Integer]
sucNNodos =
  1 : map (+ 1) (zipWith (*) [2..] sucNNodos)

-- Comparación de eficiencia de nNodosArbolSubconjuntos
-- ====================================================

--    λ> nNodosArbolSubconjuntos 10
--    6235301
--    (9.66 secs, 5,491,704,944 bytes)
--    λ> nNodosArbolSubconjuntos2 10
--    6235301
--    (0.00 secs, 145,976 bytes)
--
--    λ> length (show (nNodosArbolSubconjuntos2 (4*10^4)))
--    166714
--    (1.07 secs, 2,952,675,472 bytes)
--    λ> length (show (nNodosArbolSubconjuntos3 (4*10^4)))
--    166714
--    (1.53 secs, 2,959,020,680 bytes)

-- 1ª definición de sumaNNodos
-- ===========================

sumaNNodos :: Integer -> Integer
sumaNNodos n =
  sum [nNodosArbolSubconjuntos [1..k] | k <- [1..n]]

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

sumaNNodos2 :: Integer -> Integer
sumaNNodos2 n =
  sum [nNodosArbolSubconjuntos2 [1..k] | k <- [1..n]]

-- 3ª definición de sumaNNodos
-- ===========================

sumaNNodos3 :: Integer -> Integer
sumaNNodos3 n =
  sum (genericTake n sucNNodos)

-- Comparación de eficiencia de sumaNNodos
-- =======================================

--    λ> sumaNNodos 10 `mod` (7+10^9)
--    6938270
--    (16.00 secs, 9,552,410,688 bytes)
--    λ> sumaNNodos2 10 `mod` (7+10^9)
--    6938270
--    (0.00 secs, 177,632 bytes)
-- 
--    λ> sumaNNodos2 (2*10^3) `mod` (7+10^9)
--    851467820
--    (2.62 secs, 4,622,117,976 bytes)
--    λ> sumaNNodos3 (2*10^3) `mod` (7+10^9)
--    851467820
--    (0.01 secs, 8,645,336 bytes)

100

101

102

103

104

import Data.List (genericLength, genericTake)

import Data.Tree (Tree (Node))

-- Definición de arbolSubconjuntos

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

arbolSubconjuntos :: [a] -> Tree [a]

arbolSubconjuntos [x] = Node [x] []

arbolSubconjuntos xs =

Node xs (map arbolSubconjuntos (sinUno xs))

-- (sinUno xs) es la lista obtenidas eliminando un elemento de xs. Por

-- ejemplo,

-- sinUno "abcde" == ["bcde","acde","abde","abce","abcd"]

sinUno :: [a] -> [[a]]

sinUno xs =

[ys ++ zs | n <- [0..length xs - 1]

, let (ys,_:zs) = splitAt n xs]

-- 1ª definición de nNodosArbolSubconjuntos

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

nNodosArbolSubconjuntos :: [a] -> Integer

nNodosArbolSubconjuntos =

fromIntegral . length . arbolSubconjuntos

-- 2ª definición de nNodosArbolSubconjuntos

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

nNodosArbolSubconjuntos2 :: [a] -> Integer

nNodosArbolSubconjuntos2 = aux . genericLength

where aux 1 = 1

aux n = 1 + n * aux (n-1)

-- 3ª definición de nNodosArbolSubconjuntos

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

nNodosArbolSubconjuntos3 :: [a] -> Integer

nNodosArbolSubconjuntos3 xs =

sucNNodos !! (n-1)

where n = length xs

-- sucNNodos es la sucesión de los números de nodos de los árboles de

-- los subconjuntos con 1, 2, ... elementos. Por ejemplo.

-- λ> take 10 sucNNodos

-- [1,3,10,41,206,1237,8660,69281,623530,6235301]

sucNNodos :: [Integer]

sucNNodos =

1 : map (+ 1) (zipWith (*) [2..] sucNNodos)

-- Comparación de eficiencia de nNodosArbolSubconjuntos

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

-- λ> nNodosArbolSubconjuntos 10

-- 6235301

-- (9.66 secs, 5,491,704,944 bytes)

-- λ> nNodosArbolSubconjuntos2 10

-- 6235301

-- (0.00 secs, 145,976 bytes)

-- λ> length (show (nNodosArbolSubconjuntos2 (4*10^4)))

-- 166714

-- (1.07 secs, 2,952,675,472 bytes)

-- λ> length (show (nNodosArbolSubconjuntos3 (4*10^4)))

-- 166714

-- (1.53 secs, 2,959,020,680 bytes)

-- 1ª definición de sumaNNodos

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

sumaNNodos :: Integer -> Integer

sumaNNodos n =

sum [nNodosArbolSubconjuntos [1..k] | k <- [1..n]]

-- 2ª definición de sumaNNodos

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

sumaNNodos2 :: Integer -> Integer

sumaNNodos2 n =

sum [nNodosArbolSubconjuntos2 [1..k] | k <- [1..n]]

-- 3ª definición de sumaNNodos

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

sumaNNodos3 :: Integer -> Integer

sumaNNodos3 n =

sum (genericTake n sucNNodos)

-- Comparación de eficiencia de sumaNNodos

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

-- λ> sumaNNodos 10 `mod` (7+10^9)

-- 6938270

-- (16.00 secs, 9,552,410,688 bytes)

-- λ> sumaNNodos2 10 `mod` (7+10^9)

-- 6938270

-- (0.00 secs, 177,632 bytes)

-- λ> sumaNNodos2 (2*10^3) `mod` (7+10^9)

-- 851467820

-- (2.62 secs, 4,622,117,976 bytes)

-- λ> sumaNNodos3 (2*10^3) `mod` (7+10^9)

-- 851467820

-- (0.01 secs, 8,645,336 bytes)

Números superpares

Soluciones

Ampliación de árboles binarios

Soluciones

Clases de equivalencia

Soluciones

La carrera de Collatz

Soluciones

Árbol de subconjuntos

Soluciones

Entradas recientes

Buscar

Correo electrónico