Menu Close

Mínimo número de operaciones para transformar un número en otro

Se considera el siguiente par de operaciones sobre los números:

  • multiplicar por dos
  • restar uno.

Dados dos números x e y se desea calcular el menor número de operaciones para transformar x en y. Por ejemplo, el menor número de operaciones para transformar el 4 en 7 es 2:

   4 ------> 8 ------> 7
      (*2)      (-1)

y el menor número de operaciones para transformar 2 en 5 es 4

   2 ------> 4 ------> 3 ------> 6 ------> 5
      (*2)      (-1)      (*2)      (-1)

Definir las siguientes funciones

   arbolOp :: Int -> Int -> Arbol
   minNOp  :: Int -> Int -> Int

tales que

  • (arbolOp x n) es el árbol de profundidad n obtenido aplicándole a x las dos operaciones. Por ejemplo,
    λ> arbolOp 4 1
    N 4 (H 8) (H 3)
    λ> arbolOp 4 2
    N 4 (N 8 (H 16) (H 7))
        (N 3 (H 6) (H 2))
    λ> arbolOp 2 3
    N 2 (N 4
           (N 8 (H 16) (H 7))
           (N 3 (H 6) (H 2)))
        (N 1
           (N 2 (H 4) (H 1))
           (H 0))
    λ> arbolOp 2 4
    N 2 (N 4 (N 8
                (N 16 (H 32) (H 15))
                (N 7 (H 14) (H 6)))
             (N 3
                (N 6 (H 12) (H 5))
                (N 2 (H 4) (H 1))))
        (N 1 (N 2
                (N 4 (H 8) (H 3))
                (N 1 (H 2) (H 0)))
             (H 0))
  • (minNOp x y) es el menor número de operaciones necesarias para transformar x en y. Por ejemplo,
     minNOp 4 7  ==  2
     minNOp 2 5  ==  4

Soluciones

data Arbol = H Int
           | N Int Arbol Arbol
  deriving (Show, Eq)
 
arbolOp :: Int -> Int -> Arbol
arbolOp 0 _ = H 0
arbolOp x 0 = H x
arbolOp x n = N x (arbolOp (2 * x) (n - 1)) (arbolOp (x - 1) (n - 1))
 
ocurre :: Int -> Arbol -> Bool
ocurre x (H y)     = x == y
ocurre x (N y i d) = x == y || ocurre x i || ocurre x d
 
minNOp :: Int -> Int -> Int
minNOp x y =
  head [n | n <- [0..]
          , ocurre y (arbolOp x n)]

Pensamiento

¿Dijiste media verdad?
Dirán que mientes dos veces
si dices la otra mitad.

Antonio Machado

2 soluciones de “Mínimo número de operaciones para transformar un número en otro

  1. adogargon
    data Arbol = H Int
                  | N Int Arbol Arbol
         deriving (Eq, Show)
     
    arbolOp :: Int -> Int -> Arbol
    arbolOp x n = arbolaux x n 1
      where arbolaux x n q
              | n == 0    = (H x)
              | x == 0    = (H 0)
              | q == n    = N x (H (2*x)) (H (x-1))
              | otherwise = N x (arbolaux (2*x) n (q+1)) (arbolaux (x-1) n (q+1))
     
    alista :: Arbol -> [Int]
    alista (H x)     = [x]
    alista (N x i d) = [x] ++ alista i ++ alista d
     
    minNOp :: Int -> Int -> Int
    minNOp x y = minaux x y 0
      where minaux x y n
              | y `elem` alista (arbolOp x n ) = n
              | otherwise                        = minaux x y (n+1)
  2. frahidzam
    data Arbol = H Int 
               | N Int Arbol Arbol   
               deriving Show
     
    arbolOp :: Int -> Int -> Arbol
    arbolOp n 1
      | n /= 0    = N n (H (2*n)) (H (n-1))
      | otherwise = H 0
    arbolOp n x
      | n /= 0    = N n (arbolOp (2*n) (x-1)) (arbolOp (n-1) (x-1))
      | otherwise = H 0
     
    minNOp  :: Int -> Int -> Int
    minNOp x y
      | x == y    = 0
      | otherwise = minNOpAux x y 1
     
    minNOpAux :: Int -> Int -> Int -> Int
    minNOpAux x y n
      | elem y (aplana (arbolOp x n)) = n
      | otherwise                     = minNOpAux x y (n+1)
     
    aplana :: Arbol -> [Int]
    aplana (H h)     = [h]
    aplana (N n i d) = [n] ++ aplana i ++ aplana d

Escribe tu solución

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