Menu Close

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

José A. Alonso,

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

Posted in Medio
Tagged , , , ,

2 Comments

  1. adogargon
    Responder 
    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
    Responder 
    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.