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 |
El coste cuadrático interno puede hacerse muy rápido.
A mí me salen más casos que tu código no detecta. Por ejemplo:
Chema, tienes razón que hay un error, pero no es que no detecte casos, sino que itera en el intervalo (m, n] en lugar de hacerlo en el intervalo [m, n]. Es cambiar
"drop a"
por"drop (a - 1)"
.Por otro lado creo que las soluciones como
"((104,1625),(40,625)),((1508,1625),(580,625))"
no son válidas ;PPuede que se vea más claro usando compresiones de listas:
Una versión optimizada de la que había puesto antes:
Me he dado cuenta que se puede optimizar mucho la función
comb
mediante una función recursiva. Así mismo, es muchísimo más rápido si se busca antes por el segundo denominador que por el primero.La versión definitiva quedaría así: