Término ausente en una progresión aritmética
Una progresión aritmética es una sucesión de números tales que la diferencia de dos términos sucesivos cualesquiera de la sucesión es constante.
Definir la función
|
1 |
ausente :: Integral a => [a] -> a |
tal que (ausente xs) es el único término ausente de la progresión aritmética xs. Por ejemplo,
|
1 2 3 4 5 |
ausente [3,7,9,11] == 5 ausente [3,5,9,11] == 7 ausente [3,5,7,11] == 9 ausente ([1..9]++[11..]) == 10 ausente ([1..10^6] ++ [2+10^6]) == 1000001 |
Nota. Se supone que la lista tiene al menos 3 elementos, que puede ser infinita y que sólo hay un término de la progresión aritmética que no está en la lista.
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
import Data.List (group, genericLength) import Test.QuickCheck (Arbitrary, Gen, arbitrary, frequency, suchThat, quickCheck) -- 1ª solución -- =========== ausente1 :: Integral a => [a] -> a ausente1 (x1:xs@(x2:x3:_)) | d1 == d2 = ausente1 xs | d1 == 2 * d2 = x1 + d2 | d2 == 2 * d1 = x2 + d1 where d1 = x2 - x1 d2 = x3 - x2 -- 2ª solución -- =========== ausente2 :: Integral a => [a] -> a ausente2 s@(x1:x2:x3:_) | x1 + x3 /= 2 * x2 = x1 + (x3 - x2) | otherwise = head [a | (a,b) <- zip [x1,x2..] s , a /= b] -- 3ª solución -- =========== ausente3 :: Integral a => [a] -> a ausente3 xs@(x1:x2:_) | null us = x1 + v | otherwise = x2 + u * genericLength (u:us) where ((u:us):(v:_):_) = group (zipWith (-) (tail xs) xs) -- Comprobación de equivalencia -- ============================ -- Tipo de progresiones aritméticas con un término ausente. newtype PAconAusente = PA [Integer] deriving Show -- Generación de progresiones aritméticas con un término ausente. progresionConAusenteArbitraria :: Gen PAconAusente progresionConAusenteArbitraria = do x <- arbitrary d <- arbitrary `suchThat` (/= 0) n <- arbitrary `suchThat` (> 2) k <- arbitrary `suchThat` (> 0) let (as,_:bs) = splitAt k [x,x+d..] frequency [(1,return (PA (as ++ bs))), (1,return (PA (take (length as + n) (as ++ bs))))] -- Inclusión del tipo PAconAusente en Arbitrary. instance Arbitrary PAconAusente where arbitrary = progresionConAusenteArbitraria -- La propiedad es prop_ausente :: PAconAusente -> Bool prop_ausente (PA xs) = all (== ausente1 xs) [ausente2 xs, ausente3 xs] -- La comprobación es -- λ> quickCheck prop_ausente -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> let n = 10^6 in ausente1 ([1..n] ++ [n+2]) -- 1000001 -- (1.15 secs, 560,529,520 bytes) -- λ> let n = 10^6 in ausente2 ([1..n] ++ [n+2]) -- 1000001 -- (0.33 secs, 336,530,680 bytes) -- λ> let n = 10^6 in ausente3 ([1..n] ++ [n+2]) -- 1000001 -- (0.50 secs, 498,047,584 bytes) |
El código se encuentra en GitHub.