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
      (x2)      (-1)

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

   2 ------> 4 ------> 3 ------> 6 ------> 5
      (x2)      (-1)      (x2)      (-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
 
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)]

Referencias

Basado en el artículo Minimum number of operation required to
convert number x into y
de Vipin Khushu en
GeeksforGeeks.

Avanzado

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

  1. Diego
    data Arbol = H Int
               | N Int Arbol Arbol
               deriving (Show, Eq)
     
    arbolOp :: Int -> Int -> Arbol
    arbolOp n 0 = H n
    arbolOp n m = N n (arbolOp (2*n) (m-1)) (arbolOp (n-1) (m-1))
     
    subNodos :: Arbol -> [Arbol]
    subNodos (N _ p q) = [p, q]
    subNodos _         = []
     
    minNOp :: Int -> Int -> Int
    minNOp n m =
        aux m 0 [arbolOp n (-1)] -- (-1) para obtener un árbol infinito
        where aux m i arbs = if any ((N n _ _) -> n == m) arbs
                             then i
                             else aux m (i+1) (concatMap subNodos arbs)
  2. Juanjo Ortega (juaorture)
    arbolOp :: Int -> Int -> Arbol
    arbolOp 0 _ = H 0
    arbolOp x 0 = H x
    arbolOp x n = N x (arbolOp (x*2) (n-1)) (arbolOp (x-1) (n-1))
     
    minNOp :: Int -> Int -> Int
    minNOp x y = minimum (profundidades y (arbolOp x d) 0)
      where c = head [a | a <- [0..]
                        , y `div` (2^a) < x]
            d | x > y     = x-y
              | otherwise = c + (x*2^c - y)
     
    profundidades :: Int -> Arbol -> Int -> [Int]
    profundidades a (H b) c
      | a == b    = [c]
      | otherwise = []
    profundidades a (N b i d) c
      | a == b    = c:(profundidades a i (c+1) ++ profundidades a d (c+1))
      | otherwise = profundidades a i (c+1) ++ profundidades a d (c+1)

Escribe tu solución

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