Suma con redondeos
Definir las funciones
|
1 2 |
sumaRedondeos :: Integer -> [Integer] limiteSumaRedondeos :: Integer -> Integer |
tales que
- (sumaRedondeos n) es la sucesión cuyo k-ésimo término es
|
1 |
redondeo (n/2) + redondeo (n/4) + ... + redondeo (n/2^k) |
Por ejemplo,
|
1 |
take 5 (sumaRedondeos 1000) == [500,750,875,937,968] |
- (limiteSumaRedondeos n) es la suma de la serie
|
1 |
redondeo (n/2) + redondeo (n/4) + redondeo (n/8) + ... |
Por ejemplo,
|
1 2 3 |
limiteSumaRedondeos 2000 == 1999 limiteSumaRedondeos 2016 == 2016 limiteSumaRedondeos (10^308) `mod` (10^10) == 123839487 |
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 |
-- 1ª definición -- ============= sumaRedondeos1 :: Integer -> [Integer] sumaRedondeos1 n = [sum [round (n'/(fromIntegral (2^k))) | k <- [1..m]] | m <- [1..]] where n' = fromIntegral n limiteSumaRedondeos1 :: Integer -> Integer limiteSumaRedondeos1 = limite . sumaRedondeos1 limite :: [Integer] -> Integer limite xs = head [x | (x,y) <- zip xs (tail xs), x == y] -- 2ª definición sumaRedondeos2 :: Integer -> [Integer] sumaRedondeos2 n = scanl1 (+) [round (n'/(fromIntegral (2^k))) | k <- [1..]] where n' = fromIntegral n limiteSumaRedondeos2 :: Integer -> Integer limiteSumaRedondeos2 = limite . sumaRedondeos2 -- 3ª definición sumaRedondeos3 :: Integer -> [Integer] sumaRedondeos3 n = map fst (iterate f (round (n'/2),4)) where f (s,d) = (s + round (n'/(fromIntegral d)), 2*d) n' = fromIntegral n limiteSumaRedondeos3 :: Integer -> Integer limiteSumaRedondeos3 = limite . sumaRedondeos3 -- 4ª definición sumaRedondeos4 :: Integer -> [Integer] sumaRedondeos4 n = xs ++ repeat x where n' = fromIntegral n m = round (logBase 2 n') xs = scanl1 (+) [round (n'/(fromIntegral (2^k))) | k <- [1..m]] x = last xs limiteSumaRedondeos4 :: Integer -> Integer limiteSumaRedondeos4 = limite . sumaRedondeos4 -- Comparación de eficiencia -- λ> (sumaRedondeos1 4) !! 20000 -- 3 -- (0.92 secs, 197,782,232 bytes) -- λ> (sumaRedondeos1 4) !! 30000 -- 3 -- (2.20 secs, 351,084,816 bytes) -- λ> (sumaRedondeos3 4) !! 20000 -- 3 -- (0.30 secs, 53,472,392 bytes) -- λ> (sumaRedondeos4 4) !! 20000 -- 3 -- (0.01 secs, 0 bytes) -- En lo que sigue, usaremos la 3ª definición sumaRedondeos :: Integer -> [Integer] sumaRedondeos = sumaRedondeos3 -- 5ª definición -- ============= limiteSumaRedondeos5 :: Integer -> Integer limiteSumaRedondeos5 n = sum [round (n'/(fromIntegral (2^k))) | k <- [1..m]] where n' = fromIntegral n m = round (logBase 2 n') |