Una progresi\u00f3n aritm\u00e9tica es una sucesi\u00f3n de n\u00fameros tales que la diferencia de dos t\u00e9rminos sucesivos cualesquiera de la sucesi\u00f3n es constante.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n ausente :: Integral a => [a] -> a\n<\/pre>\ntal que (ausente xs)<\/code> es el \u00fanico t\u00e9rmino ausente de la progresi\u00f3n aritm\u00e9tica xs<\/code>. Por ejemplo,<\/p>\n\n ausente [3,7,9,11] == 5\n ausente [3,5,9,11] == 7\n ausente [3,5,7,11] == 9\n ausente ([1..9]++[11..]) == 10\n ausente ([1..10^6] ++ [2+10^6]) == 1000001\n<\/pre>\nNota.<\/strong> Se supone que la lista tiene al menos 3 elementos, que puede ser infinita y que s\u00f3lo hay un t\u00e9rmino de la progresi\u00f3n aritm\u00e9tica que no est\u00e1 en la lista.<\/p>\nSoluciones<\/h4>\n\nimport Data.List (group, genericLength)\nimport Test.QuickCheck (Arbitrary, Gen,\n arbitrary, frequency, suchThat, quickCheck) \n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nausente1 :: Integral a => [a] -> a\nausente1 (x1:xs@(x2:x3:_))\n | d1 == d2 = ausente1 xs\n | d1 == 2 * d2 = x1 + d2\n | d2 == 2 * d1 = x2 + d1\n where d1 = x2 - x1\n d2 = x3 - x2 \n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nausente2 :: Integral a => [a] -> a\nausente2 s@(x1:x2:x3:_) \n | x1 + x3 \/= 2 * x2 = x1 + (x3 - x2)\n | otherwise = head [a | (a,b) <- zip [x1,x2..] s\n , a \/= b]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nausente3 :: Integral a => [a] -> a\nausente3 xs@(x1:x2:_) \n | null us = x1 + v\n | otherwise = x2 + u * genericLength (u:us) \n where ((u:us):(v:_):_) = group (zipWith (-) (tail xs) xs)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- Tipo de progresiones aritm\u00e9ticas con un t\u00e9rmino ausente.\nnewtype PAconAusente = PA [Integer]\n deriving Show\n\n-- Generaci\u00f3n de progresiones aritm\u00e9ticas con un t\u00e9rmino ausente. \nprogresionConAusenteArbitraria :: Gen PAconAusente\nprogresionConAusenteArbitraria = do\n x <- arbitrary\n d <- arbitrary `suchThat` (\/= 0)\n n <- arbitrary `suchThat` (> 2)\n k <- arbitrary `suchThat` (> 0)\n let (as,_:bs) = splitAt k [x,x+d..]\n frequency [(1,return (PA (as ++ bs))),\n (1,return (PA (take (length as + n) (as ++ bs))))]\n\n-- Inclusi\u00f3n del tipo PAconAusente en Arbitrary.\ninstance Arbitrary PAconAusente where\n arbitrary = progresionConAusenteArbitraria\n\n-- La propiedad es\nprop_ausente :: PAconAusente -> Bool \nprop_ausente (PA xs) =\n all (== ausente1 xs)\n [ausente2 xs,\n ausente3 xs]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_ausente\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> let n = 10^6 in ausente1 ([1..n] ++ [n+2])\n-- 1000001\n-- (1.15 secs, 560,529,520 bytes)\n-- \u03bb> let n = 10^6 in ausente2 ([1..n] ++ [n+2])\n-- 1000001\n-- (0.33 secs, 336,530,680 bytes)\n-- \u03bb> let n = 10^6 in ausente3 ([1..n] ++ [n+2])\n-- 1000001\n-- (0.50 secs, 498,047,584 bytes)\n<\/pre>\n