Fracciones cancelativas
Una fracción x/y es cancelativa si se cumplen las siguientes condiciones:
- x/y es propia (es decir, x < y),
- ninguno de los números x e y son múltiplos de 10 y
- existe un dígito d tal que al borrar una ocurrencia de d en x y otra en y se obtiene una fracción cuyo valor coincide con x/y.
Por ejemplo, 16/64 es cancelativa ya que borrando el 6 en el numerador y el denominador se obtiene 1/4 que es igual a la original: 16/64 = 1/4.
Definir la función
|
1 |
cancelativas :: Int -> Int -> [((Int, Int), (Int, Int))] |
tal que (cancelativas m n) es la lista de las fracciones cancelativas con su denominador entre m y n. Por ejemplo,
|
1 2 3 4 5 6 |
ghci> cancelativas 1 100 [((16,64),(1,4)),((26,65),(2,5)),((19,95),(1,5)),((49,98),(4,8))] ghci> cancelativas 101 150 [((22,121),(2,11)),((33,132),(3,12)),((34,136),(4,16)),((44,143),(4,13))] ghci> length (cancelativas 1 200) 18 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
import Data.List (intersect, nub) cancelativas :: Int -> Int -> [((Int, Int), (Int, Int))] cancelativas m n = nub [((x,y),(a,b)) | y <- [m..n], y `mod` 10 /= 0, x <- [1..y-1], x `mod` 10 /= 0, (as,bs) <- reducciones (show x) (show y), not (null as), not (null bs), let (a,b) = (read as, read bs), b /= 0, a*y == b*x] -- (reducciones xs ys) es la lista de los pares obtenidos eliminando una -- ocurrencia de un elemento de xs tanto en xs como en ys. Por ejemplo, -- ghci> reducciones "abac" "bcba" -- [("bac","bcb"),("abc","bcb"), -- ("aac","cba"),("aac","bca"), -- ("aba","bba")] reducciones :: Eq a => [a] -> [a] -> [([a],[a])] reducciones xs ys = concat [[(us,vs) | us <- eliminaciones xs x, vs <- eliminaciones ys x] | x <- nub (intersect xs ys)] -- (eliminaciones xs y) es la lista de las listas obtenidas eliminando -- una ocurrencia del elemento y en la lista xs. Por ejemplo, -- eliminaciones "abacda" 'a' == ["bacda","abcda","abacd"] -- eliminaciones "abacd" 'a' == ["bacd","abcd"] -- eliminaciones "abacd" 'b' == ["aacd"] -- eliminaciones "abacd" 'e' == [] eliminaciones :: Eq a => [a] -> a -> [[a]] eliminaciones [] _ = [] eliminaciones (x:xs) y | x == y = xs : [x:zs | zs <- zss] | otherwise = [x:zs | zs <- zss] where zss = eliminaciones xs y |