Definir la lista
numerosConDigitosPrimos :: [Integer]
cuyos elementos son los números con todos sus dígitos primos. Por ejemplo,
λ> take 22 numerosConDigitosPrimos [2,3,5,7,22,23,25,27,32,33,35,37,52,53,55,57,72,73,75,77,222,223] λ> numerosConDigitosPrimos !! (10^7) 322732232572
Los primeros números de Fibonacci son
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
tales que los dos primeros son iguales a 1 y los siguientes se obtienen sumando los dos anteriores.
El teorema de Zeckendorf establece que entero positivo n se puede representar, de manera única, como la suma de números de Fibonacci no consecutivos decrecientes. Dicha suma se llama la representación de Zeckendorf de n. Por ejemplo, la representación de Zeckendorf de 100 es
100 = 89 + 8 + 3
Hay otras formas de representar 100 como sumas de números de Fibonacci; por ejemplo,
100 = 89 + 8 + 2 + 1 100 = 55 + 34 + 8 + 3
pero no son representaciones de Zeckendorf porque 1 y 2 son números de Fibonacci consecutivos, al igual que 34 y 55.
Definir la función
zeckendorf :: Integer -> [Integer]
tal que (zeckendorf n) es la representación de Zeckendorf de n. Por ejemplo,
zeckendorf 100 == [89,8,3] zeckendorf 200 == [144,55,1] zeckendorf 300 == [233,55,8,3,1] length (zeckendorf (10^50000)) == 66097
Los números triangulares se forman como sigue
* * * * * * * * * * 1 3 6
La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 5 primeros números triangulares son
1 = 1 3 = 1 + 2 6 = 1 + 2 + 3 10 = 1 + 2 + 3 + 4 15 = 1 + 2 + 3 + 4 + 5
Definir la función
descomposicionesTriangulares :: Int -> [(Int, Int, Int)]
tal que descomposicionesTriangulares n es la lista de las ternas correspondientes a las descomposiciones de n en tres sumandos, como máximo, formados por números triangulares. Por ejemplo,
λ> descomposicionesTriangulares3 4 [] λ> descomposicionesTriangulares3 5 [(1,1,3)] λ> descomposicionesTriangulares3 12 [(1,1,10),(3,3,6)] λ> descomposicionesTriangulares3 30 [(1,1,28),(3,6,21),(10,10,10)] λ> descomposicionesTriangulares3 61 [(1,15,45),(3,3,55),(6,10,45),(10,15,36)] λ> descomposicionesTriangulares3 52 [(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)] λ> descomposicionesTriangulares3 82 [(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)] λ> length (descomposicionesTriangulares3 (5*10^5)) 124
Dos números enteros positivos son primos relativos si no tienen ningún factor primo en común; es decir, si 1 es su único divisor común. Por ejemplo, 6 y 35 son primos entre sí, pero 6 y 27 no lo son porque ambos son divisibles por 3.
Definir la función
primosRelativos :: [Int] -> Bool
tal que primosRelativos xs se verifica si los elementos de xs son primos relativos dos a dos. Por ejemplo,
primosRelativos [6,35] == True primosRelativos [6,27] == False primosRelativos [2,3,4] == False primosRelativos [6,35,11] == True primosRelativos [6,35,11,221] == True primosRelativos [6,35,11,231] == False
La diferencia simétrica de dos conjuntos es el conjunto cuyos elementos son aquellos que pertenecen a alguno de los conjuntos iniciales, sin pertenecer a ambos a la vez. Por ejemplo, la diferencia simétrica de {2,5,3} y {4,2,3,7} es {5,4,7}.
Definir la función
diferenciaSimetrica :: Ord a => [a] -> [a] -> [a]
tal que diferenciaSimetrica xs ys es la diferencia simétrica de xs e ys. Por ejemplo,
diferenciaSimetrica [2,5,3] [4,2,3,7] == [4,5,7] diferenciaSimetrica [2,5,3] [5,2,3] == [] diferenciaSimetrica [2,5,2] [4,2,3,7] == [3,4,5,7] diferenciaSimetrica [2,5,2] [4,2,4,7] == [4,5,7] diferenciaSimetrica [2,5,2,4] [4,2,4,7] == [5,7]
Una matriz de Toeplitz es una matriz cuadrada que es constante a lo largo de las diagonales paralelas a la diagonal principal. Por ejemplo,
|2 5 1 6| |2 5 1 6| |4 2 5 1| |4 2 6 1| |7 4 2 5| |7 4 2 5| |9 7 4 2| |9 7 4 2|
la primera es una matriz de Toeplitz y la segunda no lo es.
Las anteriores matrices se pueden definir por
ej1, ej2 :: Array (Int,Int) Int ej1 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,5,1,7,4,2,5,9,7,4,2] ej2 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,6,1,7,4,2,5,9,7,4,2]
Definir la función
esToeplitz :: Eq a => Array (Int,Int) a -> Bool
tal que esToeplitz p se verifica si la matriz p es de Toeplitz. Por ejemplo,
esToeplitz ej1 == True esToeplitz ej2 == False
La lista de las diagonales principales de la matriz
1 2 3 4 5 6 7 8 9 10 11 12
es
[[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]
Definir la función
diagonalesPrincipales :: Array (Int,Int) a -> [[a]]
tal que diagonalesPrincipales p es la lista de las diagonales principales de p. Por ejemplo,
λ> diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12]) [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]
Las posiciones de una matriz con 3 filas y 4 columnas son
(1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4)
La posiciones de sus 6 diagonales principales son
[(3,1)] [(2,1),(3,2)] [(1,1),(2,2),(3,3)] [(1,2),(2,3),(3,4)] [(1,3),(2,4)] [(1,4)]
Definir la función
posicionesDiagonalesPrincipales :: Int -> Int -> [[(Int, Int)]]
tal que posicionesdiagonalesprincipales m n es la lista de las posiciones de las diagonales principales de una matriz con m filas y n columnas. Por ejemplo,
λ> mapM_ print (posicionesDiagonalesPrincipales 3 4) [(3,1)] [(2,1),(3,2)] [(1,1),(2,2),(3,3)] [(1,2),(2,3),(3,4)] [(1,3),(2,4)] [(1,4)] λ> mapM_ print (posicionesDiagonalesPrincipales 4 4) [(4,1)] [(3,1),(4,2)] [(2,1),(3,2),(4,3)] [(1,1),(2,2),(3,3),(4,4)] [(1,2),(2,3),(3,4)] [(1,3),(2,4)] [(1,4)] λ> mapM_ print (posicionesDiagonalesPrincipales 4 3) [(4,1)] [(3,1),(4,2)] [(2,1),(3,2),(4,3)] [(1,1),(2,2),(3,3)] [(1,2),(2,3)] [(1,3)]
Los números triangulares se forman como sigue
* * * * * * * * * * 1 3 6
La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 5 primeros números triangulares son
1 = 1 3 = 1 + 2 6 = 1 + 2 + 3 10 = 1 + 2 + 3 + 4 15 = 1 + 2 + 3 + 4 + 5
Definir la función
triangularesConCifras :: Int -> [Integer]
tal que triangularesConCifras n es la lista de los números triangulares con n cifras distintas. Por ejemplo,
take 6 (triangularesConCifras 1) == [1,3,6,55,66,666] take 6 (triangularesConCifras 2) == [10,15,21,28,36,45] take 6 (triangularesConCifras 3) == [105,120,136,153,190,210] take 5 (triangularesConCifras 4) == [1035,1275,1326,1378,1485] take 2 (triangularesConCifras 10) == [1062489753,1239845706]
Las ternas de números naturales se pueden ordenar como sigue
(0,0,0), (0,0,1),(0,1,0),(1,0,0), (0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0),(2,0,0), (0,0,3),(0,1,2),(0,2,1),(0,3,0),(1,0,2),(1,1,1),(1,2,0),(2,0,1),... ...
Definir la función
posicion :: (Int,Int,Int) -> Int
tal que posicion (x,y,z) es la posición de la terna de números naturales (x,y,z) en la ordenación anterior. Por ejemplo,
posicion (0,1,0) == 2 posicion (0,0,2) == 4 posicion (0,1,1) == 5
Comprobar con QuickCheck que
Definir la función
primosEquidistantes :: Integer -> [(Integer,Integer)]
tal que primosEquidistantes k es la lista de los pares de primos cuya diferencia es k. Por ejemplo,
take 3 (primosEquidistantes 2) == [(3,5),(5,7),(11,13)] take 3 (primosEquidistantes 4) == [(7,11),(13,17),(19,23)] take 3 (primosEquidistantes 6) == [(23,29),(31,37),(47,53)] take 3 (primosEquidistantes 8) == [(89,97),(359,367),(389,397)] primosEquidistantes 4 !! (10^5) == (18467047,18467051)
Dos números amigos son dos números positivos distintos tales que la suma de los divisores propios de cada uno es igual al otro. Los divisores propios de un número incluyen la unidad pero no al propio número. Por ejemplo, divisores propios de 220 son 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 y 110. La suma de estos números equivale a 284. A su vez, los divisores propios de 284 son 1, 2, 4, 71 y 142. Su suma equivale a 220. Por tanto, 220 y 284 son amigos.
Definir la función
amigos :: Integer -> Integer -> Bool
tal que amigos x y se verifica si los números x e y son amigos. Por ejemplo,
amigos 220 284 == True amigos 220 23 == False amigos 9967523980 12890541236 == True
Los triángulos se pueden representar mediante listas de listas. Por ejemplo, el triángulo
3 7 4 2 4 6 8 5 9 3
se representa por
[[3],[7,4],[2,4,6],[8,5,9,3]]
Definir la función
maximaSuma :: [[Integer]] -> Integer
tal que (maximaSuma xss) es el máximo de las sumas de los de los caminos en el triángulo xss donde los caminos comienzan en el elemento de la primera fila, en cada paso se mueve a uno de sus dos elementos adyacentes en la fila siguiente y terminan en la última fila. Por ejemplo,
maximaSuma [[3],[7,4]] == 10 maximaSuma [[3],[7,4],[2,4,6]] == 14 maximaSuma [[3],[7,4],[2,4,6],[8,5,9,3]] == 23 maximaSuma [[n..n+n] | n <- [0..100]] == 10100 maximaSuma [[n..n+n] | n <- [0..1000]] == 1001000 maximaSuma [[n..n+n] | n <- [0..2000]] == 4002000 maximaSuma [[n..n+n] | n <- [0..3000]] == 9003000 maximaSuma [[n..n+n] | n <- [0..4000]] == 16004000
Los triángulos se pueden representar mediante listas de listas. Por ejemplo, el triángulo
3 7 4 2 4 6 8 5 9 3
se representa por
[[3],[7,4],[2,4,6],[8,5,9,3]]
Definir la función
caminos :: [[a]] -> [[a]]
tal que (caminos xss) es la lista de los caminos en el triángulo, donde los caminos comienzan en el elemento de la primera fila, en cada paso se mueve a uno de sus dos elementos adyacentes en la fila siguiente y terminan en la última fila. Por ejemplo,
λ> caminos [[3],[7,4]] [[3,7],[3,4]] λ> caminos [[3],[7,4],[2,4,6]] [[3,7,2],[3,7,4],[3,4,4],[3,4,6]] λ> caminos [[3],[7,4],[2,4,6],[8,5,9,3]] [[3,7,2,8],[3,7,2,5],[3,7,4,5],[3,7,4,9], [3,4,4,5],[3,4,4,9],[3,4,6,9],[3,4,6,3]]
Un máximo local de una lista es un elemento de la lista que es mayor que su predecesor y que su sucesor en la lista. Por ejemplo, 5 es un máximo local de [3,2,5,3,7,7,1,6,2] ya que es mayor que 2 (su predecesor) y que 3 (su sucesor).
Definir la función
maximosLocales :: Ord a => [a] -> [a]
tal que (maximosLocales xs) es la lista de los máximos locales de la lista xs. Por ejemplo,
maximosLocales [3,2,5,3,7,7,1,6,2] == [5,6] maximosLocales [1..100] == [] maximosLocales "adbpmqexyz" == "dpq"
Se considera la siguiente operación, aplicable a cualquier número entero positivo:
Dado un número cualquiera, podemos calcular su órbita; es decir, las imágenes sucesivas al iterar la función. Por ejemplo, la órbita de 13 es
13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...
Si observamos este ejemplo, la órbita de 13 es periódica, es decir, se repite indefinidamente a partir de un momento dado). La conjetura de Collatz dice que siempre alcanzaremos el 1 para cualquier número con el que comencemos. Ejemplos:
Definir la función
mayoresGeneradores :: Integer -> [Integer]
tal que (mayoresGeneradores n) es la lista de los números menores o iguales que n cuyas órbitas de Collatz son las de mayor longitud. Por ejemplo,
mayoresGeneradores 20 == [18,19] mayoresGeneradores (10^6) == [837799]
Definir la función
exponente :: Integer -> Integer -> Int
tal que (exponente x n) es el exponente de x en la factorización prima de n (se supone que x > 1 y n > 0). Por ejemplo,
exponente 2 24 == 3 exponente 3 24 == 1 exponente 6 24 == 0 exponente 7 24 == 0
Definir la función
esPotenciaDe4 :: Integral a => a -> Bool
tal que (esPotenciaDe4 n) se verifica si n es una potencia de 4. Por ejemplo,
esPotenciaDe4 16 == True esPotenciaDe4 17 == False esPotenciaDe4 (4^(4*10^5)) == True esPotenciaDe4 (1 + 4^(4*10^5)) == False
Las matrices se pueden representar como lista de listas de la misma longitud, donde cada uno de sus elementos representa una fila de la matriz.
Definir la función
productoDiagonalPrincipal :: Num a => [[a]] -> a
tal que (productoDiagonalPrincipal xss) es el producto de los elementos de la diagonal principal de la matriz cuadrada xss. Por ejemplo,
productoDiagonal [[3,5,2],[4,7,1],[6,9,8]] == 168 productoDiagonal (replicate 5 [1..5]) == 120 length (show (productoDiagonal (replicate 30000 [1..30000]))) == 121288
La reiteración de la suma de los elementos consecutivos de la lista [1,5,3] es 14 como se explica en el siguiente diagrama
1 + 5 = 6
\
==> 14
/
5 + 3 = 8
y la de la lista [1,5,3,4] es 29 como se explica en el siguiente diagrama
1 + 5 = 6
\
==> 14
/ \
5 + 3 = 8 ==> 29
\ /
==> 15
/
3 + 4 = 7
Definir la función
sumaReiterada :: Num a => [a] -> a
tal que (sumaReiterada xs) es la suma reiterada de los elementos consecutivos de la lista no vacía xs. Por ejemplo,
sumaReiterada [1,5,3] == 14 sumaReiterada [1,5,3,4] == 29
Se condidera el siguiente triángulo de números impares
1
3 5
7 9 11
13 15 17 19
21 23 25 27 29
...
Definir la función
sumaFilaTrianguloImpares :: Integer -> Integer
tal que (sumaFilaTrianguloImpares n) es la suma de la n-ésima fila del triángulo de los números impares. Por ejemplo,
sumaFilaTrianguloImpares 1 == 1 sumaFilaTrianguloImpares 2 == 8 length (show (sumaFilaTrianguloImpares (10^500))) == 1501 length (show (sumaFilaTrianguloImpares (10^5000))) == 15001 length (show (sumaFilaTrianguloImpares (10^50000))) == 150001
Definir la función
duplicaElementos :: [a] -> [a]
tal que (duplicaElementos xs) es la lista obtenida duplicando cada elemento de xs. Por ejemplo,
duplicaElementos [3,2,5] == [3,3,2,2,5,5] duplicaElementos "Haskell" == "HHaasskkeellll"
El sistema factorádico es un sistema numérico basado en factoriales en el que el n-ésimo dígito, empezando desde la derecha, debe ser multiplicado por n! Por ejemplo, el número "341010" en el sistema factorádico es 463 en el sistema decimal ya que
3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0! = 463
En este sistema numérico, el dígito de más a la derecha es siempre 0, el segundo 0 o 1, el tercero 0,1 o 2 y así sucesivamente.
Con los dígitos del 0 al 9 el mayor número que podemos codificar es el 10!-1 = 3628799. En cambio, si lo ampliamos con las letras A a Z podemos codificar hasta 36!-1 = 37199332678990121746799944815083519999999910.
Definir las funciones
factoradicoAdecimal :: String -> Integer decimalAfactoradico :: Integer -> String
tales que
λ> factoradicoAdecimal "341010" 463 λ> factoradicoAdecimal "2441000" 2022 λ> factoradicoAdecimal "A0000000000" 36288000 λ> map factoradicoAdecimal ["10","100","110","200","210","1000","1010","1100","1110","1200"] [1,2,3,4,5,6,7,8,9,10] λ> factoradicoAdecimal "3KXWVUTSRQPONMLKJIHGFEDCBA9876543210" 37199332678990121746799944815083519999999
λ> decimalAfactoradico 463 "341010" λ> decimalAfactoradico 2022 "2441000" λ> decimalAfactoradico 36288000 "A0000000000" λ> map decimalAfactoradico [1..10] ["10","100","110","200","210","1000","1010","1100","1110","1200"] λ> decimalAfactoradico 37199332678990121746799944815083519999999 "3KXWVUTSRQPONMLKJIHGFEDCBA9876543210"
Comprobar con QuickCheck que, para cualquier entero positivo n,
factoradicoAdecimal (decimalAfactoradico n) == n
Definir la función
sumaCadenas :: String -> String -> String
tal que (sumaCadenas xs ys) es la cadena formada por el número entero que es la suma de los números enteros cuyas cadenas que lo representan son xs e ys; además, se supone que la cadena vacía representa al cero. Por ejemplo,
sumaCadenas "2" "6" == "8" sumaCadenas "14" "2" == "16" sumaCadenas "14" "-5" == "9" sumaCadenas "-14" "-5" == "-19" sumaCadenas "5" "-5" == "0" sumaCadenas "" "5" == "5" sumaCadenas "6" "" == "6" sumaCadenas "" "" == "0"
Definir la función
cuadradoCercano :: Integer -> Integer
tal que cuadradoCercano n es el número cuadrado más cercano a n, donde n es un entero positivo. Por ejemplo,
cuadradoCercano 2 == 1 cuadradoCercano 6 == 4 cuadradoCercano 8 == 9 cuadradoCercano (10^46) == 10000000000000000000000000000000000000000000000
Un primo cubano es un número primo que se puede escribir como diferencia de dos cubos consecutivos. Por ejemplo, el 61 es un primo cubano porque es primo y 61 = 5³-4³.
Definir la sucesión
cubanos :: [Integer]
tal que sus elementos son los números cubanos. Por ejemplo,
λ> take 15 cubanos [7,19,37,61,127,271,331,397,547,631,919,1657,1801,1951,2269]
Definir la función
cerosDelFactorial :: Integer -> Integer
tal que cerosDelFactorial n es el número de ceros en que termina el factorial de n. Por ejemplo,
cerosDelFactorial 24 == 4 cerosDelFactorial 25 == 6 length (show (cerosDelFactorial (10^70000))) == 70000
La indicatriz de Euler (también función φ de Euler) es una función importante en teoría de números. Si n es un entero positivo, entonces φ(n) se define como el número de enteros positivos menores o iguales a n y coprimos con n. Por ejemplo, φ(36) = 12 ya que los números menores o iguales a 36 y coprimos con 36 son doce: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, y 35.
Definir la función
phi :: Integer -> Integer
tal que phi n es igual a φ(n). Por ejemplo,
phi 36 == 12 map phi [10..20] == [4,10,4,12,6,8,8,16,6,18,8] phi (3^10^5) `mod` (10^9) == 681333334 length (show (phi (10^(10^5)))) == 100000
Comprobar con QuickCheck que, para todo n > 0, φ(10^n) tiene n dígitos.
El hueco de un número primo p es la distancia entre p y primo siguiente de p. Por ejemplo, el hueco de 7 es 4 porque el primo siguiente de 7 es 11 y 4 = 11-7. Los huecos de los primeros números son
Primo Hueco
2 1
3 2
7 4
11 2
El hueco de un número primo p es maximal si es mayor que los huecos de todos los números menores que p. Por ejemplo, 4 es un hueco maximal de 7 ya que los huecos de los primos menores que 7 son 1 y 2 y ambos son menores que 4. La tabla de los primeros huecos maximales es
Primo Hueco
2 1
3 2
7 4
23 6
89 8
113 14
523 18
887 20
Definir la sucesión
primosYhuecosMaximales :: [(Integer,Integer)]
cuyos elementos son los números primos con huecos maximales junto son sus huecos. Por ejemplo,
λ> take 8 primosYhuecosMaximales [(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)] λ> primosYhuecosMaximales !! 20 (2010733,148)
La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario. Los primeros términos de la serie son
[0] [0,1] [0,1,1,0] [0,1,1,0,1,0,0,1] [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]
De esta forma se va formando una sucesión
0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,...
que se conoce como la sucesión de Thue-Morse.
Definir la sucesión
sucThueMorse :: [Int]
cuyos elementos son los de la sucesión de Thue-Morse. Por ejemplo,
λ> take 30 sucThueMorse [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0] λ> map (sucThueMorse4 !!) [1234567..1234596] [1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0] λ> map (sucThueMorse4 !!) [4000000..4000030] [1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1]
Comprobar con QuickCheck que si s(n) representa el término n-ésimo de la sucesión de Thue-Morse, entonces
s(2n) = s(n) s(2n+1) = 1 - s(n)
La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario (es decir, la lista obtenida cambiando el 0 por 1 y el 1 por 0). Los primeros términos de la serie son
[0] [0,1] [0,1,1,0] [0,1,1,0,1,0,0,1] [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]
Definir la lista
serieThueMorse :: [[Int]]
tal que sus elementos son los términos de la serie de Thue-Morse. Por ejemplo,
λ> take 4 serieThueMorse [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]
Definir la función
representaciones :: Integer -> [(Integer,Integer)]
tal que representaciones n es la lista de pares de números naturales (x,y) tales que n = x² + y². Por ejemplo.
representaciones 20 == [(2,4)] representaciones 25 == [(0,5),(3,4)] representaciones 325 == [(1,18),(6,17),(10,15)] length (representaciones (10^14)) == 8
Comprobar con QuickCheck que un número natural n se puede representar como suma de dos cuadrados si, y sólo si, en la factorización prima de n todos los exponentes de sus factores primos congruentes con 3 módulo 4 son pares.
Definir la sucesión
sumasDeDosPrimos :: [Integer]
cuyos elementos son los números que se pueden escribir como suma de dos números primos. Por ejemplo,
λ> take 23 sumasDeDosPrimos [4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31] λ> sumasDeDosPrimos !! (5*10^5) 862878
Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, ...
Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, ...
Definir la función
factorizacionesH :: Integer -> [[Integer]]
tal que factorizacionesH n es la listas de primos de Hilbert cuyo producto es el número de Hilbert n. Por ejemplo,
factorizacionesH 25 == [[5,5]] factorizacionesH 45 == [[5,9]] factorizacionesH 441 == [[9,49],[21,21]] factorizacionesH 80109 == [[9,9,989],[9,69,129]]
Comprobar con QuickCheck que todos los números de Hilbert son factorizables como producto de primos de Hilbert (aunque la factorización, como para el 441, puede no ser única).
Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97, ...
Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, 141, 149, 157, 161, 173, 177, 181, 193, 197, ...
Definir la sucesión
primosH :: [Integer]
tal que sus elementos son los primos de Hilbert. Por ejemplo,
take 15 primosH == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73] primosH !! (3*10^4) == 313661
El 25 de diciembre de 1640, en una carta a Mersenne, Fermat demostró la conjetura de Girard: todo primo de la forma 4n+1 puede expresarse de manera única como suma de dos cuadrados. Por eso es conocido como el teorema de Navidad de Fermat.
Definir las funciones
representaciones :: Integer -> [(Integer,Integer)] primosImparesConRepresentacionUnica :: [Integer] primos4nM1 :: [Integer]
tales que
representaciones n es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2 con x <= y. Por ejemplo. representaciones 20 == [(2,4)]
representaciones 25 == [(0,5),(3,4)]
representaciones 325 == [(1,18),(6,17),(10,15)]
representaciones 100000147984 == [(0,316228)]
length (representaciones (10^10)) == 6
length (representaciones (4*10^12)) == 7
primosImparesConRepresentacionUnica es la lista de los números primos impares que se pueden escribir exactamente de una manera como suma de cuadrados de pares de números naturales (x,y) con x <= y. Por ejemplo, λ> take 20 primosImparesConRepresentacionUnica
[5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]
primos4nM1 es la lista de los números primos que se pueden escribir como uno más un múltiplo de 4 (es decir, que son congruentes con 1 módulo 4). Por ejemplo, λ> take 20 primos4nM1
[5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]
El teorema de Navidad de Fermat afirma que un número primo impar p se puede escribir exactamente de una manera como suma de dos cuadrados de números naturales p = x² + y² (con x <= y) si, y sólo si, p se puede escribir como uno más un múltiplo de 4 (es decir, que es congruente con 1 módulo 4).
Comprobar con QuickCheck el teorema de Navidad de Fermat; es decir, que para todo número n, los n-ésimos elementos de primosImparesConRepresentacionUnica y de primos4nM1 son iguales.
Los números de Fibonacci se definen mediante las ecuaciones
F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2), si n > 1
Los primeros números de Fibonacci son
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
Una generalización de los anteriores son los números de Pentanacci definidos por las siguientes ecuaciones
P(0) = 0 P(1) = 1 P(2) = 1 P(3) = 2 P(4) = 4 P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4
Los primeros números de Pentanacci son
0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...
Definir las funciones
pentanacci :: Integer -> Integer pentanaccis :: [Integer]
tales que
pentanacci n es el n-ésimo número de Pentanacci. Por ejemplo,λ> pentanacci 14 3525 λ> pentanacci (10^5) `mod` 10^30 482929150584077921552549215816 λ> length (show (pentanacci (10^5))) 29357
pentanaccis es la lista de los números de Pentanacci. Por ejemplo, λ> take 15 pentanacci
[0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]
Un sistema de ecuaciones lineales \(Ax = b\) es triangular inferior si todos los elementos de la matriz \(A\) que están por encima de la diagonal principal son nulos; es decir, es de la forma \begin{align} &a_{1 1}x_1 &= b_1 \newline &a_{2 1}x_1 + a_{2 2}x_2 &= b_2 \newline &a_{3 1}x_1 + a_{3 2}x_2 + a_{3 3}x_3 &= b_3 \newline &... & \newline &a_{n 1}x_1 + a_{n 2}x_2 + a_{n 3}x_3 +...+ a_{n n}x_n &= b_n \end{align}
El sistema es compatible si, y sólo si, el producto de los elementos de la diagonal principal es distinto de cero. En este caso, la solución se puede calcular mediante el algoritmo de bajada: \begin{align} x_1 &= \frac{b_1}{a_{1 1}} \newline x_2 &= \frac{b_2 - a_{2 1}x_1}{a_{2 2}} \newline x_3 &= \frac{b_3 - a_{3 1}x_1 - a_{3 2}x_2}{a_{3 3}} \newline ... \newline x_n &= \frac{b_n - a_{n 1}x_1 - a_{n 2}x_2 - ... - a_{n,n-1}x_{n-1}}{a_{n n}} \end{align}
Definir la función
bajada :: Matrix Double -> Matrix Double -> Matrix Double
tal que bajada a b es la solución, mediante el algoritmo de bajada, del sistema compatible triangular superior ax = b. Por ejemplo,
λ> let a = fromLists [[2,0,0],[3,1,0],[4,2,5.0]] λ> let b = fromLists [[3],[6.5],[10]] λ> bajada a b ( 1.5 ) ( 2.0 ) ( 0.0 )
Es decir, la solución del sistema \begin{align} 2x &= 3 \newline 3x + y &= 6.5 \newline 4x + 2y + 5z &= 10 \end{align} es \(x=1.5\), \(y=2\) y \(z=0\).
La integral definida de una función f entre los límites a y b puede calcularse mediante la regla del rectángulo (ver en https://en.wikipedia.org/wiki/Riemann_sum) usando la fórmula \[ h(f(a+\frac{h}{2}) + f(a+h+\frac{h}{2}) + f(a+2h+\frac{h}{2}) + ... + f(a+nh+\frac{h}{2}))\] con \(a+nh+\frac{h}{2} \leq b < a+(n+1)h+\frac{h}{2}\) y usando valores pequeños para \(h\).
Definir la función
integral :: (Fractional a, Ord a) => a -> a -> (a -> a) -> a -> a
tal que integral a b f h es el valor de dicha expresión. Por ejemplo, el cálculo de la integral de (f(x) = x^3) entre 0 y 1, con paso 0.01, es
integral 0 1 (^3) 0.01 == 0.24998750000000042
Otros ejemplos son
integral 0 1 (^4) 0.01 == 0.19998333362500048 integral 0 1 (\x -> 3*x^2 + 4*x^3) 0.01 == 1.9999250000000026 log 2 - integral 1 2 (\x -> 1/x) 0.01 == 3.124931644782336e-6 pi - 4 * integral 0 1 (\x -> 1/(x^2+1)) 0.01 == -8.333333331389525e-6
Definir la función
raizEnt :: Integer -> Integer -> Integer
tal que raizEnt x n es la raíz entera n-ésima de x; es decir, el mayor número entero y tal que \(y^n \leq x\). Por ejemplo,
raizEnt 8 3 == 2 raizEnt 9 3 == 2 raizEnt 26 3 == 2 raizEnt 27 3 == 3 raizEnt (10^50) 2 == 10000000000000000000000000
Comprobar con QuickCheck que para todo número natural n,
raizEnt (10^(2*n)) 2 == 10^n
El método de bisección para calcular una raíz de una función en el intervalo [a,b] se basa en el teorema de Bolzano:
Si f(x) es una función continua en el intervalo \([a, b]\), y si, además, en los extremos del intervalo la función \(f\) toma valores de signo opuesto \((f(a)f(b) < 0)\), entonces existe al menos un valor \(c\) en \((a, b)\) para el que \(f(c) = 0\)".
El método para calcular una raíz de la función \(f\) en el intervalo \([a,b]\) con un error menor que \(e\) consiste en tomar el punto medio del intervalo \(c = \frac{a+b}{2}\) y considerar los siguientes casos:
Definir la función
biseccion :: (Double -> Double) -> Double -> Double -> Double -> Double
tal que biseccion f a b e es una aproximación del punto del intervalo [a,b] en el que se anula la función f, con un error menor que e, calculada mediante el método de la bisección. Por ejemplo,
biseccion (\x -> x^2 - 3) 0 5 0.01 == 1.7333984375 biseccion (\x -> x^3 - x - 2) 0 4 0.01 == 1.521484375 biseccion cos 0 2 0.01 == 1.5625 biseccion (\x -> log (50-x) - 4) (-10) 3 0.01 == -5.125
Definir la función
limite :: (Double -> Double) -> Double -> Double
tal que limite f a es el valor de f en el primer término x tal que, para todo y entre x+1 y x+100, el valor absoluto de la diferencia entre f(y) y f(x) es menor que a. Por ejemplo,
limite (\n -> (2*n+1)/(n+5)) 0.001 == 1.9900110987791344 limite (\n -> (1+1/n)**n) 0.001 == 2.714072874546881
Definir, usando puntoCero, la función
inversa :: (Double -> Double) -> Double -> Double
tal que inversa g x es el valor de la inversa de g en x. Por ejemplo,
inversa (^2) 9 == 3.000000002941184
Definir, usando inversa, las funciones raizCuadrada, raizCubica, arcoseno y arcocoseno que calculen la raíz cuadrada, la raíz cúbica, el arco seno y el arco coseno, respectivamente. Por ejemplo,
raizCuadrada 9 == 3.000000002941184 raizCubica 27 == 3.0000000000196048 arcoseno 1 == 1.5665489428306574 arcocoseno 0 == 1.5707963267949576
Los ceros de una función pueden calcularse mediante el método de Newton basándose en las siguientes propiedades:
Definir la función
puntoCero :: (Double -> Double) -> Double
tal que puntoCero f es un cero de la función f calculado usando la propiedad anterior. Por ejemplo,
puntoCero cos == 1.5707963267949576
El método de Herón para calcular la raíz cuadrada de un número se basa en las siguientes propiedades:
Definir la función
raiz :: Double -> Double
tal que raiz x es la raíz cuadrada de x calculada usando la propiedad anterior con una aproximación de 0.00001 y tomando como valor inicial 1. Por ejemplo,
raiz 9 == 3.000000001396984
Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 )
moviéndose en cada paso una casilla hacia la derecha o hacia abajo, son los siguientes:
[1,6,11,2,8,9] [1,6,11,3,8,9] [1,6,12,3,8,9] [1,7,12,3,8,9] [1,6,11,3,4,9] [1,6,12,3,4,9] [1,7,12,3,4,9] [1,6,12,8,4,9] [1,7,12,8,4,9] [1,7, 3,8,4,9]
La suma de los caminos son 37, 38, 39, 40, 34, 35, 36, 40, 41 y 32, respectivamente. El camino de máxima suma es el penúltimo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.
Definir la función
caminoMaxSuma :: Matrix Int -> [Int]
tal que caminoMaxSuma m es un camino de máxima suma en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,
λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) [1,7,12,8,4,9] λ> sum (caminoMaxSuma (fromList 500 500 [1..])) 187001249
Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 )
moviéndose en cada paso una casilla hacia la derecha o hacia abajo, son los siguientes:
[1,6,11,2,8,9] [1,6,11,3,8,9] [1,6,12,3,8,9] [1,7,12,3,8,9] [1,6,11,3,4,9] [1,6,12,3,4,9] [1,7,12,3,4,9] [1,6,12,8,4,9] [1,7,12,8,4,9] [1,7, 3,8,4,9]
La suma de los caminos son 37, 38, 39, 40, 34, 35, 36, 40, 41 y 32, respectivamente. El camino de máxima suma es el penúltimo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.
Definir la función
maximaSuma :: Matrix Int -> Int
tal que maximaSuma m es el máximo de las sumas de los caminos en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia a derecha. Por ejemplo,
λ> maximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) 41 λ> maximaSuma (fromList 800 800 [1..]) 766721999
Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 )
moviéndose en cada paso una casilla hacia la derecha o abajo, son los siguientes:
[1,6,11,2,8,9] [1,6,11,3,8,9] [1,6,12,3,8,9] [1,7,12,3,8,9] [1,6,11,3,4,9] [1,6,12,3,4,9] [1,7,12,3,4,9] [1,6,12,8,4,9] [1,7,12,8,4,9] [1,7, 3,8,4,9]
Definir la función
caminos :: Matrix Int -> [[Int]]
tal que caminos m es la lista de los caminos en la matriz m desde extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia la derecha o abajo. Por ejemplo,
λ> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
[[1,6,11,2,8,9],
[1,6,11,3,8,9],
[1,6,12,3,8,9],
[1,7,12,3,8,9],
[1,6,11,3,4,9],
[1,6,12,3,4,9],
[1,7,12,3,4,9],
[1,6,12,8,4,9],
[1,7,12,8,4,9],
[1,7, 3,8,4,9]]
λ> length (caminos (fromList 12 12 [1..]))
705432
Se considera una retícula con sus posiciones numeradas, desde el vértice superior izquierdo, hacia la derecha y hacia abajo. Por ejemplo, la retícula de dimensión 3x4 se numera como sigue:
|-------+-------+-------+-------| | (1,1) | (1,2) | (1,3) | (1,4) | | (2,1) | (2,2) | (2,3) | (2,4) | | (3,1) | (3,2) | (3,3) | (3,4) | |-------+-------+-------+-------|
Definir la función
caminos :: (Int,Int) -> [[(Int,Int)]]
tal que caminos (m,n) es la lista de los caminos en la retícula de dimensión mxn desde (1,1) hasta (m,n). Por ejemplo,
λ> caminos (2,3)
[[(1,1),(1,2),(1,3),(2,3)],
[(1,1),(1,2),(2,2),(2,3)],
[(1,1),(2,1),(2,2),(2,3)]]
λ> mapM_ print (caminos (3,4))
[(1,1),(1,2),(1,3),(1,4),(2,4),(3,4)]
[(1,1),(1,2),(1,3),(2,3),(2,4),(3,4)]
[(1,1),(1,2),(2,2),(2,3),(2,4),(3,4)]
[(1,1),(2,1),(2,2),(2,3),(2,4),(3,4)]
[(1,1),(1,2),(1,3),(2,3),(3,3),(3,4)]
[(1,1),(1,2),(2,2),(2,3),(3,3),(3,4)]
[(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)]
[(1,1),(1,2),(2,2),(3,2),(3,3),(3,4)]
[(1,1),(2,1),(2,2),(3,2),(3,3),(3,4)]
[(1,1),(2,1),(3,1),(3,2),(3,3),(3,4)]
La distancia de Levenshtein (o distancia de edición) es el mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. Las operaciones de edición que se pueden hacer son:
Por ejemplo, la distancia de Levenshtein entre "casa" y "calle" es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro:
"casa" --> "cala" (sustitución de 's' por 'l') "cala" --> "calla" (inserción de 'l' entre 'l' y 'a') "calla" --> "calle" (sustitución de 'a' por 'e')
Definir la función
levenshtein :: String -> String -> Int
tal que levenshtein xs ys es la distancia de Levenshtein entre xs e ys. Por ejemplo,
levenshtein "casa" "calle" == 3 levenshtein "calle" "casa" == 3 levenshtein "casa" "casa" == 0 levenshtein "ana" "maria" == 3 levenshtein "agua" "manantial" == 7
Si a una secuencia X de elementos (pongamos por ejemplo, le quitamos algunos de ellos y dejamos los que quedan en el orden en el que aparecían originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, "aaoa" es una subsecuencia de la secuencia "amapola".
El término también se aplica cuando quitamos todos los elementos (es decir, la secuencia vacía es siempre subsecuencia de cualquier secuencia) o cuando no quitamos ninguno (lo que significa que cualquier secuencia es siempre subsecuencia de sí misma).
Dadas dos secuencias X e Y, decimos que Z es una subsecuencia de X e Y si Z es subsecuencia de X y de Y. Por ejemplo, si X = "amapola" e Y = "matamoscas", la secuencia "aaoa" es una de las subsecuencias comunes de X e Y más larga, con longitud 4, ya que no hay ninguna subsecuencia común a X e Y de longitud mayor que 4. También son subsecuencias comunes de longitud 4 "maoa" o "amoa".
Definir la función
scm :: Eq a => [a] -> [a] -> [a]
tal que scm xs ys es una de las subsecuencias comunes de longitud máxima de xs e ys. Por ejemplo,
scm "amapola" "matamoscas" == "amoa" scm "atamos" "matamoscas" == "atamos" scm "aaa" "bbbb" == ""
Si a una secuencia X de elementos (pongamos por ejemplo, caracteres) le quitamos algunos de ellos y dejamos los que quedan en el orden en el que aparecían originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, "aaoa" es una subsecuencia de la secuencia "amapola".
El término también se aplica cuando quitamos todos los elementos (es decir, la secuencia vacía es siempre subsecuencia de cualquier secuencia) o cuando no quitamos ninguno (lo que significa que cualquier secuencia es siempre subsecuencia de sí misma).
Dadas dos secuencias X e Y, decimos que Z es una subsecuencia común de X e Y si Z es subsecuencia de X y de Y. Por ejemplo, si X = "amapola" e Y = "matamoscas", la secuencia "aaoa" es una de las subsecuencias comunes de X e Y más larga, con longitud 4, ya que no hay ninguna subsecuencia común a X e Y de longitud mayor que 4. También son subsecuencias comunes de longitud 4 "maoa" o "amoa".
Se desea encontrar la longitud de las subsecuencias comunes más largas de dos secuencias de caracteres dadas.
Definir la función
longitudSCM :: Eq a => [a] -> [a] -> Int
tal que longitudSCM xs ys es la longitud de la subsecuencia máxima de xs e ys. Por ejemplo,
longitudSCM "amapola" "matamoscas" == 4 longitudSCM "atamos" "matamoscas" == 6 longitudSCM "aaa" "bbbb" == 0
El coeficiente binomial n sobre k es el número de subconjuntos de k elementos escogidos de un conjunto con n elementos.
Definir la función
binomial :: Integer -> Integer -> Integer
tal que binomial n k es el coeficiente binomial n sobre k. Por ejemplo,
binomial 6 3 == 20 binomial 5 2 == 10 binomial 5 3 == 10
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, ...
Escribir dos definiciones (una recursiva y otra con programación dinámica) de la función
fib :: Integer -> Integer
tal que fib n es el n-ésimo término de la sucesión de Fibonacci. Por ejemplo,
fib 6 == 8
Comparar la eficiencia de las dos definiciones.
En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medición, una de A litros de capacidad y otra de B. También se dispone de una bomba que permite llenar las jarras de agua.
El problema de las jarras (A,B,C) consiste en determinar cómo se puede lograr tener exactamente C litros de agua en la jarra de A litros de capacidad.
Usando el procedimiento de búsqueda en anchura, definir la función
jarras :: (Int,Int,Int) -> [[(Int,Int)]]
tal jarras (a,b,c) es la lista de las soluciones del problema de las jarras (a,b,c). Por ejemplo,
λ> take 3 (jarras (4,3,2))
[[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)],
[(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)],
[(0,0),(0,3),(3,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]]
La interpretación [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)] es:
Otros ejemplos
λ> length (jarras (15,10,5)) 8 λ> map length (jarras (15,10,5)) [3,5,5,7,7,7,8,9] λ> jarras (15,10,4) []
El problema de suma cero consiste en, dado el conjunto de enteros, encontrar sus subconjuntos no vacío cuyos elementos sumen cero.
Usando el procedimiento de búsqueda en profundidad, definir la función
suma0 :: [Int] -> [[Int]]
tal que suma0 ns es la lista de las soluciones del problema de suma cero para ns. Por ejemplo,
λ> suma0 [-7,-3,-2,5,8] [[-3,-2,5]] λ> suma0 [-7,-3,-2,5,8,-1] [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]] λ> suma0 [-7,-3,1,5,8] []
Las fichas del dominó se pueden representar por pares de enteros. El problema del dominó consiste en colocar todas las fichas de una lista dada de forma que el segundo número de cada ficha coincida con el primero de la siguiente.
Usando el procedimiento de búsqueda en profundidad, definir la función
domino :: [(Int,Int)] -> [[(Int,Int)]]
tal que domino fs es la lista de las soluciones del problema del dominó correspondiente a las fichas fs. Por ejemplo,
λ> domino [(1,2),(2,3),(1,4)] [[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]] λ> domino [(1,2),(1,1),(1,4)] [[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]] λ> domino [(1,2),(3,4),(2,3)] [[(1,2),(2,3),(3,4)],[(4,3),(3,2),(2,1)]] λ> domino [(1,2),(2,3),(5,4)] []
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
module El_problema_del_domino where import BusquedaEnProfundidad (buscaProfundidad) import Data.List (delete) import Test.Hspec (Spec, hspec, it, shouldBe) -- Las fichas son pares de números enteros. type Ficha = (Int,Int) -- Un problema está definido por la lista de fichas que hay que colocar type Problema = [Ficha] -- Los estados son los pares formados por la listas sin colocar y las -- colocadas. type Estado = ([Ficha],[Ficha]) -- (inicial p) es el estado inicial del problema p. Por ejemplo, -- λ> inicial [(1,2),(2,3),(1,4)] -- ([(1,2),(2,3),(1,4)],[]) inicial :: Problema -> Estado inicial p = (p,[]) -- (esFinal e) se verifica si e es un estado final. Por ejemplo, -- λ> esFinal ([], [(4,1),(1,2),(2,3)]) -- True -- λ> esFinal ([(2,3)], [(4,1),(1,2)]) -- False esFinal :: Estado -> Bool esFinal = null . fst -- (sucesores e) es la lista de los sucesores del estado e. Por ejemplo, -- λ> sucesores ([(1,2),(2,3),(1,4)],[]) -- [([(2,3),(1,4)],[(1,2)]), -- ([(1,2),(1,4)],[(2,3)]), -- ([(1,2),(2,3)],[(1,4)]), -- ([(2,3),(1,4)],[(2,1)]), -- ([(1,2),(1,4)],[(3,2)]), -- ([(1,2),(2,3)],[(4,1)])] -- λ> sucesores ([(2,3),(1,4)],[(1,2)]) -- [([(2,3)],[(4,1),(1,2)])] -- λ> sucesores ([(2,3),(1,4)],[(2,1)]) -- [([(1,4)],[(3,2),(2,1)])] sucesores :: Estado -> [Estado] sucesores (fs,[]) = [(delete (a,b) fs, [(a,b)]) | (a,b) <- fs, a /= b] ++ [(delete (a,b) fs, [(b,a)]) | (a,b) <- fs] sucesores (fs,e@((x,_):_)) = [(delete (u,v) fs,(u,v):e) | (u,v) <- fs, u /= v, v == x] ++ [(delete (u,v) fs,(v,u):e) | (u,v) <- fs, u /= v, u == x] ++ [(delete (u,v) fs,(u,v):e) | (u,v) <- fs, u == v, u == x] -- (soluciones p) es la lista de las soluciones del problema p. Por -- ejemplo, -- λ> soluciones [(1,2),(2,3),(1,4)] -- [([],[(4,1),(1,2),(2,3)]),([],[(3,2),(2,1),(1,4)])] soluciones :: Problema -> [Estado] soluciones p = buscaProfundidad sucesores esFinal (inicial p) domino :: Problema -> [[Ficha]] domino p = map snd (soluciones p) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ domino [(1,2),(2,3),(1,4)] `shouldBe` [[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]] it "e2" $ domino [(1,2),(1,1),(1,4)] `shouldBe` [[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]] it "e3" $ domino [(1,2),(3,4),(2,3)] `shouldBe` [[(1,2),(2,3),(3,4)],[(4,3),(3,2),(2,1)]] it "e4" $ domino [(1,2),(2,3),(5,4)] `shouldBe` [] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0013 seconds -- 4 examples, 0 failures
from src.BusquedaEnProfundidad import buscaProfundidad # Las fichas son pares de números enteros. Ficha = tuple[int, int] # Un problema está definido por la lista de fichas que hay que colocar Problema = list[Ficha] # Los estados son los pares formados por la listas sin colocar y las # colocadas. Estado = tuple[list[Ficha], list[Ficha]] # inicial(p) es el estado inicial del problema p. Por ejemplo, # >>> inicial([(1,2),(2,3),(1,4)]) # ([(1, 2), (2, 3), (1, 4)], []) def inicial(p: Problema) -> Estado: return (p, []) # esFinal(e) se verifica si e es un estado final. Por ejemplo, # >>> esFinal(([], [(4,1),(1,2),(2,3)])) # True # >>> esFinal(([(2,3)], [(4,1),(1,2)])) # False def esFinal(e: Estado) -> bool: return not e[0] # elimina(f, fs) es la lista obtenida eliminando la ficha f de la lista # fs. Por ejemplo, # >>> elimina((1,2),[(4,1),(1,2),(2,3)]) # [(4, 1), (2, 3)] def elimina(f: Ficha, fs: list[Ficha]) -> list[Ficha]: return [g for g in fs if g != f] # sucesores(e) es la lista de los sucesores del estado e. Por ejemplo, # >>> sucesores(([(1,2),(2,3),(1,4)],[])) # [([(2,3),(1,4)],[(1,2)]), # ([(1,2),(1,4)],[(2,3)]), # ([(1,2),(2,3)],[(1,4)]), # ([(2,3),(1,4)],[(2,1)]), # ([(1,2),(1,4)],[(3,2)]), # ([(1,2),(2,3)],[(4,1)])] # >>> sucesores(([(2,3),(1,4)],[(1,2)])) # [([(2,3)],[(4,1),(1,2)])] # >>> sucesores(([(2,3),(1,4)],[(2,1)])) # [([(1,4)],[(3,2),(2,1)])] def sucesores(e: Estado) -> list[Estado]: if not e[1]: return [(elimina((a,b), e[0]), [(a,b)]) for (a,b) in e[0] if a != b] + \ [(elimina((a,b), e[0]), [(b,a)]) for (a,b) in e[0]] return [(elimina((u,v),e[0]),[(u,v)]+e[1]) for (u,v) in e[0] if u != v and v == e[1][0][0]] +\ [(elimina((u,v),e[0]),[(v,u)]+e[1]) for (u,v) in e[0] if u != v and u == e[1][0][0]] +\ [(elimina((u,v),e[0]),[(u,v)]+e[1]) for (u,v) in e[0] if u == v and u == e[1][0][0]] # soluciones(p) es la lista de las soluciones del problema p. Por # ejemplo, # >>> soluciones([(1,2),(2,3),(1,4)]) # [([], [(3, 2), (2, 1), (1, 4)]), ([], [(4, 1), (1, 2), (2, 3)])] def soluciones(p: Problema) -> list[Estado]: return buscaProfundidad(sucesores, esFinal, inicial(p)) def domino(p: Problema) -> list[list[Ficha]]: return [s[1] for s in soluciones(p)] # # Verificación # # ============ def test_domino() -> None: assert domino([(1,2),(2,3),(1,4)]) == \ [[(3, 2), (2, 1), (1, 4)], [(4, 1), (1, 2), (2, 3)]] assert domino([(1,2),(1,1),(1,4)]) == \ [[(2, 1), (1, 1), (1, 4)], [(4, 1), (1, 1), (1, 2)]] assert domino([(1,2),(3,4),(2,3)]) == \ [[(4, 3), (3, 2), (2, 1)], [(1, 2), (2, 3), (3, 4)]] assert domino([(1,2),(2,3),(5,4)]) == \ [] print("Verificado") # La verificación es # >>> test_domino() # Verificado
El problema del calendario, para una competición deportiva en la que se enfrentan n participantes, consiste en elaborar un calendario de forma que:
Por ejemplo, con 8 participantes una posible solución es
| 1 2 3 4 5 6 7 --+-------------- 1 | 2 3 4 5 6 7 8 2 | 1 4 3 6 5 8 7 3 | 4 1 2 7 8 5 6 4 | 3 2 1 8 7 6 5 5 | 6 7 8 1 2 3 4 6 | 5 8 7 2 1 4 3 7 | 8 5 6 3 4 1 2 8 | 7 6 5 4 3 2 1
donde las filas indican los jugadores y las columnas los días; es decir, el elemento (i,j) indica el adversario del jugador i el día j; por ejemplo, el adversario del jugador 2 el 4ª día es el jugador 6.
Para representar el problema se define el tipo Calendario como matrices de enteros,
Usando el procedimiento de búsqueda en profundidad, definir la función
calendario :: Int -> [Calendario]
tal que calendario n son las soluciones del problema del calendario, con n participantes, mediante el patrón de búsqueda em profundidad. Por ejemplo,
λ> head (calendario 6) ┌ ┐ │ 2 3 4 5 6 │ │ 1 4 5 6 3 │ │ 5 1 6 4 2 │ │ 6 2 1 3 5 │ │ 3 6 2 1 4 │ │ 4 5 3 2 1 │ └ ┘ λ> length (calendario 6) 720 λ> length (calendario 5) 0
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
module El_problema_del_calendario_mediante_busqueda_en_espacio_de_estado where import BusquedaEnProfundidad (buscaProfundidad) import Data.Matrix (Matrix, (!), nrows, zero, setElem, toLists) import Data.List ((\\)) import Test.Hspec (Spec, hspec, it, shouldBe) type Calendario = Matrix Int -- (inicial n) es el estado inicial para el problema del calendario con -- n participantes; es decir, una matriz de n fila y n-1 columnas con -- todos sus elementos iguales a 0. Por ejemplo, -- λ> inicial 4 -- ┌ ┐ -- │ 0 0 0 │ -- │ 0 0 0 │ -- │ 0 0 0 │ -- │ 0 0 0 │ -- └ ┘ inicial :: Int -> Calendario inicial n = zero n (n-1) -- (huecos c) es la lista de las posiciones de c cuyo valor es 0. huecos :: Calendario -> [(Int, Int)] huecos c = [(i,j) | i <- [1..n], j <- [1..n-1], c!(i,j) == 0] where n = nrows c -- (sucesores c) es la lista de calendarios obtenidos poniendo en el -- lugar del primer elemento nulo de c uno de los posibles jugadores de -- forma que se cumplan las condiciones del problema. Por ejemplo, -- λ> sucesores (inicial 4) -- [┌ ┐ ┌ ┐ ┌ ┐ -- │ 2 0 0 │ │ 3 0 0 │ │ 4 0 0 │ -- │ 1 0 0 │ │ 0 0 0 │ │ 0 0 0 │ -- │ 0 0 0 │ │ 1 0 0 │ │ 0 0 0 │ -- │ 0 0 0 │ │ 0 0 0 │ │ 1 0 0 │ -- └ ┘, └ ┘, └ ┘] -- λ> sucesores (fromLists [[2,3,0],[1,0,0],[0,1,0],[0,0,0]]) -- [┌ ┐ -- │ 2 3 4 │ -- │ 1 0 0 │ -- │ 0 1 0 │ -- │ 0 0 1 │ -- └ ┘] -- λ> sucesores (fromLists [[2,3,4],[1,0,0],[0,1,0],[0,0,1]]) -- [┌ ┐ -- │ 2 3 4 │ -- │ 1 4 0 │ -- │ 0 1 0 │ -- │ 0 2 1 │ -- └ ┘] sucesores :: Calendario -> [Calendario] sucesores c = [setElem i (k,j) (setElem k (i,j) c) | k <- [1..n] \\ (i : [c!(k,j) | k <- [1..i-1]] ++ [c!(i,k) | k <- [1..j-1]]), c!(k,j) == 0] where n = nrows c (i,j) = head (huecos c) -- (esFinal c) se verifica si c un estado final para el problema -- del calendario con n participantes; es decir, no queda en c ningún -- elemento igual a 0. Por ejemplo, -- λ> esFinal (fromLists [[2,3,4],[1,4,3],[4,1,2],[3,2,1]]) -- True -- λ> esFinal (fromLists [[2,3,4],[1,4,3],[4,1,2],[3,2,0]]) -- False esFinal :: Calendario -> Bool esFinal c = null (huecos c) calendario :: Int -> [Calendario] calendario n = buscaProfundidad sucesores esFinal (inicial n) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ toLists (head (calendario 6)) `shouldBe` [[2,3,4,5,6],[1,4,5,6,3],[5,1,6,4,2],[6,2,1,3,5],[3,6,2,1,4],[4,5,3,2,1]] it "e2" $ length (calendario 6) `shouldBe` 720 it "e3" $ length (calendario 5) `shouldBe` 0 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- -- Finished in 0.2580 seconds -- 3 examples, 0 failures
from copy import deepcopy from typing import Optional import numpy as np import numpy.typing as npt from src.BusquedaEnProfundidad import buscaProfundidad Calendario = npt.NDArray[np.complex64] # inicial(n) es el estado inicial para el problema del calendario con # n participantes; es decir, una matriz de n fila y n-1 columnas con # todos sus elementos iguales a 0. Por ejemplo, # >>> inicial(4) # array([[0, 0, 0], # [0, 0, 0], # [0, 0, 0], # [0, 0, 0]]) def inicial(n: int) -> Calendario: return np.zeros((n, n - 1), dtype=int) # primerHueco(c) es la posición del primer elemento cuyo valor es 0. Si # todos los valores son distintos de 0, devuelve (-1,-1). Por ejemplo, # primerHueco(np.array([[1,2,3],[4,5,0],[7,0,0]])) == (1, 2) # primerHueco(np.array([[1,2,3],[4,5,6],[7,8,0]])) == (2, 2) # primerHueco(np.array([[1,2,3],[4,5,6],[7,8,9]])) == (-1, -1) def primerHueco(c: Calendario) -> tuple[int, int]: (n, m) = c.shape for i in range(0, n): for j in range(0, m): if c[i,j] == 0: return (i, j) return (-1, -1) # libres(c, i, j) es la lista de valores que que pueden poner en la # posición (i,j) del calendario c. Por ejemplo, # libres(np.array([[0,0,0],[0,0,0],[0,0,0],[0,0,0]]),0,0) == [2, 3, 4] # libres(np.array([[2,0,0],[1,0,0],[0,0,0],[0,0,0]]),0,1) == [3, 4] # libres(np.array([[2,3,0],[1,0,0],[0,1,0],[0,0,0]]),0,2) == [4] # libres(np.array([[2,3,4],[1,0,0],[0,1,0],[0,0,1]]),1,1) == [4] # libres(np.array([[2,3,4],[1,4,0],[0,1,0],[0,2,1]]),1,2) == [3] def libres(c: Calendario, i: int, j: int) -> list[int]: n = c.shape[0] return list(set(range(1, n + 1)) - {i + 1} - set(c[i]) - set(c[:,j])) # setElem(k, i, j, c) es el calendario obtenido colocando en c el valor # k en la posición (i,j). # >>> setElem(7,1,2,np.array([[1,2,3],[4,5,0],[0,0,0]])) # array([[1, 2, 3], # [4, 5, 7], # [0, 0, 0]]) def setElem(k: int, i: int, j: int, c: Calendario) -> Calendario: _c = deepcopy(c) _c[i, j] = k return _c # sucesores(c) es la lista de calendarios obtenidos poniendo en el # lugar del primer elemento nulo de c uno de los posibles jugadores de # forma que se cumplan las condiciones del problema. Por ejemplo, # >>> sucesores(np.array([[0,0,0],[0,0,0],[0,0,0],[0,0,0]])) # [array([[2,0,0], [1,0,0], [0,0,0], [0,0,0]]), # array([[3,0,0], [0,0,0], [1,0,0], [0,0,0]]), # array([[4,0,0], [0,0,0], [0,0,0], [1,0,0]])] # >>> sucesores(np.array([[2,0,0],[1,0,0],[0,0,0],[0,0,0]])) # [array([[2,3,0], [1,0,0], [0,1,0], [0,0,0]]), # array([[2,4,0], [1,0,0], [0,0,0], [0,1,0]])] # >>> sucesores(np.array([[2,3,0],[1,0,0],[0,1,0],[0,0,0]])) # [array([[2,3,4], [1,0,0], [0,1,0], [0,0,1]])] # >>> sucesores(np.array([[2,3,4],[1,0,0],[0,1,0],[0,0,1]])) # [array([[2,3,4], [1,4,0], [0,1,0], [0,2,1]])] # >>> sucesores(np.array([[2,3,4],[1,4,0],[0,1,0],[0,2,1]])) # [array([[2,3,4], [1,4,3], [0,1,2], [0,2,1]])] # >>> sucesores(np.array([[2,3,4],[1,4,3],[0,1,2],[0,2,1]])) # [array([[2,3,4], [1,4,3], [4,1,2], [3,2,1]])] # >>> sucesores(np.array([[2,3,4],[1,4,3],[4,1,2],[3,2,1]])) # [] def sucesores(c: Calendario) -> list[Calendario]: n = c.shape[0] (i, j) = primerHueco(c) return [setElem(i+1, k-1, j, setElem(k, i, j, c)) for k in libres(c, i, j)] # esFinal(c) se verifica si c un estado final para el problema # del calendario con n participantes; es decir, no queda en c ningún # elemento igual a 0. Por ejemplo, # >>> esFinal(np.array([[2,3,4],[1,4,3],[4,1,2],[3,2,1]])) # True # >>> esFinal(np.array([[2,3,4],[1,4,3],[4,1,2],[3,2,0]])) # False def esFinal(c: Calendario) -> bool: return primerHueco(c) == (-1, -1) def calendario(n: int) -> list[Calendario]: return buscaProfundidad(sucesores, esFinal, inicial(n)) # Verificación # ============ def test_calendario() -> None: def filas(p: Calendario) -> list[list[int]]: return p.tolist() assert filas(calendario(6)[0]) == \ [[6, 5, 4, 3, 2], [5, 4, 3, 6, 1], [4, 6, 2, 1, 5], [3, 2, 1, 5, 6], [2, 1, 6, 4, 3], [1, 3, 5, 2, 4]] assert len(calendario(6)) == 720 assert len(calendario(5)) == 0 print("Verificado")
Para el problema de las fichas de orden (m,n) se considera un tablero con m+n+1 cuadrados consecutivos.
Inicialmente, en cada uno de los m primeros cuadrados hay una blanca, a continuación un hueco y en cada uno de los n últimos cuadrados hay una ficha verde. El objetivo consiste en tener las fichas verdes al principio y las blancas al final.
Por ejemplo, en el problema de las fichas de orden (3,3) el tablero inicial es
+---+---+---+---+---+---+---+
| B | B | B | | V | V | V |
+---+---+---+---+---+---+---+
y el final es
+---+---+---+---+---+---+---+
| V | V | V | | B | B | B |
+---+---+---+---+---+---+---+
Los movimientos permitidos consisten en desplazar una ficha al hueco saltando, como máximo, sobre otras dos.
Para representar el problema se definen los siguientes tipos de datos:
Ficha con tres constructores B, V y H que representan las fichas blanca, verde y hueco, respectivamente.data Ficha = B | V | H deriving (Eq, Show)
Tablero que es una lista de fichas que representa las fichas colocadas en el tablero.type Tablero = [Ficha]
Estado representa los estados del espacio de búsqueda, donde un estado es una lista de tableros [t(n), ..., t(2), t(1)] tal que t(1) es el tablero inicial y para cada i (2 <= i <= n), t(i) es un sucesor de t(i-1).newtype Estado = E [Tablero] deriving (Eq, Show)
Busqueda es un procedimiento de búsquedatype Busqueda = (Estado -> [Estado]) -> (Estado -> Bool) -> Estado -> [Estado]
Además, se considera la heurística que para cada tablero vale la suma de piezas blancas situadas a la izquierda de cada una de las piezas verdes. Por ejemplo, para el estado
+---+---+---+---+---+---+---+
| B | V | B | | V | V | B |
+---+---+---+---+---+---+---+
su valor es 1+2+2 = 5. La heurística de un estado es la del primero de sus tableros.
Usando los métodos de búsqueda estudiado en los ejercicios anteriores, definir la función
fichas :: Busqueda -> Int -> Int -> [[Tablero]]
tal que fichas b m n es la lista de las soluciones del problema de las fichas de orden (m,n) obtenidas mediante el procedimiento de búsqueda b. Por ejemplo,
λ> head (fichas buscaProfundidad 2 2)
[[B,B,H,V,V],[B,H,B,V,V],[H,B,B,V,V],[V,B,B,H,V],[V,B,H,B,V],[V,H,B,B,V],
[H,V,B,B,V],[B,V,H,B,V],[B,H,V,B,V],[H,B,V,B,V],[B,B,V,H,V],[B,B,V,V,H],
[B,H,V,V,B],[H,B,V,V,B],[V,B,H,V,B],[V,H,B,V,B],[H,V,B,V,B],[B,V,H,V,B],
[B,V,V,H,B],[H,V,V,B,B],[V,H,V,B,B],[V,V,H,B,B]]
λ> head (fichas buscaAnchura 2 2)
[[B,B,H,V,V],[B,B,V,V,H],[B,H,V,V,B],[B,V,V,H,B],[H,V,V,B,B],
[V,V,H,B,B]]
λ> head (fichas buscaPM 2 2)
[[B,B,H,V,V],[B,H,B,V,V],[B,V,B,H,V],[H,V,B,B,V],[V,H,B,B,V],
[V,V,B,B,H],[V,V,B,H,B],[V,V,H,B,B]]
λ> head (fichas buscaEscalada 2 2)
[[B,B,H,V,V],[B,H,B,V,V],[B,V,B,H,V],[H,V,B,B,V],[V,H,B,B,V],
[V,V,B,B,H],[V,V,B,H,B],[V,V,H,B,B]]
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
module BEE_El_problema_de_las_fichas where import BusquedaEnProfundidad (buscaProfundidad) import BusquedaEnAnchura (buscaAnchura) import BusquedaPrimeroElMejor (buscaPM) import BusquedaEnEscalada (buscaEscalada) import Test.Hspec (Spec, hspec, it, shouldBe) -- Representación del problema -- =========================== data Ficha = B | V | H deriving (Eq, Show) type Tablero = [Ficha] -- (tableroInicial m n) representa el tablero inicial del problema de las fichas -- de orden (m,n). Por ejemplo, -- tableroInicial 2 3 == [B,B,H,V,V,V] -- tableroInicial 3 2 == [B,B,B,H,V,V] tableroInicial :: Int -> Int -> Tablero tableroInicial m n = replicate m B ++ [H] ++ replicate n V -- (tableroFinal m n) representa el tablero final del problema de las fichas de -- orden (m,n). Por ejemplo, -- tableroFinal 2 3 == [V,V,V,H,B,B] -- tableroFinal 3 2 == [V,V,H,B,B,B] tableroFinal :: Int -> Int -> Tablero tableroFinal m n = replicate n V ++ [H] ++ replicate m B -- (tablerosSucesores t) es la lista de los sucesores del tablero t. Por -- ejemplo, -- λ> tablerosSucesores [V,B,H,V,V,B] -- [[V,H,B,V,V,B],[H,B,V,V,V,B],[V,B,V,H,V,B],[V,B,V,V,H,B], -- [V,B,B,V,V,H]] -- λ> tablerosSucesores [B,B,B,H,V,V,V] -- [[B,B,H,B,V,V,V],[B,H,B,B,V,V,V],[H,B,B,B,V,V,V], -- [B,B,B,V,H,V,V],[B,B,B,V,V,H,V],[B,B,B,V,V,V,H]] tablerosSucesores :: Tablero -> [Tablero] tablerosSucesores t = [intercambia i j t | i <- [j-1,j-2,j-3,j+1,j+2,j+3] , 0 <= i, i < n] where j = posicionHueco t n = length t -- (posicionHueco t) es la posición del hueco en el tablero t. Por -- ejemplo, -- posicionHueco (tableroInicial 3 2) == 3 posicionHueco :: Tablero -> Int posicionHueco t = length (takeWhile (/=H) t) -- (intercambia xs i j) es la lista obtenida intercambiando los -- elementos de xs en las posiciones i y j. Por ejemplo, -- intercambia 2 6 [0..9] == [0,1,6,3,4,5,2,7,8,9] -- intercambia 6 2 [0..9] == [0,1,6,3,4,5,2,7,8,9] intercambia :: Int -> Int -> [a] -> [a] intercambia i j xs = concat [xs1,[x2],xs2,[x1],xs3] where (xs1,x1,xs2,x2,xs3) = divide (min i j) (max i j) xs -- (divide xs i j) es la tupla (xs1,x1,xs2,x2,xs3) tal que xs1 son los -- elementos de xs cuya posición es menor que i, x1 es el elemento de xs -- en la posición i, xs2 son los elementos de xs cuya posición es mayor -- que i y menor que j, x2 es el elemento de xs en la posición j y xs3 -- son los elementos de xs cuya posición es mayor que j (suponiendo que -- i < j). Por ejemplo, -- divide 2 6 [0..9] == ([0,1],2,[3,4,5],6,[7,8,9]) divide :: Int -> Int -> [a] -> ([a],a,[a],a,[a]) divide i j xs = (xs1,x1,xs2,x2,xs3) where (xs1,x1:ys) = splitAt i xs (xs2,x2:xs3) = splitAt (j - i - 1) ys newtype Estado = E [Tablero] deriving (Eq, Show) -- (inicial m n) representa el estado inicial del problema de las fichas -- de orden (m,n). Por ejemplo, -- inicial 2 3 == E [[B,B,H,V,V,V]] -- inicial 3 2 == E [[B,B,B,H,V,V]] inicial :: Int -> Int -> Estado inicial m n = E [tableroInicial m n] -- (esFinal m n e) se verifica si e es un estado final del problema de las -- fichas de orden (m,n). Por ejemplo, -- λ> esFinal 2 1 (E [[V,H,B,B],[V,B,B,H],[H,B,B,V],[B,B,H,V]]) -- True -- λ> esFinal 2 1 (E [[V,B,B,H],[H,B,B,V],[B,B,H,V]]) -- False esFinal :: Int -> Int -> Estado -> Bool esFinal m n (E (e:_)) = e == tableroFinal m n -- (sucesores n) es la lista de los sucesores del estado n. Por ejemplo, -- λ> sucesores (E [[H,B,B,V],[B,B,H,V]]) -- [E [[B,H,B,V],[H,B,B,V],[B,B,H,V]], -- E [[V,B,B,H],[H,B,B,V],[B,B,H,V]]] -- λ> sucesores (E [[B,H,B,V],[H,B,B,V],[B,B,H,V]]) -- [E [[B,V,B,H],[B,H,B,V],[H,B,B,V],[B,B,H,V]]] sucesores :: Estado -> [Estado] sucesores (E e@(t:ts)) = [E (t':e) | t' <- tablerosSucesores t, t' `notElem` ts] -- Heurística -- ========== -- (heuristicaT t) es la heurística del tablero t. Por ejemplo, -- heuristicaT [B,V,B,H,V,V,B] == 5 heuristicaT :: Tablero -> Int heuristicaT [] = 0 heuristicaT (V:xs) = heuristicaT xs heuristicaT (H:xs) = heuristicaT xs heuristicaT (B:xs) = heuristicaT xs + length (filter (==V) xs) -- (heuristica e) es la heurística del primer tablero del estado e. Por -- ejemplo, -- heuristica (E [[H,B,B,V],[B,B,H,V]]) == 2 -- heuristica (E [[V,B,B,H],[H,B,B,V],[B,B,H,V]]) == 0 heuristica :: Estado -> Int heuristica (E (t:_)) = heuristicaT t -- Estado es un subtipo de Ord de forma que un estado es menor o igual -- que otro si su heurística lo es. instance Ord Estado where e1 <= e2 = heuristica e1 <= heuristica e2 -- Solución por búsqueda -- ===================== type Busqueda = (Estado -> [Estado]) -> (Estado -> Bool) -> Estado -> [Estado] fichas :: Busqueda -> Int -> Int -> [[Tablero]] fichas b m n = [reverse es | E es <- b sucesores (esFinal m n) (inicial m n)] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ head (fichas buscaProfundidad 2 2) `shouldBe` [[B,B,H,V,V],[B,H,B,V,V],[H,B,B,V,V],[V,B,B,H,V],[V,B,H,B,V],[V,H,B,B,V], [H,V,B,B,V],[B,V,H,B,V],[B,H,V,B,V],[H,B,V,B,V],[B,B,V,H,V],[B,B,V,V,H], [B,H,V,V,B],[H,B,V,V,B],[V,B,H,V,B],[V,H,B,V,B],[H,V,B,V,B],[B,V,H,V,B], [B,V,V,H,B],[H,V,V,B,B],[V,H,V,B,B],[V,V,H,B,B]] it "e2" $ head (fichas buscaAnchura 2 2) `shouldBe` [[B,B,H,V,V],[B,B,V,V,H],[B,H,V,V,B],[B,V,V,H,B],[H,V,V,B,B],[V,V,H,B,B]] it "e3" $ head (fichas buscaPM 2 2) `shouldBe` [[B,B,H,V,V],[B,H,B,V,V],[B,V,B,H,V],[H,V,B,B,V],[V,H,B,B,V],[V,V,B,B,H], [V,V,B,H,B],[V,V,H,B,B]] it "e4" $ head (fichas buscaEscalada 2 2) `shouldBe` [[B,B,H,V,V],[B,H,B,V,V],[B,V,B,H,V],[H,V,B,B,V],[V,H,B,B,V],[V,V,B,B,H], [V,V,B,H,B],[V,V,H,B,B]] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0055 seconds -- 4 examples, 0 failures
from enum import Enum from functools import partial from typing import Callable, Optional from src.BusquedaEnAnchura import buscaAnchura1 from src.BusquedaEnEscalada import buscaEscalada from src.BusquedaEnProfundidad import buscaProfundidad1 from src.BusquedaPrimeroElMejor import buscaPM # Representación del problema # =========================== class Ficha(Enum): B = 0 V = 1 H = 2 def __repr__(self) -> str: return self.name B = Ficha.B V = Ficha.V H = Ficha.H Tablero = list[Ficha] # tableroInicial(m, n) representa el tablero inicial del problema de las fichas # de orden (m,n). Por ejemplo, # tableroInicial(2, 3) == [B,B,H,V,V,V] # tableroInicial(3, 2) == [B,B,B,H,V,V] def tableroInicial(m: int, n: int) -> Tablero: return [B]*m + [H] + [V]*n # tableroFinal(m, n) representa el tablero final del problema de las fichas de # orden (m,n). Por ejemplo, # tableroFinal(2, 3) == [V,V,V,H,B,B] # tableroFinal(3, 2) == [V,V,H,B,B,B] def tableroFinal(m: int, n: int) -> Tablero: return [V]*n + [H] + [B]*m # posicionHueco(t) es la posición del hueco en el tablero t. Por # ejemplo, # posicionHueco(tableroInicial(3, 2)) == 3 def posicionHueco(t: Tablero) -> int: return t.index(H) # intercambia(xs, i, j) es la lista obtenida intercambiando los # elementos de xs en las posiciones i y j. Por ejemplo, # intercambia(1, 3, tableroInicial(3, 2)) == [B, H, B, B, V, V] def intercambia(i: int, j: int, t: Tablero) -> Tablero: t1 = t.copy() t1[i], t1[j] = t1[j], t1[i] return t1 # tablerosSucesores(t) es la lista de los sucesores del tablero t. Por # ejemplo, # >>> tablerosSucesores([V,B,H,V,V,B]) # [[V,H,B,V,V,B],[H,B,V,V,V,B],[V,B,V,H,V,B],[V,B,V,V,H,B], # [V,B,B,V,V,H]] # >>> tablerosSucesores([B,B,B,H,V,V,V]) # [[B,B,H,B,V,V,V],[B,H,B,B,V,V,V],[H,B,B,B,V,V,V], # [B,B,B,V,H,V,V],[B,B,B,V,V,H,V],[B,B,B,V,V,V,H]] def tablerosSucesores(t: Tablero) -> list[Tablero]: j = posicionHueco(t) n = len(t) return [intercambia(i, j, t) for i in [j-1,j-2,j-3,j+1,j+2,j+3] if 0 <= i < n] # Heurística # ========== # heuristicaT(t) es la heurística del tablero t. Por ejemplo, # heuristicaT([B,V,B,H,V,V,B]) == 5 def heuristicaT(t: Tablero) -> int: if not t: return 0 f, *fs = t if f in {V, H}: return heuristicaT(fs) return heuristicaT(fs) + len([x for x in fs if x == V]) class Estado(list[Tablero]): def __lt__(self, e: list[Tablero]) -> bool: return heuristicaT(self[0]) < heuristicaT(e[0]) # inicial(m, n) representa el estado inicial del problema de las fichas # de orden (m,n). Por ejemplo, # inicial(2, 3) == [[B,B,H,V,V,V]] # inicial(3, 2) == [[B,B,B,H,V,V]] def inicial(m: int, n: int) -> Estado: return Estado([tableroInicial(m, n)]) # esFinal(m, n, e) se verifica si e es un estado final del problema de las # fichas de orden (m,n). Por ejemplo, # >>> esFinal(2, 1, [[V,H,B,B],[V,B,B,H],[H,B,B,V],[B,B,H,V]]) # True # >>> esFinal(2, 1, [[V,B,B,H],[H,B,B,V],[B,B,H,V]]) # False def esFinal(m: int, n: int, e: Estado) -> bool: return e[0] == tableroFinal(m, n) # (sucesores n) es la lista de los sucesores del estado n. Por ejemplo, # >>> sucesores([[H,B,B,V],[B,B,H,V]]) # [[[B,H,B,V],[H,B,B,V],[B,B,H,V]], # [[V,B,B,H],[H,B,B,V],[B,B,H,V]]] # >>> sucesores([[B,H,B,V],[H,B,B,V],[B,B,H,V]]) # [[[B,V,B,H],[B,H,B,V],[H,B,B,V],[B,B,H,V]]] def sucesores(e: Estado) -> list[Estado]: t, *ts = e return [Estado([t1] + e) for t1 in tablerosSucesores(t) if t1 not in ts] # Solución por búsqueda # ===================== Busqueda = Callable[[Callable[[Estado], list[Estado]], Callable[[Estado], bool], Estado], Optional[Estado]] def fichas(b: Busqueda, m: int, n: int) -> Optional[list[Tablero]]: r = partial(b, sucesores, lambda e: esFinal(m, n, e), inicial(m, n))() if r is None: return None return [list(reversed(es)) for es in r] # Verificación # ============ def test_fichas() -> None: assert fichas(buscaProfundidad1, 1, 2) == \ [[B, H, V, V], [B, V, V, H], [H, V, V, B], [V, V, H, B]] assert fichas(buscaAnchura1, 1, 2) == \ [[B, H, V, V], [B, V, V, H], [H, V, V, B], [V, V, H, B]] assert fichas(buscaPM, 1, 2) == \ [[B, H, V, V], [B, V, H, V], [H, V, B, V], [V, V, B, H], [V, V, H, B]] assert fichas(buscaEscalada, 1, 2) == \ [[B, H, V, V], [H, B, V, V], [V, B, H, V], [V, H, B, V], [V, V, B, H], [V, V, H, B]] print("Verificado") # La verificación es # >>> test_fichas() # Verificado
Un granjero está parado en un lado del río y con él tiene un una cabra y una repollo. En el río hay un barco pequeño. El desea cruzar el río con sus tres posesiones. No hay puentes y en el barco hay solamente sitio para el granjero y un artículo. Si deja la cabra con la repollo sola en un lado del río la cabra comerá la repollo. Si deja el lobo y la cabra en un lado, el lobo se comerá a la cabra. ¿Cómo puede cruzar el granjero el río con los tres artículos, sin que ninguno se coma al otro?
Para representar el problema se definen los siguientes tipos de dato:
Orilla con dos constructores (I y D) que representan las orillas izquierda y derecha, respectivamente.Estado que es una tupla que representa en qué orilla se encuentra cada uno de los elementos (granjero, lobo, cabra, repollo). Por ejemplo, (I,D,D,I) representa que el granjero está en la izquierda, que el lobo está en la derecha, que la cabra está en la derecha y el repollo está en la izquierda.Usando el procedimiento de búsqueda en profundidad, definir la función
granjero :: [[Estado]]
tal que granjero son las soluciones del problema del granjero mediante el patrón de búsqueda en espacio de estados. Por ejemplo,
λ> head granjero
[(I,I,I,I),(D,I,D,I),(I,I,D,I),(D,D,D,I),
(I,D,I,I),(D,D,I,D),(I,D,I,D),(D,D,D,D)]
λ> length granjero
2
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
module BEE_El_problema_del_granjero where import BusquedaEnProfundidad (buscaProfundidad) import Test.Hspec (Spec, hspec, it, shouldBe) data Orilla = I | D deriving (Eq, Show) type Estado = (Orilla,Orilla,Orilla,Orilla) -- (seguro e) se verifica si el estado e es seguro; es decir, que no -- puede estar en una orilla el lobo con la cabra sin el granjero ni la -- cabra con el repollo sin el granjero. Por ejemplo, -- seguro (I,D,D,I) == False -- seguro (D,D,D,I) == True -- seguro (D,D,I,I) == False -- seguro (I,D,I,I) == True seguro :: Estado -> Bool seguro (g,l,c,r) = not (g /= c && (c == l || c == r)) -- (opuesta x) es la opuesta de la orilla x. Por ejemplo -- opuesta I = D opuesta :: Orilla -> Orilla opuesta I = D opuesta D = I -- (sucesoresE e) es la lista de los sucesores seguros del estado e. Por -- ejemplo, -- sucesoresE (I,I,I,I) == [(D,I,D,I)] -- sucesoresE (D,I,D,I) == [(I,I,D,I),(I,I,I,I)] sucesoresE :: Estado -> [Estado] sucesoresE e = [mov e | mov <- [m1,m2,m3,m4], seguro (mov e)] where m1 (g,l,c,r) = (opuesta g, l, c, r) m2 (g,l,c,r) = (opuesta g, opuesta l, c, r) m3 (g,l,c,r) = (opuesta g, l, opuesta c, r) m4 (g,l,c,r) = (opuesta g, l, c, opuesta r) -- Nodo es el tipo de los nodos del espacio de búsqueda, donde un nodo -- es una lista de estados -- [e_n, ..., e_2, e_1] -- tal que e_1 es el estado inicial y para cada i (2 <= i <= n), e_i es un -- sucesor de e_(i-1). newtype Nodo = Nodo [Estado] deriving (Eq, Show) -- inicial es el nodo inicial en el que todos están en la orilla -- izquierda. inicial :: Nodo inicial = Nodo [(I,I,I,I)] -- (esFinal n) se verifica si n es un nodo final; es decir, su primer -- elemento es el estado final. Por ejemplo, -- esFinal (Nodo [(D,D,D,D),(I,I,I,I)]) == True -- esFinal (Nodo [(I,I,D,I),(I,I,I,I)]) == False esFinal :: Nodo -> Bool esFinal (Nodo (n:_)) = n == (D,D,D,D) -- (sucesores n) es la lista de los sucesores del nodo n. Por ejemplo, -- λ> sucesores (Nodo [(I,I,D,I),(D,I,D,I),(I,I,I,I)]) -- [Nodo [(D,D,D,I),(I,I,D,I),(D,I,D,I),(I,I,I,I)], -- Nodo [(D,I,D,D),(I,I,D,I),(D,I,D,I),(I,I,I,I)]] sucesores :: Nodo -> [Nodo] sucesores (Nodo n@(e:es)) = [Nodo (e':n) | e' <- sucesoresE e, e' `notElem` es] granjero :: [[Estado]] granjero = [reverse es | (Nodo es) <- buscaProfundidad sucesores esFinal inicial] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ head granjero `shouldBe` [(I,I,I,I),(D,I,D,I),(I,I,D,I),(D,D,D,I), (I,D,I,I),(D,D,I,D),(I,D,I,D),(D,D,D,D)] it "e2" $ length granjero `shouldBe` 2 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.0008 seconds -- 2 examples, 0 failures
from enum import Enum from src.BusquedaEnProfundidad import buscaProfundidad class Orilla(Enum): I = 0 D = 1 def __repr__(self) -> str: return self.name I = Orilla.I D = Orilla.D Estado = tuple[Orilla, Orilla, Orilla, Orilla] # seguro(e) se verifica si el estado e es seguro; es decir, que no # puede estar en una orilla el lobo con la cabra sin el granjero ni la # cabra con el repollo sin el granjero. Por ejemplo, # seguro((I,D,D,I)) == False # seguro((D,D,D,I)) == True # seguro((D,D,I,I)) == False # seguro((I,D,I,I)) == True def seguro(e: Estado) -> bool: (g,l,c,r) = e return not (g != c and c in {l, r}) # (opuesta x) es la opuesta de la orilla x. Por ejemplo # opuesta(I) == D def opuesta(o: Orilla) -> Orilla: if o == I: return D return I # sucesoresE(e) es la lista de los sucesores seguros del estado e. Por # ejemplo, # sucesoresE((I,I,I,I)) == [(D,I,D,I)] # sucesoresE((D,I,D,I)) == [(I,I,D,I),(I,I,I,I)] def sucesoresE(e: Estado) -> list[Estado]: def mov(n: int, e: Estado) -> Estado: (g,l,c,r) = e if n == 1: return (opuesta(g), l, c, r) if n == 2: return (opuesta(g), opuesta(l), c, r) if n == 3: return (opuesta(g), l, opuesta(c), r) return (opuesta(g), l, c, opuesta(r)) return [mov(n, e) for n in range(1, 5) if seguro(mov(n, e))] # Nodo es el tipo de los nodos del espacio de búsqueda, donde un nodo # es una lista de estados # [e_n, ..., e_2, e_1] # tal que e_1 es el estado inicial y para cada i (2 <= i <= n), e_i es un # sucesor de e_(i-1). Nodo = list[Estado] # inicial es el nodo inicial en el que todos están en la orilla # izquierda. inicial: Nodo = [(I,I,I,I)] # esFinal(n) se verifica si n es un nodo final; es decir, su primer # elemento es el estado final. Por ejemplo, # esFinal([(D,D,D,D),(I,I,I,I)]) == True # esFinal([(I,I,D,I),(I,I,I,I)]) == False def esFinal(n: Nodo) -> bool: return n[0] == (D,D,D,D) # sucesores(n) es la lista de los sucesores del nodo n. Por ejemplo, # >>> sucesores([(I,I,D,I),(D,I,D,I),(I,I,I,I)]) # [[(D, D, D, I), (I, I, D, I), (D, I, D, I), (I, I, I, I)], # [(D, I, D, D), (I, I, D, I), (D, I, D, I), (I, I, I, I)]] def sucesores(n: Nodo) -> list[Nodo]: e, *es = n return [[e1] + n for e1 in sucesoresE(e) if e1 not in es] def granjero() -> list[list[Estado]]: return [list(reversed(es)) for es in buscaProfundidad(sucesores, esFinal, inicial)] # # Verificación # # ============ def test_granjero() -> None: assert granjero() == \ [[(I,I,I,I),(D,I,D,I),(I,I,D,I),(D,I,D,D),(I,I,I,D),(D,D,I,D),(I,D,I,D),(D,D,D,D)], [(I,I,I,I),(D,I,D,I),(I,I,D,I),(D,D,D,I),(I,D,I,I),(D,D,I,D),(I,D,I,D),(D,D,D,D)]] print("Verificado") # La verificación es # >>> test_granjero() # Verificado
El algoritmo de Prim calcula un recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.
El algoritmo de Prim funciona de la siguiente manera:
Usando la búsqueda en escalada el tipo abstracto de datos de los grafos, definir la función
prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]
tal que prim g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Prim con bñusqueda en escalada. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por
g1, g2, g3, g4 :: Grafo Int Int
g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
(2,4,55),(2,5,32),
(3,4,61),(3,5,44),
(4,5,93)]
g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),
(2,4,12),(2,5,32),
(3,4,14),(3,5,44),
(4,5,93)]
g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
(2,3,7),
(3,4,8),(3,5,7),
(4,5,5),
(5,6,3),(5,7,9),
(6,7,11)]
g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
(2,3,7),
(3,4,8),(3,5,1),
(4,5,5),
(5,6,3),(5,7,9),
(6,7,11)]
entonces
prim g1 == [(2,4,55),(1,3,34),(2,5,32),(1,2,12)] prim g2 == [(2,5,32),(2,4,12),(1,2,13),(1,3,11)] prim g3 == [(5,7,9),(2,3,7),(5,4,5),(6,5,3),(1,6,6),(1,2,5)] prim g4 == [(5,7,9),(5,4,5),(5,3,1),(6,5,3),(1,6,6),(1,2,5)]
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
module Escalada_Prim where import BusquedaEnEscalada (buscaEscalada) import TAD.Grafo (Grafo, Orientacion (ND), aristaEn, creaGrafo, nodos, peso) import Data.Ix (Ix) import Data.List (delete) import Test.Hspec (Spec, hspec, it, shouldBe) g1, g2, g3, g4 :: Grafo Int Int g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78), (2,4,12),(2,5,32), (3,4,14),(3,5,44), (4,5,93)] g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,7), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,1), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] -- Una arista esta formada por dos vértices junto con su peso. type Arista a b = (a,a,b) -- Un estado (Estado (p,t,r,aem)) está formado por el peso p de la -- última arista añadida el árbol de expansión mínimo (aem), la lista t -- de nodos del grafo que están en el aem, la lista r de nodos del -- grafo que no están en el aem y el aem. type Estado a b = (b,[a],[a],[Arista a b]) -- (inicial g) es el estado inicial correspondiente al grafo g. inicial :: (Ix a, Num b, Ord b) => Grafo a b -> Estado a b inicial g = (0,[n],ns,[]) where (n:ns) = nodos g -- (esFinal e) se verifica si e es un estado final; es decir, si no -- queda ningún elemento en la lista de nodos sin colocar en el árbol de -- expansión mínimo. esFinal :: Estado a b -> Bool esFinal (_,_,[],_) = True esFinal _ = False -- (sucesores g e) es la lista de los sucesores del estado e en el -- grafo g. Por ejemplo, -- λ> sucesores g1 (0,[1],[2..5],[]) -- [(12,[2,1],[3,4,5],[(1,2,12)]), -- (34,[3,1],[2,4,5],[(1,3,34)]), -- (78,[5,1],[2,3,4],[(1,5,78)])] sucesores :: (Ix a, Num b, Eq b) => Grafo a b -> Estado a b -> [Estado a b] sucesores g (_,t,r,aem) = [(peso x y g, y:t, delete y r, (x,y,peso x y g):aem) | x <- t , y <- r, aristaEn g (x,y)] prim :: (Ix a, Num b, Ord b) => Grafo a b -> [Arista a b] prim g = sol where [(_,_,_,sol)] = buscaEscalada (sucesores g) esFinal (inicial g) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ prim g1 `shouldBe` [(2,4,55),(1,3,34),(2,5,32),(1,2,12)] it "e2" $ prim g2 `shouldBe` [(2,5,32),(2,4,12),(1,2,13),(1,3,11)] it "e3" $ prim g3 `shouldBe` [(5,7,9),(2,3,7),(5,4,5),(6,5,3),(1,6,6),(1,2,5)] it "e4" $ prim g4 `shouldBe` [(5,7,9),(5,4,5),(5,3,1),(6,5,3),(1,6,6),(1,2,5)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0043 seconds -- 4 examples, 0 failures
from typing import Optional from src.BusquedaEnEscalada import buscaEscalada from src.TAD.Grafo import (Grafo, Orientacion, Peso, Vertice, aristaEn, creaGrafo, nodos, peso) g1 = creaGrafo (Orientacion.ND, (1,5), [((1,2),12),((1,3),34),((1,5),78), ((2,4),55),((2,5),32), ((3,4),61),((3,5),44), ((4,5),93)]) g2 = creaGrafo (Orientacion.ND, (1,5), [((1,2),13),((1,3),11),((1,5),78), ((2,4),12),((2,5),32), ((3,4),14),((3,5),44), ((4,5),93)]) g3 = creaGrafo (Orientacion.ND, (1,7), [((1,2),5),((1,3),9),((1,5),15),((1,6),6), ((2,3),7), ((3,4),8),((3,5),7), ((4,5),5), ((5,6),3),((5,7),9), ((6,7),11)]) g4 = creaGrafo (Orientacion.ND, (1,7), [((1,2),5),((1,3),9),((1,5),15),((1,6),6), ((2,3),7), ((3,4),8),((3,5),1), ((4,5),5), ((5,6),3),((5,7),9), ((6,7),11)]) Arista = tuple[tuple[Vertice, Vertice], Peso] # Un nodo (Estado (p,t,r,aem)) está formado por el peso p de la última # arista añadida el árbol de expansión mínimo (aem), la lista t # de nodos del grafo que están en el aem, la lista r de nodos del # grafo que no están en el aem y el aem. Estado = tuple[Peso, list[Vertice], list[Vertice], list[Arista]] # inicial(g) es el estado inicial correspondiente al grafo g. def inicial(g: Grafo) -> Estado: n, *ns = nodos(g) return (0, [n], ns, []) # esFinal(e) se verifica si e es un estado final; es decir, si no # queda ningún elemento en la lista de nodos sin colocar en el árbol de # expansión mínimo. def esFinal(e: Estado) -> bool: return e[2] == [] # sucesores(g, e) es la lista de los sucesores del estado e en el # grafo g. Por ejemplo, # λ> sucesores(g1, (0,[1],[2,3,4,5],[])) # [(12,[2,1],[3,4,5],[(1,2,12)]), # (34,[3,1],[2,4,5],[(1,3,34)]), # (78,[5,1],[2,3,4],[(1,5,78)])] def sucesores(g: Grafo, e: Estado) -> list[Estado]: (_,t,r,aem) = e return [(peso(x, y, g), [y] + t, [x for x in r if x != y], [((x,y),peso(x, y, g))] + aem) for x in t for y in r if aristaEn(g, (x, y))] def prim(g: Grafo) -> Optional[list[Arista]]: r = buscaEscalada(lambda e: sucesores(g, e), esFinal, inicial(g)) if r is None: return None return r[3] # Verificación # ============ def test_prim() -> None: assert prim(g1) == [((2,4),55),((1,3),34),((2,5),32),((1,2),12)] assert prim(g2) == [((2,5),32),((2,4),12),((1,2),13),((1,3),11)] assert prim(g3) == [((5,7),9),((2,3),7),((5,4),5),((6,5),3),((1,6),6),((1,2),5)] assert prim(g4) == [((5,7),9),((5,4),5),((5,3),1),((6,5),3),((1,6),6),((1,2),5)] print("Verificado") # La verificación es # >>> test_prim() # Verificado
El problema del cambio de monedas consiste en determinar conseguir una cantidad usando el menor número de monedas disponibles. Se supone que se posee un número ilimitado de monedas de 1, 2, 5, 10, 20, 50 y 100 euros. Por ejemplo, para conseguir 199 se necesitan como mínimo 7 monedas (129 = 2 + 2 + 5 + 20 + 20 + 50 + 100).
En la representación se usarán los siguientes tipos:
Moneda, que es un número entero representado el valor de la monedaSolucion, que es una lista de monedas cuya suma es la cantidad
deseada y no nay ninguna lista más corta con la misma suma.Usando la búsqueda en escalada, definir la función
cambio :: Int -> Solucion
tal que (cambio n) es la solución del problema de las monedas, para obtener la cantidad n, por búsqueda en escalada. Por ejemplo,
cambio 199 == [2,2,5,20,20,50,100]
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
module Escalada_Monedas where import BusquedaEnEscalada import Test.Hspec (Spec, hspec, it, shouldBe) -- Las monedas son números enteros. type Moneda = Int -- monedas es la lista del tipo de monedas disponibles. Se supone que -- hay un número infinito de monedas de cada tipo. monedas :: [Moneda] monedas = [1,2,5,10,20,50,100] -- Las soluciones son listas de monedas. type Solucion = [Moneda] -- Los estados son pares formados por la cantidad que falta y la lista -- de monedas usadas. type Estado = (Int, [Moneda]) -- (inicial n) es el estado inicial del problema de las monedas, para -- obtener la cantidad n. inicial :: Int -> Estado inicial n = (n, []) -- (esFinal e) se verifica si e es un estado final del problema -- de las monedas. esFinal :: Estado -> Bool esFinal (v,_) = v == 0 -- (sucesores e) es la lista de los sucesores del estado e en el -- problema de las monedas. Por ejemplo, -- λ> sucesores (199,[]) -- [(198,[1]),(197,[2]),(194,[5]),(189,[10]), -- (179,[20]),(149,[50]),(99,[100])] sucesores :: Estado -> [Estado] sucesores (r,p) = [(r-c,c:p) | c <- monedas, r-c >= 0] cambio :: Int -> Solucion cambio n = snd (head (buscaEscalada sucesores esFinal (inicial n))) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ cambio 199 `shouldBe` [2,2,5,20,20,50,100] -- La verificación es -- λ> verifica -- -- e1 -- -- Finished in 0.0003 seconds -- 1 example, 0 failures
from typing import Optional from src.BusquedaEnEscalada import buscaEscalada # Las monedas son números enteros. Moneda = int # monedas es la lista del tipo de monedas disponibles. Se supone que # hay un número infinito de monedas de cada tipo. monedas: list[Moneda] = [1,2,5,10,20,50,100] # Las soluciones son listas de monedas. Solucion = list[Moneda] # Los estados son pares formados por la cantidad que falta y la lista # de monedas usadas. Estado = tuple[int, list[Moneda]] # inicial(n) es el estado inicial del problema de las monedas, para # obtener la cantidad n. def inicial(n: int) -> Estado: return (n, []) # esFinal(e) se verifica si e es un estado final del problema # de las monedas. def esFinal(e: Estado) -> bool: return e[0] == 0 # sucesores(e) es la lista de los sucesores del estado e en el # problema de las monedas. Por ejemplo, # λ> sucesores((199,[])) # [(198,[1]),(197,[2]),(194,[5]),(189,[10]), # (179,[20]),(149,[50]),(99,[100])] def sucesores(e: Estado) -> list[Estado]: (r,p) = e return [(r - c, [c] + p) for c in monedas if r - c >= 0] def cambio(n: int) -> Optional[Solucion]: r = buscaEscalada(sucesores, esFinal, inicial(n)) if r is None: return None return r[1] # Verificación # ============ def test_monedas() -> None: assert cambio(199) == [2,2,5,20,20,50,100] # La verificación es # src> poetry run pytest -q Escalada_Monedas.py # 1 passed in 0.12s
En la búsqueda en escalada se supone que los estados están mediante una función, la heurística, que es una estimación de su coste para llegar a un estado final.
Definir la función
buscaEscalada :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]
tal que (buscaEscalada s o e) es la lista de soluciones del problema de espacio de estado definido por la función sucesores s, el objetivo o y estado inicial e, obtenidas buscando en escalada.
Nota: La búsqueda en escalada se aplica en el problema de las monedas.
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
module BusquedaEnEscalada (buscaEscalada) where import TAD.ColaDePrioridad (esVacia, inserta, primero, vacia) buscaEscalada :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n] buscaEscalada sucesores esFinal x = busca' (inserta x vacia) where busca' c | esVacia c = [] | esFinal (primero c) = [primero c] | otherwise = busca' (foldr inserta vacia (sucesores (primero c)))
from __future__ import annotations from abc import abstractmethod from functools import reduce from typing import Callable, Optional, Protocol, TypeVar from src.TAD.ColaDePrioridad import (CPrioridad, esVacia, inserta, primero, vacia) class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) def buscaEscalada(sucesores: Callable[[A], list[A]], esFinal: Callable[[A], bool], inicial: A) -> Optional[A]: c: CPrioridad[A] = inserta(inicial, vacia()) while not esVacia(c): x = primero(c) if esFinal(x): return x c = reduce(lambda x, y: inserta(y, x), sucesores(x), vacia()) return None
Para el 8-puzzle se usa un cajón cuadrado en el que hay situados bloques cuadrados. El cuadrado restante está sin rellenar. Cada bloque tiene un número. Un bloque adyacente al hueco puede deslizarse hacia él. El juego consiste en transformar la posición inicial en la posición final mediante el deslizamiento de los bloques. En particular, consideramos el estado inicial y final siguientes:
+---+---+---+ +---+---+---+ | | 1 | 3 | | 1 | 2 | 3 | +---+---+---+ +---+---+---+ | 8 | 2 | 4 | | 8 | | 4 | +---+---+---+ +---+---+---+ | 7 | 5 | 5 | | 7 | 6 | 5 | +---+---+---+ +---+---+---+ Estado inicial Estado final
Para solucionar el problema se definen los siguientes tipos:
Tablero es una matriz de número enteros (que representan las piezas en
cada posición y el 0 representa el hueco):type Tablero = Matrix Int
Estado es una listas de tableros [t_n,...,t_1] tal que t_i es un
sucesor de t_(i-1).newtype Estado = Est [Tablero] deriving Show
Usando el procedimiento de búsqueda por primero el mejor, definir la función
solucion_8puzzle :: Tablero -> [Tablero]
tal que (solucion_8puzzle t) es la solución del problema del problema del 8 puzzle a partir del tablero t. Por ejemplo,
λ> solucion_8puzzle (fromLists [[0,1,3],[8,2,4],[7,6,5]])
[┌ ┐ ┌ ┐ ┌ ┐
│ 0 1 3 │ │ 1 0 3 │ │ 1 2 3 │
│ 8 2 4 │ │ 8 2 4 │ │ 8 0 4 │
│ 7 6 5 │ │ 7 6 5 │ │ 7 6 5 │
└ ┘, └ ┘, └ ┘]
λ> length (solucion_8puzzle (fromLists [[2,6,3],[5,0,4],[1,7,8]]))
21
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
module BPM_8Puzzle where import BusquedaPrimeroElMejor (buscaPM) import Data.Matrix (Matrix, (!), fromLists, setElem, toLists) import Test.Hspec (Spec, hspec, it, shouldBe) type Tablero = Matrix Int newtype Estado = Est [Tablero] deriving (Eq, Show) solucion_8puzzle :: Tablero -> [Tablero] solucion_8puzzle t = reverse ts where (Est ts) = head (buscaPM sucesores esFinal (inicial t)) -- Estado inicial -- ============== -- (inicial t) es el estado inicial del problema del 8 puzzle a partir del -- tablero t. inicial :: Tablero -> Estado inicial t = Est [t] -- Estado final -- ============ -- (esFinal e) se verifica si e es un estado final. esFinal :: Estado -> Bool esFinal (Est (n:_)) = n == tableroFinal -- tableroFinal es el estado tablero final del 8 puzzle. tableroFinal :: Tablero tableroFinal = fromLists [[1,2,3], [8,0,4], [7,6,5]] -- Sucesores -- ========= -- (sucesores e) es la lista de sucesores del estado e. Por ejemplo, -- λ> sucesores (Est [fromLists [[2,1,3],[8,0,4],[7,6,5]]]) -- [Est [┌ ┐ ┌ ┐ -- │ 2 0 3 │ │ 2 1 3 │ -- │ 8 1 4 │ │ 8 0 4 │ -- │ 7 6 5 │ │ 7 6 5 │ -- └ ┘, └ ┘], -- Est [┌ ┐ ┌ ┐ -- │ 2 1 3 │ │ 2 1 3 │ -- │ 8 6 4 │ │ 8 0 4 │ -- │ 7 0 5 │ │ 7 6 5 │ -- └ ┘, └ ┘], -- Est [┌ ┐ ┌ ┐ -- │ 2 1 3 │ │ 2 1 3 │ -- │ 0 8 4 │ │ 8 0 4 │ -- │ 7 6 5 │ │ 7 6 5 │ -- └ ┘, └ ┘], -- Est [┌ ┐ ┌ ┐ -- │ 2 1 3 │ │ 2 1 3 │ -- │ 8 4 0 │ │ 8 0 4 │ -- │ 7 6 5 │ │ 7 6 5 │ -- └ ┘, └ ┘]] sucesores :: Estado -> [Estado] sucesores (Est e@(t:_)) = [Est (t':e) | t' <- tablerosSucesores t, t' `notElem` e] -- (tablerosSucesores t) es la lista de los tableros sucesores del -- tablero t. Por ejemplo, -- λ> tablerosSucesores (fromLists [[2,1,3],[8,0,4],[7,6,5]]) -- [┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ -- │ 2 0 3 │ │ 2 1 3 │ │ 2 1 3 │ │ 2 1 3 │ -- │ 8 1 4 │ │ 8 6 4 │ │ 0 8 4 │ │ 8 4 0 │ -- │ 7 6 5 │ │ 7 0 5 │ │ 7 6 5 │ │ 7 6 5 │ -- └ ┘, └ ┘, └ ┘, └ ┘] tablerosSucesores :: Tablero -> [Tablero] tablerosSucesores t = [intercambia t p q | q <- posicionesVecinas p] where p = posicionHueco t -- Una posición es un par de enteros. type Posicion = (Int,Int) -- (posicionesVecinas p) son las posiciones de la matriz cuadrada de -- dimensión 3 que se encuentran encima, abajo, a la izquierda y a la -- derecha de los posición p. Por ejemplo, -- λ> posicionesVecinas (2,2) -- [(1,2),(3,2),(2,1),(2,3)] -- λ> posicionesVecinas (1,2) -- [(2,2),(1,1),(1,3)] -- λ> posicionesVecinas (1,1) -- [(2,1),(1,2)] posicionesVecinas :: Posicion -> [Posicion] posicionesVecinas (i,j) = [(i-1,j) | i > 1] ++ [(i+1,j) | i < 3] ++ [(i,j-1) | j > 1] ++ [(i,j+1) | j < 3] -- (posicionHueco t) es la posición del hueco en el tablero t. Por -- ejemplo, -- λ> posicionHueco (fromLists [[2,1,3],[8,0,4],[7,6,5]]) -- (2,2) posicionHueco :: Tablero -> Posicion posicionHueco t = posicionElemento t 0 -- (posicionElemento t a) es la posición de elemento a en el tablero -- t. Por ejemplo, -- λ> posicionElemento (fromLists [[2,1,3],[8,0,4],[7,6,5]]) 4 -- (2,3) posicionElemento :: Tablero -> Int -> Posicion posicionElemento t a = head [(i,j) | i <- [1..3], j <- [1..3], t ! (i,j) == a] -- (intercambia t p1 p2) es el tablero obtenido intercambiando en t los -- elementos que se encuentran en las posiciones p1 y p2. Por ejemplo, -- λ> intercambia (fromLists [[2,1,3],[8,0,4],[7,6,5]]) (1,2) (2,2) -- ┌ ┐ -- │ 2 0 3 │ -- │ 8 1 4 │ -- │ 7 6 5 │ -- └ ┘ intercambia :: Tablero -> Posicion -> Posicion -> Tablero intercambia t p1 p2 = setElem a2 p1 (setElem a1 p2 t) where a1 = t ! p1 a2 = t ! p2 -- Heurística -- ========== -- (heuristica t) es la suma de la distancia Manhatan desde la posición de -- cada objeto del tablero a su posición en el tablero final. Por -- ejemplo, -- λ> heuristica (fromLists [[0,1,3],[8,2,4],[7,6,5]]) -- 4 heuristica :: Tablero -> Int heuristica t = sum [distancia (posicionElemento t i) (posicionElemento tableroFinal i) | i <- [0..8]] -- (distancia p1 p2) es la distancia Manhatan entre las posiciones p1 y -- p2. Por ejemplo, -- distancia (2,7) (4,1) == 8 distancia :: Posicion -> Posicion -> Int distancia (x1,y1) (x2,y2) = abs (x1-x2) + abs (y1-y2) -- Comparación de estados -- ====================== -- Un estado es menor o igual que otro si tiene la heurística de su -- primer tablero es menor o que la del segundo o so iguales y el -- primero es más corto. instance Ord Estado where Est (t1:ts1) <= Est (t2:ts2) = (heuristica t1 < heuristica t2) || ((heuristica t1 == heuristica t2) && (length ts1 <= length ts2)) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ map toLists (solucion_8puzzle (fromLists [[0,1,3],[8,2,4],[7,6,5]])) `shouldBe` [[[0,1,3], [8,2,4], [7,6,5]], [[1,0,3], [8,2,4], [7,6,5]], [[1,2,3], [8,0,4], [7,6,5]]] it "e2" $ length (solucion_8puzzle (fromLists [[2,6,3],[5,0,4],[1,7,8]])) `shouldBe` 21 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.1361 seconds -- 2 examples, 0 failures
from copy import deepcopy from typing import Optional from src.BusquedaPrimeroElMejor import buscaPM Tablero = list[list[int]] # Tablero final # ============= # tableroFinal es el tablero final del 8 puzzle. tableroFinal: Tablero = [[1,2,3], [8,0,4], [7,6,5]] # Posiciones # ========== # Una posición es un par de enteros. Posicion = tuple[int,int] # Heurística # ========== # distancia(p1, p2) es la distancia Manhatan entre las posiciones p1 y # p2. Por ejemplo, # >>> distancia((2,7), (4,1)) # 8 def distancia(p1: Posicion, p2: Posicion) -> int: (x1, y1) = p1 (x2, y2) = p2 return abs(x1-x2) + abs (y1-y2) # posicionElemento(t, a) es la posición de elemento a en el tablero # t. Por ejemplo, # λ> posicionElemento([[2,1,3],[8,0,4],[7,6,5]], 4) # (1, 2) def posicionElemento(t: Tablero, a: int) -> Posicion: for i in range(0, 3): for j in range(0, 3): if t[i][j] == a: return (i, j) return (4, 4) # posicionHueco(t) es la posición del hueco en el tablero t. Por # ejemplo, # >>> posicionHueco([[2,1,3],[8,0,4],[7,6,5]]) # (1, 1) def posicionHueco(t: Tablero) -> Posicion: return posicionElemento(t, 0) # heuristica(t) es la suma de la distancia Manhatan desde la posición de # cada objeto del tablero a su posición en el tablero final. Por # ejemplo, # >>> heuristica([[0,1,3],[8,2,4],[7,6,5]]) # 4 def heuristica(t: Tablero) -> int: return sum((distancia(posicionElemento(t, i), posicionElemento(tableroFinal, i)) for i in range(0, 10))) # Estados # ======= # Un estado es una tupla (h, n, ts), donde ts es una listas de tableros # [t_n,...,t_1] tal que t_i es un sucesor de t_(i-1) y h es la # heurística de t_n. Estado = tuple[int, int, list[Tablero]] # Estado inicial # ============== # inicial(t) es el estado inicial del problema del 8 puzzle a partir del # tablero t. def inicial(t: Tablero) -> Estado: return (heuristica(t), 1, [t]) # Estado final # ============ # esFinal(e) se verifica si e es un estado final. def esFinal(e: Estado) -> bool: (_, _, ts) = e return ts[0] == tableroFinal # Sucesores # ========= # posicionesVecinas(p) son las posiciones de la matriz cuadrada de # dimensión 3 que se encuentran encima, abajo, a la izquierda y a la # derecha de los posición p. Por ejemplo, # >>> posicionesVecinas((1,1)) # [(0, 1), (2, 1), (1, 0), (1, 2)] # >>> posicionesVecinas((0,1)) # [(1, 1), (0, 0), (0, 2)] # >>> posicionesVecinas((0,0)) # [(1, 0), (0, 1)] def posicionesVecinas(p: Posicion) -> list[Posicion]: (i, j) = p vecinas = [] if i > 0: vecinas.append((i - 1, j)) if i < 2: vecinas.append((i + 1, j)) if j > 0: vecinas.append((i, j - 1)) if j < 2: vecinas.append((i, j + 1)) return vecinas # intercambia(t,p1, p2) es el tablero obtenido intercambiando en t los # elementos que se encuentran en las posiciones p1 y p2. Por ejemplo, # >>> intercambia([[2,1,3],[8,0,4],[7,6,5]], (0,1), (1,1)) # [[2, 0, 3], [8, 1, 4], [7, 6, 5]] def intercambia(t: Tablero, p1: Posicion, p2: Posicion) -> Tablero: (i1, j1) = p1 (i2, j2) = p2 t1 = deepcopy(t) a1 = t1[i1][j1] a2 = t1[i2][j2] t1[i1][j1] = a2 t1[i2][j2] = a1 return t1 # tablerosSucesores(t) es la lista de los tablrtos sucesores del # tablero t. Por ejemplo, # >>> tablerosSucesores([[2,1,3],[8,0,4],[7,6,5]]) # [[[2, 0, 3], [8, 1, 4], [7, 6, 5]], # [[2, 1, 3], [8, 6, 4], [7, 0, 5]], # [[2, 1, 3], [0, 8, 4], [7, 6, 5]], # [[2, 1, 3], [8, 4, 0], [7, 6, 5]]] def tablerosSucesores(t: Tablero) -> list[Tablero]: p = posicionHueco(t) return [intercambia(t, p, q) for q in posicionesVecinas(p)] # (sucesores e) es la lista de sucesores del estado e. Por ejemplo, # >>> t1 = [[0,1,3],[8,2,4],[7,6,5]] # >>> es = sucesores((heuristica(t1), 1, [t1])) # >>> es # [(4, 2, [[[8, 1, 3], # [0, 2, 4], # [7, 6, 5]], # [[0, 1, 3], # [8, 2, 4], # [7, 6, 5]]]), # (2, 2, [[[1, 0, 3], # [8, 2, 4], # [7, 6, 5]], # [[0, 1, 3], # [8, 2, 4], # [7, 6, 5]]])] # >>> sucesores(es[1]) # [(0, 3, [[[1, 2, 3], # [8, 0, 4], # [7, 6, 5]], # [[1, 0, 3], # [8, 2, 4], # [7, 6, 5]], # [[0, 1, 3], # [8, 2, 4], # [7, 6, 5]]]), # (4, 3, [[[1, 3, 0], # [8, 2, 4], # [7, 6, 5]], # [[1, 0, 3], # [8, 2, 4], # [7, 6, 5]], # [[0, 1, 3], # [8, 2, 4], # [7, 6, 5]]])] def sucesores(e: Estado) -> list[Estado]: (_, n, ts) = e return [(heuristica(t1), n+1, [t1] + ts) for t1 in tablerosSucesores(ts[0]) if t1 not in ts] # Solución # ======== def solucion_8puzzle(t: Tablero) -> Optional[list[Tablero]]: r = buscaPM(sucesores, esFinal, inicial(t)) if r is None: return None (_, _, ts) = r ts.reverse() return ts # Verificación # ============ def test_8puzzle() -> None: assert solucion_8puzzle([[8,1,3],[0,2,4],[7,6,5]]) == \ [[[8, 1, 3], [0, 2, 4], [7, 6, 5]], [[0, 1, 3], [8, 2, 4], [7, 6, 5]], [[1, 0, 3], [8, 2, 4], [7, 6, 5]], [[1, 2, 3], [8, 0, 4], [7, 6, 5]]] # La verificación es # src> poetry run pytest -q BPM_8Puzzle.py # 1 passed in 0.10s
En la búsqueda por primero el mejor se supone que los estados están ordenados mediante una función, la heurística, que es una rstimación de su coste para llegar a un estado final.
Definir la función
buscaPM :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]
tal que buscaPM s o e es la lista de soluciones del problema de espacio de estado definido por la función sucesores s, el objetivo o y estado inicial e, obtenidas buscando por primero el mejor.
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
module BusquedaPrimeroElMejor (buscaPM) where import TAD.ColaDePrioridad (esVacia, inserta, primero, resto, vacia) buscaPM :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n] buscaPM sucesores esFinal x = busca' (inserta x vacia) where busca' c | esVacia c = [] | esFinal (primero c) = primero c : busca' (resto c) | otherwise = busca' (foldr inserta (resto c) (sucesores (primero c)))
from __future__ import annotations from abc import abstractmethod from functools import reduce from typing import Callable, Optional, Protocol, TypeVar from src.TAD.ColaDePrioridad import (CPrioridad, esVacia, inserta, primero, resto, vacia) class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) def buscaPM(sucesores: Callable[[A], list[A]], esFinal: Callable[[A], bool], inicial: A) -> Optional[A]: c: CPrioridad[A] = inserta(inicial, vacia()) while not esVacia(c): if esFinal(primero(c)): return primero(c) es = sucesores(primero(c)) c = reduce(lambda x, y: inserta(y, x), es, resto(c)) return None
Una cola de prioridad es una cola en la que cada elemento tiene asociada una prioridad. La operación de extracción siempre elige el elemento de menor prioridad.
Las operaciones que definen a tipo abstracto de datos (TAD) de las colas de prioridad (cuyos elementos son del tipo a) son las siguientes:
vacia :: Ord a => CPrioridad a inserta :: Ord a => a -> CPrioridad a -> CPrioridad a primero :: Ord a => CPrioridad a -> a resto :: Ord a => CPrioridad a -> CPrioridad a esVacia :: Ord a => CPrioridad a -> Bool
tales que
Las operaciones tienen que verificar las siguientes propiedades:
El TAD de las colas de prioridadd se encuentra en el módulo ColaDePrioridad.hs cuyo contenido es el siguiente:
module TAD.ColaDePrioridad (CPrioridad, vacia, -- Ord a => CPrioridad a inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a primero, -- Ord a => CPrioridad a -> a resto, -- Ord a => CPrioridad a -> CPrioridad a esVacia, -- Ord a => CPrioridad a -> Bool ) where import TAD.ColaDePrioridadConListas
Para usar el TAD hay que usar una implementación concreta. En principio, solo considearemos una que usa las listas.
La implementación se encuentra en el módulo ColaDePrioridadConListas.hs cuyo contenido es el siguiente:
{-# LANGUAGE FlexibleInstances #-} {-# OPTIONS_GHC -fno-warn-unused-top-binds #-} module TAD.ColaDePrioridadConListas (CPrioridad, vacia, -- Ord a => CPrioridad a inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a primero, -- Ord a => CPrioridad a -> a resto, -- Ord a => CPrioridad a -> CPrioridad a esVacia, -- Ord a => CPrioridad a -> Bool ) where import Test.QuickCheck -- Colas de prioridad mediante listas. newtype CPrioridad a = CP [a] deriving Eq -- (escribeColaDePrioridad c) es la cadena correspondiente a la cola de -- prioridad c. Por ejemplo, -- λ> escribeColaDePrioridad (inserta 5 (inserta 2 (inserta 3 vacia))) -- "2 | 3 | 5" escribeColaDePrioridad :: Show a => CPrioridad a -> String escribeColaDePrioridad (CP []) = "-" escribeColaDePrioridad (CP [x]) = show x escribeColaDePrioridad (CP (x:xs)) = show x ++ " | " ++ escribeColaDePrioridad (CP xs) -- Procedimiento de escritura de colas de prioridad. instance Show a => Show (CPrioridad a) where show = escribeColaDePrioridad -- Ejemplo de cola de prioridad -- λ> inserta 5 (inserta 2 (inserta 3 vacia)) -- 2 | 3 | 5 -- vacia es la cola de prioridad vacía. Por ejemplo, -- λ> vacia -- CP [] vacia :: Ord a => CPrioridad a vacia = CP [] -- (inserta x c) es la cola obtenida añadiendo el elemento x a la cola -- de prioridad c. Por ejemplo, -- λ> inserta 5 (foldr inserta vacia [3,1,7,2,9]) -- 1 | 2 | 3 | 5 | 7 | 9 inserta :: Ord a => a -> CPrioridad a -> CPrioridad a inserta x (CP q) = CP (ins x q) where ins y [] = [y] ins y r@(e:r') | y < e = y:r | otherwise = e:ins y r' -- (primero c) es el primer elemento de la cola de prioridad c. Por -- ejemplo, -- primero (foldr inserta vacia [3,1,7,2,9]) == 1 primero :: Ord a => CPrioridad a -> a primero (CP(x:_)) = x primero _ = error "primero: cola de prioridad vacia" -- (resto c) es la cola de prioridad obtenida eliminando el primer -- elemento de la cola de prioridad c. Por ejemplo, -- λ> resto (foldr inserta vacia [3,1,7,2,9]) -- 2 | 3 | 7 | 9 resto :: Ord a => CPrioridad a -> CPrioridad a resto (CP (_:xs)) = CP xs resto _ = error "resto: cola de prioridad vacia" -- (esVacia c) se verifica si la cola de prioridad c es vacía. Por -- ejemplo, -- esVacia (foldr inserta vacia [3,1,7,2,9]) == False -- esVacia vacia == True esVacia :: Ord a => CPrioridad a -> Bool esVacia (CP xs) = null xs -- Generador de colas de prioridad -- =============================== -- genCPrioridad es un generador de colas de enteros. Por ejemplo, -- λ> sample genCPrioridad -- - -- 0 | 0 -- 4 -- -4 | -3 | 6 | 6 -- -7 | -6 | -2 | 0 -- -10 | -10 | -5 | 1 | 4 | 6 | 6 | 9 | 10 -- - -- -13 | -11 | -9 | -5 | -2 | -1 | 0 | 1 | 2 | 2 | 13 | 14 -- -15 | -13 | -13 | -5 | -3 | -1 | 3 | 5 | 7 | 9 | 9 | 14 | 16 -- - -- -17 | -15 | -14 | -5 | -2 | 1 | 1 | 2 | 5 | 7 genCPrioridad :: (Arbitrary a, Num a, Ord a) => Gen (CPrioridad a) genCPrioridad = do xs <- listOf arbitrary return (foldr inserta vacia xs) -- El tipo cola de prioridad es una instancia del arbitrario. instance (Arbitrary a, Num a, Ord a) => Arbitrary (CPrioridad a) where arbitrary = genCPrioridad -- Propiedades de las colas de prioridad -- ===================================== -- Propiedad. Si se añade dos elementos a una cola de prioridad se -- obtiene la misma cola de prioridad idependientemente del orden en -- que se añadan los elementos. prop_inserta_conmuta :: Int -> Int -> CPrioridad Int -> Bool prop_inserta_conmuta x y c = inserta x (inserta y c) == inserta y (inserta x c) -- Comprobación. -- λ> quickCheck prop_inserta_conmuta -- +++ OK, passed 100 tests. -- Propiedad. La cabeza de la cola de prioridad obtenida añadiendo un -- elemento x a la cola de prioridad vacía es x. prop_primero_inserta_vacia :: Int -> CPrioridad Int -> Bool prop_primero_inserta_vacia x _ = primero (inserta x vacia) == x -- Comprobación. -- λ> quickCheck prop_primero_inserta_vacia -- +++ OK, passed 100 tests. -- Propiedad. El primer elemento de una cola de prioridad c no cambia -- cuando se le añade un elemento mayor o igual que algún elemento de c. prop_primero_inserta :: Int -> Int -> CPrioridad Int -> Property prop_primero_inserta x y c = x <= y ==> primero (inserta y c') == primero c' where c' = inserta x c -- Comprobación. -- λ> quickCheck prop_primero_inserta -- +++ OK, passed 100 tests. -- Propiedad. El resto de añadir un elemento a la cola de prioridad -- vacía es la cola vacía. prop_resto_inserta_vacia :: Int -> Bool prop_resto_inserta_vacia x = resto (inserta x vacia) == vacia -- Comprobación. -- λ> quickCheck prop_resto_inserta_vacia -- +++ OK, passed 100 tests. -- Propiedad. El resto de la cola de prioridad obtenida añadiendo un -- elemento y a una cola c' (que tiene algún elemento menor o igual que -- y) es la cola que se obtiene añadiendo y al resto de c'. prop_resto_inserta :: Int -> Int -> CPrioridad Int -> Property prop_resto_inserta x y c = x <= y ==> resto (inserta y c') == inserta y (resto c') where c' = inserta x c -- Comprobación: -- λ> quickCheck prop_resto_inserta -- +++ OK, passed 100 tests. -- Propiedad. vacia es una cola vacía. prop_vacia_es_vacia :: Bool prop_vacia_es_vacia = esVacia (vacia :: CPrioridad Int) -- Comprobación. -- λ> quickCheck prop_vacia_es_vacia -- +++ OK, passed 100 tests. -- Propiedad. Si se añade un elemento a una cola de prioridad se obtiene -- una cola no vacía. prop_inserta_no_es_vacia :: Int -> CPrioridad Int -> Bool prop_inserta_no_es_vacia x c = not (esVacia (inserta x c)) -- Comprobación. -- λ> quickCheck prop_inserta_no_es_vacia -- +++ OK, passed 100 tests.
La implementación se encuentra en el módulo ColaDePrioridad.py cuyo contenido es el siguiente:
__all__ = [ 'CPrioridad', 'vacia', 'inserta', 'primero', 'resto', 'esVacia', ] from src.TAD.ColaDePrioridadConListas import (CPrioridad, esVacia, inserta, primero, resto, vacia)
Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos solo una que usa las listas.
La implementación se encuentra en el módulo ColaDePrioridadConListas.py en el que se define la clase CPrioridad con los siguientes métodos:
Por ejemplo,
>>> c = CPrioridad() >>> c - >>> c.inserta(5) >>> c.inserta(2) >>> c.inserta(3) >>> c.inserta(4) >>> c 2 | 3 | 4 | 5 >>> c.primero() 2 >>> c.resto() >>> c 3 | 4 | 5 >>> c.esVacia() False >>> c = CPrioridad() >>> c.esVacia() True
Además se definen las correspondientes funciones. Por ejemplo,
>>> vacia() - >>> inserta(4, inserta(3, inserta(2, inserta(5, vacia())))) 2 | 3 | 4 | 5 >>> primero (inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))) 2 >>> resto (inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))) 3 | 4 | 5 >>> esVacia(inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))) False >>> esVacia(vacia()) True
Finalmente, se define un generador aleatorio de colas de prioridad y se comprueba que las colas de prioridad cumplen las propiedades de su especificación.
from __future__ import annotations __all__ = [ 'CPrioridad', 'vacia', 'inserta', 'primero', 'resto', 'esVacia', ] from abc import abstractmethod from copy import deepcopy from dataclasses import dataclass, field from typing import Generic, Protocol, TypeVar from hypothesis import assume, given from hypothesis import strategies as st class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) # Clase de las colas de prioridad mediante listas # =============================================== @dataclass class CPrioridad(Generic[A]): _elementos: list[A] = field(default_factory=list) def __repr__(self) -> str: """ Devuelve una cadena con los elementos de la cola separados por " | ". Si la cola está vacía, devuelve "-". """ if not self._elementos: return '-' return ' | '.join(str(x) for x in self._elementos) def esVacia(self) -> bool: """ Comprueba si la cola está vacía. Devuelve True si la cola está vacía, False en caso contrario. """ return not self._elementos def inserta(self, x: A) -> None: """ Inserta el elemento x en la cola de prioridad. """ self._elementos.append(x) self._elementos.sort() def primero(self) -> A: """ Devuelve el primer elemento de la cola. """ return self._elementos[0] def resto(self) -> None: """ Elimina el primer elemento de la cola """ self._elementos.pop(0) # Funciones del tipo de las listas # ================================ def vacia() -> CPrioridad[A]: """ Crea y devuelve una cola vacía de tipo A. """ c: CPrioridad[A] = CPrioridad() return c def inserta(x: A, c: CPrioridad[A]) -> CPrioridad[A]: """ Inserta un elemento x en la cola c y devuelve una nueva cola con el elemento insertado. """ _aux = deepcopy(c) _aux.inserta(x) return _aux def esVacia(c: CPrioridad[A]) -> bool: """ Devuelve True si la cola está vacía, False si no lo está. """ return c.esVacia() def primero(c: CPrioridad[A]) -> A: """ Devuelve el primer elemento de la cola c. """ return c.primero() def resto(c: CPrioridad[A]) -> CPrioridad[A]: """ Elimina el primer elemento de la cola c y devuelve una copia de la cola resultante. """ _aux = deepcopy(c) _aux.resto() return _aux # Generador de colas de prioridad # =============================== def colaAleatoria() -> st.SearchStrategy[CPrioridad[int]]: """ Genera una estrategia de búsqueda para generar colas de enteros de forma aleatoria. Utiliza la librería Hypothesis para generar una lista de enteros y luego se convierte en una instancia de la clase cola. """ return st.lists(st.integers()).map(CPrioridad) # Comprobación de las propiedades de las colas # ============================================ # Las propiedades son @given(c=colaAleatoria(), x=st.integers(), y=st.integers()) def test_cola1(c: CPrioridad[int], x: int, y: int) -> None: assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c)) assert primero(inserta(x, vacia())) == x assert resto(inserta(x, vacia())) == vacia() assert esVacia(vacia()) assert not esVacia(inserta(x, c)) @given(c=colaAleatoria(), x=st.integers(), y=st.integers()) def test_cola2(c: CPrioridad[int], x: int, y: int) -> None: assume(not y < x) assert primero(inserta(y, (inserta(x, c)))) == \ primero(inserta(x,c)) assert resto(inserta(y, (inserta(x, c)))) == \ inserta(y, resto(inserta(x, c))) # La comprobación es # > poetry run pytest -q ColaDePrioridadConListas.py # 2 passed in 0.54s
Se tiene una mochila de capacidad de peso p y una lista de n para colocar en la mochila. Cada objeto i tiene un peso w(i) y un valor v(i). Considerando la posibilidad de colocar el mismo objeto varias veces en la mochila, el problema consiste en determinar la forma de colocar los objetos en la mochila sin sobrepasar la capacidad de la mochila colocando el máximo valor posible.
Para solucionar el problema se definen los siguientes tipos:
type SolMoch = [Objeto]
type Objeto = (Peso,Valor)
type Peso = Int
type Valor = Float
type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch)
Usando el procedimiento de búsqueda en profundidad, definir la función
mochila :: [Objeto] -> Peso -> (SolMoch,Valor)
tal que mochila os l es la solución del problema de la mochila para la lista de objetos os y el límite de capacidad l. Por ejemplo,
> mochila [(2,3),(3,5),(4,6),(5,10)] 8 ([(5,10.0),(3,5.0)],15.0) > mochila [(2,3),(3,5),(5,6)] 10 ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0) > mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35 ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0) > mochila [(2,2.8),(3,4.4),(5,6.1)] 10 ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
module BEE_Mochila where import BusquedaEnProfundidad (buscaProfundidad) import Data.List (sort) import Test.Hspec (Spec, hspec, it, shouldBe) type Peso = Int type Valor = Float type Objeto = (Peso,Valor) type SolMoch = [Objeto] type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch) mochila :: [Objeto] -> Peso -> (SolMoch,Valor) mochila os l = (sol,v) where (v,_,_,_,sol) = maximum (buscaProfundidad sucesoresMoch esObjetivoMoch (inicial os l)) -- (inicial os l) es el estado inicial del problema de la mochila -- para la lista de objetos os y el límite de capacidad l inicial :: [Objeto] -> Peso -> NodoMoch inicial os l = (0,0,l,sort os,[]) -- (sucesoresMoch e) es la lista de los sucesores del estado e en el -- problema de la mochila para la lista de objetos os y el límite de -- capacidad l. sucesoresMoch :: NodoMoch -> [NodoMoch] sucesoresMoch (v,p,l,os,solp) = [( v+v', p+p', l, [o | o@(p'',_) <- os, p''>=p'], (p',v'):solp ) | (p',v') <- os, p+p' <= l] -- (esObjetivoMoch e) se verifica si e es un estado final el problema de -- la mochila para la lista de objetos os y el límite de capacidad l . esObjetivoMoch :: NodoMoch -> Bool esObjetivoMoch (_,p,l,(p',_):_,_) = p+p'>l -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ mochila [(2,3),(3,5),(4,6),(5,10)] 8 `shouldBe` ([(5,10.0),(3,5.0)],15.0) it "e2" $ mochila [(2,3),(3,5),(5,6)] 10 `shouldBe` ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0) it "e3" $ mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35 `shouldBe` ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0) it "e4" $ mochila [(2,2.8),(3,4.4),(5,6.1)] 10 `shouldBe` ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4) -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0424 seconds -- 4 examples, 0 failures
from src.BusquedaEnProfundidad import buscaProfundidad Peso = int Valor = float Objeto = tuple[Peso, Valor] SolMoch = list[Objeto] NodoMoch = tuple[Valor, Peso, Peso, list[Objeto], SolMoch] # inicial(os, l) es el estado inicial del problema de la mochila # para la lista de objetos os y el límite de capacidad l def inicial(os: list[Objeto], l: Peso) -> NodoMoch: return (0,0,l,sorted(os),[]) # sucesoresMoch(e) es la lista de los sucesores del estado e en el # problema de la mochila para la lista de objetos os y el límite de # capacidad l. def sucesoresMoch(n: NodoMoch) -> list[NodoMoch]: (v,p,l,os,solp) = n return [( v+v1, p+p1, l, [(p2,v2) for (p2,v2) in os if p2 >= p1], [(p1,v1)] + solp ) for (p1,v1) in os if p + p1 <= l] # esObjetivoMoch(e) se verifica si e es un estado final el problema de # la mochila para la lista de objetos os y el límite de capacidad l . def esObjetivoMoch(e: NodoMoch) -> bool: (_, p, l, os, _) = e (p_, _) = os[0] return p + p_ > l def mochila(os: list[Objeto], l: Peso) -> tuple[SolMoch, Valor]: (v,_,_,_,sol) = max(buscaProfundidad(sucesoresMoch, esObjetivoMoch, inicial(os, l))) return (sol, v) # Verificación # ============ def test_Mochila() -> None: assert mochila([(2,3),(3,5),(4,6),(5,10)], 8) == \ ([(5,10.0),(3,5.0)],15.0) assert mochila([(2,3),(3,5),(5,6)], 10) == \ ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0) assert mochila([(2,2.8),(3,4.4),(5,6.1)], 10) == \ ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4) print("Verificado") # La verificación es # >>> test_Mochila() # Verificado
El problema de las n reinas consiste en colocar n reinas en un tablero cuadrado de dimensiones n por n de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal.
Las posiciones de las reinas en el tablero se representan por su columna y su fila.
type Columna = Int type Fila = Int
Una solución del problema de las n reinas es una lista de posiciones.
type SolNR = [(Columna,Fila)]
Usando el procedimiento de búsqueda en anchura, definir las funciones
solucionesNR :: Columna -> [SolNR] primeraSolucionNR :: Columna -> SolNR nSolucionesNR :: Columna -> Int
tales que
solucionesNR n es la lista de las soluciones del problema de las n reinas, por búsqueda de espacio de estados en anchura. Por ejemplo,take 3 (solucionesNR 8) [[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)], [(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)], [(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]]
primeraSolucionNR n es la primera solución del problema de las n reinas, por búsqueda en espacio de estados por anchura. Por ejemplo,λ> primeraSolucionNR 8 [(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)]
nSolucionesNR n es el número de soluciones del problema de las n reinas, por búsqueda en espacio de estados. Por ejemplo,nSolucionesNR 8 == 92
Las características de los problemas de espacios de estados son:
Definir la función
buscaAnchura :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool) -> nodo -> [nodo]
tal que buscaAnchura s o e es la lista de soluciones del problema de espacio de estado definido por la función sucesores s, el objetivo o y estado inicial e obtenidas mediante búsqueda en anchura.
Las características de los problemas de espacios de estados son:
Definir la función
buscaProfundidad :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool) -> nodo -> [nodo]
tal que buscaProfundidad s o e es la lista de soluciones del problema de espacio de estado definido por la función sucesores s, el objetivo o y estado inicial e obtenidas mediante búsqueda en profundidad.
Un poliominó es una figura geométrica plana formada conectando dos o más cuadrados por alguno de sus lados. Los cuadrados se conectan lado con lado, pero no se pueden conectar ni por sus vértices, ni juntando solo parte de un lado de un cuadrado con parte de un lado de otro. Si unimos dos cuadrados se obtiene un dominó, si se juntan tres cuadrados se construye un triominó.
Sólo existen dos triominós, el I-triomino (por tener forma de I) y el L-triominó (por su forma de L) como se observa en las siguientes figuras
X X X X XX
El rompecabeza del triominó consiste en cubrir un tablero cuadrado con 2^n filas y 2^n columnas, en el que se ha eliminado una casilla, con L-triominós de formas que cubran todas las casillas excepto la eliminada y los triominós no se solapen.
La casilla eliminada se representará con -1 y los L-triominós sucesiones de tres números consecutivos en forma de L. Con esta representación una solución del rompecabeza del triominó con 4 filas y la fila eliminada en la posición (4,4) es
( 3 3 2 2 ) ( 3 1 1 2 ) ( 4 1 5 5 ) ( 4 4 5 -1 )
Definir la función
triomino :: Int -> Posicion -> Tablero
tal que (triomino n p) es la solución, mediante divide y vencerás, del rompecabeza del triominó en un cuadrado nxn en el que se ha eliminado la casilla de la posición p. Por ejemplo,
λ> triomino 4 (4,4) ( 3 3 2 2 ) ( 3 1 1 2 ) ( 4 1 5 5 ) ( 4 4 5 -1 ) λ> triomino 4 (2,3) ( 3 3 2 2 ) ( 3 1 -1 2 ) ( 4 1 1 5 ) ( 4 4 5 5 ) λ> triomino 16 (5,6) ( 7 7 6 6 6 6 5 5 6 6 5 5 5 5 4 4 ) ( 7 5 5 6 6 4 4 5 6 4 4 5 5 3 3 4 ) ( 8 5 9 9 7 7 4 8 7 4 8 8 6 6 3 7 ) ( 8 8 9 3 3 7 8 8 7 7 8 2 2 6 7 7 ) ( 8 8 7 3 9 -1 8 8 7 7 6 6 2 8 7 7 ) ( 8 6 7 7 9 9 7 8 7 5 5 6 8 8 6 7 ) ( 9 6 6 10 10 7 7 11 8 8 5 9 9 6 6 10 ) ( 9 9 10 10 10 10 11 11 1 8 9 9 9 9 10 10 ) ( 8 8 7 7 7 7 6 1 1 9 8 8 8 8 7 7 ) ( 8 6 6 7 7 5 6 6 9 9 7 8 8 6 6 7 ) ( 9 6 10 10 8 5 5 9 10 7 7 11 9 9 6 10 ) ( 9 9 10 4 8 8 9 9 10 10 11 11 5 9 10 10 ) ( 9 9 8 4 4 10 9 9 10 10 9 5 5 11 10 10 ) ( 9 7 8 8 10 10 8 9 10 8 9 9 11 11 9 10 ) ( 10 7 7 11 11 8 8 12 11 8 8 12 12 9 9 13 ) ( 10 10 11 11 11 11 12 12 11 11 12 12 12 12 13 13 )
La técnica divide y vencerás consta de los siguientes pasos:
Definir la función
divideVenceras :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s
tal que divideVenceras ind resuelve divide combina pbInicial resuelve el problema pbInicial mediante la técnica de divide y vencerás, donde
ind pb se verifica si el problema pb es indivisibleresuelve pb es la solución del problema indivisible pb
divide pb es la lista de subproblemas de pb
combina pb ss es la combinación de las soluciones ss de los subproblemas del problema pb.pbInicial es el problema inicialUsando la función DivideVenceras, definir las funciones
ordenaPorMezcla :: Ord a => [a] -> [a] ordenaRapida :: Ord a => [a] -> [a]
tales que
ordenaPorMezcla xs es la lista obtenida ordenando xs por el procedimiento de ordenación por mezcla. Por ejemplo,λ> ordenaPorMezcla [3,1,4,1,5,9,2,8] [1,1,2,3,4,5,8,9]
ordenaRapida xs es la lista obtenida ordenando xs por el procedimiento de ordenación rápida. Por ejemplo,λ> ordenaRapida [3,1,4,1,5,9,2,8] [1,1,2,3,4,5,8,9]
El algoritmo de Prim calcula un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.
El algoritmo de Prim funciona de la siguiente manera:
Usando el tipo abstrado de datos de los grafos, definir la función
prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]
tal que prim g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Prim. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por
g1, g2, g3, g4 :: Grafo Int Int g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78), (2,4,12),(2,5,32), (3,4,14),(3,5,44), (4,5,93)] g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,7), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,1), (4,5,5), (5,6,3),(5,7,9), (6,7,11)]
entonces
prim g1 == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)] prim g2 == [(32,2,5),(12,2,4),(13,1,2),(11,1,3)] prim g3 == [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)]
El algoritmo de Kruskal calcula un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.
El algoritmo de Kruskal funciona de la siguiente manera:
Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo.
Usando el tipo abstrado de datos de los grafos, definir la función
kruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]
tal que kruskal g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Kruskal. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por
g1, g2, g3, g4 :: Grafo Int Int g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78), (2,4,12),(2,5,32), (3,4,14),(3,5,44), (4,5,93)] g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,7), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,1), (4,5,5), (5,6,3),(5,7,9), (6,7,11)]
entonces
kruskal g1 == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)] kruskal g2 == [(32,2,5),(13,1,2),(12,2,4),(11,1,3)] kruskal g3 == [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)] kruskal g4 == [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)]
Usando el tipo abstrado de datos de los grafos, definir la función
conectados :: Grafo Int Int -> Int -> Int -> Bool
tal que conectados g v1 v2 se verifica si los vértices v1 y v2 están conectados en el grafo g. Por ejemplo, si grafo1 es el grafo definido por
grafo1 :: Grafo Int Int grafo1 = creaGrafo' D (1,6) [(1,3),(1,5),(3,5),(5,1),(5,50), (2,4),(2,6),(4,6),(4,4),(6,4)]
entonces,
conectados grafo1 1 3 == True conectados grafo1 1 4 == False conectados grafo1 6 2 == False conectados grafo1 3 1 == True
Dado un grafo dirigido G, diremos que un nodo está aislado si o bien de dicho nodo no sale ninguna arista o bien no llega al nodo ninguna arista. Por ejemplo, en el siguiente grafo
grafo1 :: Grafo Int Int grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6), (5,4),(6,2),(6,5)]
podemos ver que del nodo 1 salen 3 aristas pero no llega ninguna, por lo que lo consideramos aislado. Así mismo, a los nodos 2 y 4 llegan aristas pero no sale ninguna, por tanto también estarán aislados.
Usando el tipo abstrado de datos de los grafos, definir la función
aislados :: (Ix v, Num p) => Grafo v p -> [v]
tal que aislados g es la lista de nodos aislados del grafo g. Por ejemplo,
aislados grafo1 == [1,2,4]
Un mapa se puede representar mediante un grafo donde los vértices son las regiones del mapa y hay una arista entre dos vértices si las correspondientes regiones son vecinas. Por ejemplo, el mapa siguiente
+----------+----------+ | 1 | 2 | +----+-----+-----+----+ | | | | | 3 | 4 | 5 | | | | | +----+-----+-----+----+ | 6 | 7 | +----------+----------+
se pueden representar por
mapa :: Grafo Int Int mapa = creaGrafo' ND (1,7) [(1,2),(1,3),(1,4),(2,4),(2,5),(3,4), (3,6),(4,5),(4,6),(4,7),(5,7),(6,7)]
Para colorear el mapa se dispone de 4 colores definidos por
data Color = A | B | C | D deriving (Eq, Show)
Usando el tipo abstrado de datos de los grafos, definir la función
correcta :: [(Int,Color)] -> Grafo Int Int -> Bool
tal que correcta ncs m se verifica si ncs es una coloración del mapa m tal que todos las regiones vecinas tienen colores distintos. Por ejemplo,
correcta [(1,A),(2,B),(3,B),(4,C),(5,A),(6,A),(7,B)] mapa == True correcta [(1,A),(2,B),(3,A),(4,C),(5,A),(6,A),(7,B)] mapa == False
Un grafo no dirigido G se dice conexo, si para cualquier par de vértices u y v en G, existe al menos una trayectoria (una sucesión de vértices adyacentes) de u a v.
Usando el tipo abstrado de datos de los grafos, definir la función
conexo :: (Ix a, Num p, Eq p) => Grafo a p -> Bool
tal que conexo g se verifica si el grafo g es conexo. Por ejemplo,
conexo (creaGrafo' ND (1,3) [(1,2),(3,2)]) == True conexo (creaGrafo' ND (1,4) [(1,2),(3,2),(4,1)]) == True conexo (creaGrafo' ND (1,4) [(1,2),(3,4)]) == False
Usando el tipo abstrado de datos de los grafos, definir la función
recorridoEnAnchura :: (Num p, Eq p, Ix v) => v -> Grafo v p -> [v]
tal que recorridoEnAnchura i g es el recorrido en anchura del grafo g desde el vértice i. Por ejemplo, en el grafo
+---> 2 <---+ | | | | 1 --> 3 --> 6 --> 5 | | | | +---> 4 <---------+
definido por
grafo1 :: Grafo Int Int grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)]
entonces
recorridoEnAnchura 1 grafo1 == [1,2,3,4,6,5]
Usando el tipo abstrado de datos de los grafos, definir la función
recorridoEnProfundidad :: (Num p, Eq p, Ix v) => v -> Grafo v p -> [v]
tal que recorridoEnProfundidad i g es el recorrido en profundidad del grafo g desde el vértice i. Por ejemplo, en el grafo
+---> 2 <---+ | | | | 1 --> 3 --> 6 --> 5 | | | | +---> 4 <---------+
definido por
grafo1 :: Grafo Int Int grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)]
entonces
recorridoEnProfundidad 1 grafo1 == [1,2,3,6,5,4]
En un grafo, la anchura de un nodo es el máximo de los absolutos de la diferencia entre el valor del nodo y los de sus adyacentes; y la anchura del grafo es la máxima anchura de sus nodos. Por ejemplo, en el grafo
grafo1 :: Grafo Int Int grafo1 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5), (2,4),(2,5), (3,4),(3,5), (4,5)]
su anchura es 4 y el nodo de máxima anchura es el 5.
Usando el tipo abstrado de datos de los grafos, definir la función
anchura :: Grafo Int Int -> Int
tal que (anchuraG g) es la anchura del grafo g. Por ejemplo,
anchura grafo1 == 4
Comprobar experimentalmente que la anchura del grafo ciclo de orden n es n-1.
Definir la función
recorridos :: [a] -> [[a]]
tal que recorridos xs es la lista de todos los posibles por el grafo cuyo conjunto de vértices es xs y cada vértice se encuentra conectado con todos los otros y los recorridos pasan por todos los vértices una vez y terminan en el vértice inicial. Por ejemplo,
λ> recorridos [2,5,3] [[2,5,3,2],[5,2,3,5],[3,5,2,3],[5,3,2,5],[3,2,5,3],[2,3,5,2]]
Un grafo k-regular es un grafo con todos sus vértices son de grado k.
Usando el tipo abstrado de datos de los grafos, definir la función
regularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int
tal que (regularidad g) es la regularidad de g. Por ejemplo,
regularidad (creaGrafo' ND (1,2) [(1,2),(2,3)]) == Just 1 regularidad (creaGrafo' D (1,2) [(1,2),(2,3)]) == Nothing regularidad (completo 4) == Just 3 regularidad (completo 5) == Just 4 regularidad (grafoCiclo 4) == Just 2 regularidad (grafoCiclo 5) == Just 2
Comprobar que el grafo completo de orden n es (n-1)-regular (para n de 1 a 20) y el grafo ciclo de orden n es 2-regular (para n de 3 a 20).
Un grafo regular es un grafo en el que todos sus vértices tienen el mismo grado.
Usando el tipo abstrado de datos de los grafos, definir la función
regular :: (Ix v,Num p) => Grafo v p -> Bool
tal que (regular g) se verifica si el grafo g es regular. Por ejemplo,
λ> regular (creaGrafo' D (1,3) [(1,2),(2,3),(3,1)]) True λ> regular (creaGrafo' ND (1,3) [(1,2),(2,3)]) False λ> regular (completo 4) True
Comprobar que los grafos completos son regulares.
En la teoría de grafos, se conoce como "Lema del apretón de manos" la siguiente propiedad: la suma de los grados de los vértices de g es el doble del número de aristas de g.
Comprobar con QuickCheck que para cualquier grafo g, se verifica dicha propiedad.
El grado de un vértice v de un grafo dirigido g, es el número aristas de g que contiene a v. Si g es no dirigido, el grado de un vértice v es el número de aristas incidentes en v, teniendo en cuenta que los lazos se cuentan dos veces.
Usando el tipo abstrado de datos de los grafos, definir la función
grado :: (Ix v,Num p) => Grafo v p -> v -> Int
tal que grado g v es el grado del vértice v en el grafo g. Por ejemplo,
g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)] g2 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)] g3 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)] g4 = creaGrafo' D (1,1) [(1,1)] g5 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)] g6 = creaGrafo' D (1,3) [(1,2),(1,3),(2,3),(3,3)] grado g1 5 == 4 grado g2 5 == 3 grado g2 1 == 3 grado g3 2 == 4 grado g3 1 == 2 grado g3 3 == 2 grado g4 1 == 2 grado g6 3 == 4 grado g6 3 == 4
Comprobar con QuickCheck que en todo grafo, el número de nodos de grado impar es par.
Definir un generador de grafos para comprobar propiedades de grafos con QuickCheck y hacer el tipo de los Grafos un subtipo de Arbutrary.
Usando el generador, con QuickCheck que para cualquier grafo g, las sumas de los grados positivos y la de los grados negativos de los vértices de g son iguales.
El grado positivo de un vértice v de un grafo g es el número de vértices de g adyacentes con v y su grado negativo es el número de vértices de g incidentes con v.
Usando el tipo abstrado de datos de los grafos, definir las funciones
gradoPos :: (Ix v,Num p) => Grafo v p -> v -> Int gradoNeg :: (Ix v,Num p) => Grafo v p -> v -> Int
tales que
+ gradoPos g v es el grado positivo del vértice v en el grafo g. Por ejemplo,
λ> g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)] λ> g2 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)] λ> gradoPos g1 5 4 λ> gradoPos g2 5 0 λ> gradoPos g2 1 3
gradoNeg g v es el grado negativo del vértice v en el grafo g. Por ejemplo,λ> gradoNeg g1 5 4 λ> gradoNeg g2 5 3 λ> gradoNeg g2 1 0
Usando el tipo abstrado de datos de los grafos, definir la función
nAristas :: (Ix v,Num p) => Grafo v p -> Int
tal que nAristas g es el número de aristas del grafo g. Si g es no dirigido, las aristas de v1 a v2 y de v2 a v1 sólo se cuentan una vez. Por ejemplo,
λ> g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)] λ> g2 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)] λ> g3 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)] λ> g4 = creaGrafo' ND (1,4) [(1,1),(1,2),(3,3)] λ> nAristas g1 8 λ> nAristas g2 7 λ> nAristas g3 4 λ> nAristas g4 3 λ> nAristas (completo 4) 6 λ> nAristas (completo 5) 10
Definir la función
prop_nAristasCompleto :: Int -> Bool
tal que prop_nAristasCompleto n se verifica si el número de aristas del grafo completo de orden n es n*(n-1)/2 y, usando la función, comprobar que la propiedad se cumple para n de 1 a 20.
Usando el tipo abstrado de datos de los grafos, definir las funciones
lazos :: (Ix v,Num p) => Grafo v p -> [(v,v)] nLazos :: (Ix v,Num p) => Grafo v p -> Int
tales que
lazos g es el conjunto de los lazos (es decir, aristas cuyos extremos son iguales) del grafo g. Por ejemplo,λ> ej1 = creaGrafo' D (1,3) [(1,1),(2,3),(3,2),(3,3)] λ> ej2 = creaGrafo' ND (1,3) [(2,3),(3,1)] λ> lazos ej1 [(1,1),(3,3)] λ> lazos ej2 []
nLazos g es el número de lazos del grafo g. Por ejemplo,λ> nLazos ej1 2 λ> nLazos ej2 0
En un un grafo g, los contiguos de un vértice v es el conjuntos de vértices x de g tales que x es adyacente o incidente con v.
Usando el tipo abstrado de datos de los grafos, definir la función,
contiguos :: (Ix v,Num p) => Grafo v p -> v -> [v]
tal que contiguos g v es el conjunto de los vértices de g contiguos con el vértice v. Por ejemplo,
λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)] λ> contiguos g1 1 [2,3] λ> contiguos g1 2 [2,1,3] λ> contiguos g1 3 [1,2] λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)] λ> contiguos g2 1 [2,3] λ> contiguos g2 2 [1,2,3] λ> contiguos g2 3 [1,2]
En un un grafo g, los incidentes de un vértice v es el conjuntos de vértices x de g para los que hay un arco (o una arista) de x a v; es decir, que v es adyacente a x.
Usando el tipo abstrado de datos de los grafos, definir la función,
incidentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]
tal que incidentes g v es la lista de los vértices incidentes en el vértice v. Por ejemplo,
λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)] λ> incidentes g1 1 [3] λ> incidentes g1 2 [1,2,3] λ> incidentes g1 3 [] λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)] λ> incidentes g2 1 [2,3] λ> incidentes g2 2 [1,2,3] λ> incidentes g2 3 [1,2]
Usando el tipo abstrado de datos de los grafos, definir la función,
nVertices :: (Ix v, Num p) => Grafo v p -> Int
tal que nVertices g es el número de vértices del grafo g. Por
ejemplo,
nVertices (creaGrafo' D (1,5) [(1,2),(3,1)]) == 5 nVertices (creaGrafo' ND (2,4) [(1,2),(3,1)]) == 3
El ciclo de orden n, C(n), es un grafo no dirigido cuyo conjunto de vértices es {1,...,n} y las aristas son
(1,2), (2,3), ..., (n-1,n), (n,1)
Usando el tipo abstrado de datos de los grafos, definir la función,
grafoCiclo :: Int -> Grafo Int Int
tal que (grafoCiclo n) es el grafo ciclo de orden n. Por ejemplo,
λ> grafoCiclo 3 G ND ([1,2,3],[(1,2),(1,3),(2,3)])
El grafo completo de orden n, K(n), es un grafo no dirigido cuyos conjunto de vértices es {1,..n} y tiene una arista entre cada par de vértices distintos.
Usando el tipo abstrado de datos de los grafos, definir la función,
completo :: Int -> Grafo Int Int
tal que completo n es el grafo completo de orden n. Por ejemplo,
λ> completo 4 G ND ([1,2,3,4],[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)])
Un grafo es una estructura que consta de un conjunto de vértices y un conjunto de aristas que conectan los vértices entre sí. Cada vértice representa una entidad o un elemento, y cada arista representa una relación o conexión entre dos vértices.
Por ejemplo,
12 1 -------- 2 | \78 /| | \ 32/ | | \ / | 34| 5 |55 | / \ | | /44 \ | | / 93\| 3 -------- 4 61
representa un grafo no dirigido, lo que significa que las aristas tienen una dirección específica. Cada arista tiene un peso asociado, que puede representar una medida o una valoración de la relación entre los vértices que conecta.
El grafo consta de cinco vértices numerados del 1 al 5. Las aristas especificadas en la lista indican las conexiones entre los vértices y sus respectivos pesos. Por ejemplo, la arista (1,2,12) indica que existe una conexión entre el vértice 1 y el vértice 2 con un peso de 12.
En el grafo representado, se pueden observar las conexiones entre los vértices de la siguiente manera:
Las operaciones del tipo abstracto de datos (TAD) de los grafos son
creaGrafo :: (Ix v, Num p, Ord v, Ord p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p creaGrafo' :: (Ix v, Num p, Ord v, Ord p) => Orientacion -> (v,v) -> [(v,v)] -> Grafo v p dirigido :: (Ix v,Num p) => (Grafo v p) -> Bool adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v] nodos :: (Ix v,Num p) => (Grafo v p) -> [v] aristas :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)] aristaEn :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool peso :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p
tales que
+ creaGrafo o cs as es un grafo (dirigido o no, según el de o), con el par de cotas cs y listas de aristas as (cada arista es un trío formado por los dos vértices y su peso).
+ creaGrafo' es la versión de creaGrafo para los grafos sin pesos.
+ dirigido g se verifica si g es dirigido.
+ nodos g es la lista de todos los nodos del grafo g.
+ aristas g es la lista de las aristas del grafo g.
+ adyacentes g v es la lista de los vértices adyacentes al nodo v en el grafo g.
+ aristaEn g a se verifica si a es una arista del grafo g.
+ peso v1 v2 g es el peso de la arista que une los vértices v1 y v2 en el grafo g.
Usando el TAD de los grafos, el grafo anterior se puede definir por
creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)]
con los siguientes argumentos:
Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes: + mediante lista de adyacencia, + mediante vector de adyacencia y + mediante matriz de adyacencia.
Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.
Utilizando el tipo abstracto de datos de los polinomios definir la función
factorizacion :: Polinomio Int -> [Polinomio Int]
tal que factorizacion p es la lista de la descomposición del polinomio p en factores obtenida mediante el regla de Ruffini. Por ejemplo,
λ> ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> ejPol1 x^5 + 5*x^2 + 4*x λ> factorizacion ejPol1 [1*x,1*x + 1,x^3 + -1*x^2 + 1*x + 4] λ> ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero))) λ> ejPol2 x^3 + 2*x^2 + -1*x + -2 λ> factorizacion ejPol2 [1*x + -1,1*x + 1,1*x + 2,1]
Utilizando el tipo abstracto de datos de los polinomios definir la función
raicesRuffini :: Polinomio Int -> [Int]
tal que raicesRuffini p es la lista de las raices enteras de p, calculadas usando el regla de Ruffini. Por ejemplo,
λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)) λ> ejPol1 3*x^4 + -5*x^2 + 3 λ> raicesRuffini ejPol1 [] λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> ejPol2 x^5 + 5*x^2 + 4*x λ> raicesRuffini ejPol2 [0,-1] λ> ejPol3 = consPol 4 6 (consPol 1 2 polCero) λ> ejPol3 6*x^4 + 2*x λ> raicesRuffini ejPol3 [0] λ> ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero))) λ> ejPol4 x^3 + 2*x^2 + -1*x + -2 λ> raicesRuffini ejPol4 [1,-1,-2]
Utilizando el tipo abstracto de datos de los polinomios definir la función
esRaizRuffini :: Int -> Polinomio Int -> Bool
tal que esRaizRuffini r p se verifica si r es una raiz de p, usando para ello el regla de Ruffini. Por ejemplo,
λ> ejPol = consPol 4 6 (consPol 1 2 polCero) λ> ejPol 6*x^4 + 2*x λ> esRaizRuffini 0 ejPol True λ> esRaizRuffini 1 ejPol False
Utilizando el tipo abstracto de datos de los polinomios definir las funciones
cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int restoRuffini :: Int -> Polinomio Int -> Int
tales que
cocienteRuffini r p es el cociente de dividir el polinomio p por el polinomio x-r. Por ejemplo:λ> ejPol = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero))) λ> ejPol x^3 + 2*x^2 + -1*x + -2 λ> cocienteRuffini 2 ejPol x^2 + 4*x + 7 λ> cocienteRuffini (-2) ejPol x^2 + -1 λ> cocienteRuffini 3 ejPol x^2 + 5*x + 14
restoRuffini r p es el resto de dividir el polinomio p por el polinomio x-r. Por ejemplo,λ> restoRuffini 2 ejPol 12 λ> restoRuffini (-2) ejPol 0 λ> restoRuffini 3 ejPol 40
Comprobar con QuickCheck que, dado un polinomio p y un número entero r, las funciones anteriores verifican la propiedad de la división euclídea.