Menu Close

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:

  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

   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,

   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


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)

7 soluciones de “El pasatiempo de Ulises

  1. albcercid
     
    import I1M.Cola
    import Data.Numbers.Primes
     
     
    numeroPasos :: Cola Int -> Int
    numeroPasos xs | esVacia xs = 0
                   | otherwise =
                     length (primeFactors (primero xs)) + 1 + numeroPasos (resto xs)
  2. Cescarde
    import I1M.Cola
     
    numeroPasos :: Cola Int -> Int
    numeroPasos a | esVacia a = 0
                  | p == 1 = 1 + numeroPasos r
                  | otherwise = 1 + numeroPasos (inserta (divProp p) r)
                  where p = primero a
                        r = resto a
                        divProp x = head [n | n <- reverse [1..x-1], mod x n == 0]
  3. enrnarbej
    import Data.Numbers.Primes
    import I1M.Cola
     
    numeroPasos :: Cola Int -> Int
    numeroPasos c | esVacia c = 0
                  | p == 1    = 1 + numeroPasos rc
                  | otherwise = 1 + numeroPasos (inserta m rc)
                  where
                  rc = resto c
                  p  = primero c
                  m  = p `div` (head (primeFactors p))
  4. marmerzaf
    numeroPasos :: Cola Int -> Int
    numeroPasos xs | esVacia xs = 0
                   | primero xs == 1 = 1 + numeroPasos (resto xs)
                   | otherwise  = 1+ numeroPasos (inserta (quot (primero xs)(head (primeFactors (primero xs)))) (resto xs))
  5. marlobrip
    numeroPasos :: Cola Int -> Int
    numeroPasos c | esVacia c = 0
                  | pc  == 1 = 1 + numeroPasos rc
                  | otherwise = 1 + numeroPasos (inserta (mayorDiv pc) rc)
         where rc = resto c
               pc = primero c
     
    mayorDiv :: Int -> Int
    mayorDiv n = last [ x | x <- [1..n-1], n `mod` x == 0]
  6. alvfercen
    import I1M.Cola
    import Data.Numbers.Primes
     
    numeroPasos :: Cola Int -> Int
    numeroPasos c |esVacia c = 0
                  |p == 1    = 1 + numeroPasos r
                  |otherwise = 1 + numeroPasos (inserta n r)
      where r = resto c
            p = primero c
            n = maximum (divisores p)
     
    divisores :: Int -> [Int]        
    divisores n = [x |x <- [1..n `div` 2], n `rem` x == 0]
  7. eliguivil
    import I1M.Cola
     
    numeroPasos :: Cola Int -> Int
    numeroPasos c
      | esVacia c = 0
      | primero c == 1 = 1 + numeroPasos (resto c)
      | otherwise =
        1 + (numeroPasos $ inserta (mayorDivisor (primero c)) (resto c))
     
    mayorDivisor :: Int -> Int
    mayorDivisor n | even n    = div n 2
                   | otherwise = head [-k | k <- [-div n 3..0], n `mod` (-k) == 0]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.