Menu Close

El problema del número perdido

José A. Alonso,

Sea xs una lista de números consecutivos (creciente o decreciente), en la que puede faltar algún número. El problema del número perdido en xs consiste en lo siguiente:

  • si falta un único número z, devolver Just z
  • si no falta ninguno, devolver Nothing

Definir la función

   numeroPerdido :: [Int] -> Maybe Int

tal que (numeroPerdido xs) es el resultado del problema del número perdidio en xs. Por ejemplo,

   numeroPerdido [7,6,4,3]                     == Just 5
   numeroPerdido [1,2,4,5,6]                   == Just 3
   numeroPerdido [6,5..3]                      == Nothing
   numeroPerdido [1..6]                        == Nothing
   numeroPerdido ([5..10^6] ++ [10^6+2..10^7]) == Just 1000001

Soluciones

import Data.List (tails, sort)
import Data.Maybe (listToMaybe)
 
-- 1ª solución
numeroPerdido :: [Int] -> Maybe Int
numeroPerdido (x:y:xs)
  | abs (y - x) == 1 = numeroPerdido (y:xs)
  | otherwise        = Just (div (x+y) 2)
numeroPerdido _      = Nothing
 
-- 2ª solución
numeroPerdido2 :: [Int] -> Maybe Int
numeroPerdido2 xs = aux z (z:zs) 
  where (z:zs) = sort xs
        aux _ [] = Nothing
        aux y (x:xs) | y == x    = aux (y+1) xs
                     | otherwise = Just y
 
-- 3ª solución
-- ===========
 
numeroPerdido3 :: [Int] -> Maybe Int
numeroPerdido3 xs =
  listToMaybe [(a+b) `div` 2 | (a:b:_) <- tails xs, abs(a-b) /= 1]

Pensamiento

¡Reventó de risa!
¡Un hombre tan serio!
… Nadie lo diría.

Antonio Machado

Posted in Inicial
Tagged , , , , , , ,

8 Comments

  1. frahidzam
    Responder 
    numeroPerdido :: [Int] -> Maybe Int
numeroPerdido t@(x:y:xs)
  | abs (y - x) == 1 = cabezaSegura [a | (a,b) <- zip [x,y..] t, a /= b]
  | otherwise        = Just (x + head xs - y)
 
cabezaSegura :: [Int] -> Maybe Int
cabezaSegura [] = Nothing
cabezaSegura xs = Just (head xs)
  2. adogargon
    Responder 
    numeroPerdido :: [Int] -> Maybe Int
numeroPerdido (x:y:z:xs)
  | (x + z) `div` 2 /= y = Just (x + (z - y))
  | null zs              = Nothing
  | otherwise            = Just (head zs )
  where zs = [k | (k,q) <- zip [x,y..] (x:y:z:xs), k /= q]
  3. josejuan
    Responder 
    import Data.List (tails)
import Data.Maybe (listToMaybe)
 
numeroPerdido :: [Int] -> Maybe Int
numeroPerdido xs = listToMaybe [(a+b) `div` 2 | (a:b:_) <- tails xs, abs(a-b) /= 1]
  4. marlimand
    Responder 
    numeroPerdido :: [Int] -> Maybe Int
numeroPerdido []  = Nothing
numeroPerdido [x] = Nothing
numeroPerdido (x:y:xs)
  | y == x+1 || y == x-1    = numeroPerdido (y:xs)
  | y /= x+1 && head xs > y = Just (x+1)
  | y /= x-1 && head xs < y = Just (x-1)
  5. luipromor
    Responder 
    numeroPerdido :: [Int] -> Maybe Int
numeroPerdido (x:y:xs)
  | abs (y - x) == 1 = numeroPerdido (y:xs)
  | otherwise        = Just (div (x+y) 2)
numeroPerdido _      = Nothing
  6. danmorper2
    Responder 
    numeroPerdido :: [Int] -> Maybe Int
numeroPerdido (x:xs)
  | head xs - x > 0 = aux (x:xs)
  | otherwise       = aux' (x:xs)
 
aux :: [Int] -> Maybe Int
aux (x:xs)
  | null xs || length xs == 1 = Nothing
  | x+1 /= head xs            = Just (x+1)
  | otherwise                 = numeroPerdido xs
 
aux' :: [Int] -> Maybe Int
aux' (x:xs)
  | null xs || length xs == 1 = Nothing
  | x-1 /= head xs            = Just (x-1)
  | otherwise                 = numeroPerdido xs
  7. javmarcha1
    Responder 
    import Data.List (sort)
 
numeroPerdido :: [Int] -> Maybe Int
numeroPerdido xs = numeroPerdidoAux (sort xs)
 
numeroPerdidoAux :: [Int] -> Maybe Int
numeroPerdidoAux []  = Nothing
numeroPerdidoAux [x] = Nothing
numeroPerdidoAux (x:y:xs)
  | x+1 == y  = numeroPerdidoAux (y:xs)
  | otherwise = Just (x+1)
  8. ireprirod
    Responder

    Solución en Maxima:
    numeroPerdido (xs) := if (length(xs)<2)
    then Nothing else g(xs)$
    g(xs):=if (abs(second(xs)-first(xs))=1) then
    numeroPerdido (rest(xs)) else
    (Just ((first(xs)+second(xs))/ 2)) $

Leave a Reply to ireprirodCancel reply

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