El pasatiempo de Ulises
Ulises, en sus ratos libres, juega a un pasatiempo que consiste en, dada una serie de números naturales positivos en una cola, sacar un elemento y, si es distinto de 1, volver a meter el mayor de sus divisores propios. Si el número que saca es el 1, entonces lo deja fuera y no mete ningún otro. El pasatiempo continúa hasta que la cola queda vacía.
Por ejemplo, a partir de una cola con los números 10, 20 y 30, el pasatiempo se desarrollaría como sigue:
1 2 3 4 5 6 7 8 9 10 11 12 |
C [30,20,10] C [20,10,15] C [10,15,10] C [15,10,5] C [10,5,5] C [5,5,5] C [5,5,1] C [5,1,1] C [1,1,1] C [1,1] C [1] C [] |
Definir la función
1 |
numeroPasos :: Cola Int -> Int |
tal que (numeroPasos c) es el número de veces que Ulises saca algún número de la cola c al utilizarla en su pasatiempo. Por ejemplo,
1 2 3 4 |
numeroPasos (foldr inserta vacia [30]) == 4 numeroPasos (foldr inserta vacia [20]) == 4 numeroPasos (foldr inserta vacia [10]) == 3 numeroPasos (foldr inserta vacia [10,20,30]) == 11 |
Soluciones
[schedule expon=’2017-05-29′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios hasta el 29 de mayo.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
[/schedule]
[schedule on=’2017-05-29′ at=»06:00″]
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 |
import I1M.Cola import Data.Numbers.Primes (primeFactors) numeroPasos :: Cola Int -> Int numeroPasos c | esVacia c = 0 | pc == 1 = 1 + numeroPasos rc | otherwise = 1 + numeroPasos (inserta (mayorDivisorPropio pc) rc) where pc = primero c rc = resto c -- 1ª definición de mayorDivisorPropio mayorDivisorPropio1 :: Int -> Int mayorDivisorPropio1 n = head [x | x <- [n-1,n-2..], n `mod` x == 0] -- 2ª definición de mayorDivisorPropio mayorDivisorPropio2 :: Int -> Int mayorDivisorPropio2 n = n `div` head (primeFactors n) -- Comparación de eficiencia: -- ghci> sum (map mayorDivisorPropio1 [2..3000]) -- 1485659 -- (3.91 secs, 618,271,360 bytes) -- ghci> sum (map mayorDivisorPropio2 [2..3000]) -- 1485659 -- (0.04 secs, 22,726,600 bytes) |
[/schedule]
7 Comentarios