Constante de Champernowne

5 Comentarios

1. Supuesto el coste de las operaciones numéricas O(1); coste O(log n) para obtener cada dígito.

   Haskell

   -- Extrae el dígito n-ésimo (n=1,2,...) de la secuencia 12345... digito :: Integer -> Integer digito n = serie 1 1 1 where -- calcula la suma: 9 sum { 10^(k-1) * k } k=1,2,... serie g p a = let b = a + 9 * p * g (d, r) = (n - a) `divMod` g in if n >= b then serie (g + 1) (10 * p) b -- el nº que contiene el dígito buscado es `p + d` else ((p + d) `div` 10^(g - r - 1)) `mod` 10 productoChampernowne :: [Integer] -> Integer productoChampernowne = product . map (digito . (+1))

   1 2 3 4 5 6 7 8 9 10 11 12

   -- Extrae el dígito n-ésimo (n=1,2,...) de la secuencia 12345... digito :: Integer -> Integer digito n = serie 1 1 1   where -- calcula la suma: 9 sum { 10^(k-1) * k } k=1,2,...         serie g p a = let b = a + 9 * p * g                           (d, r) = (n - a) `divMod` g                       in  if n >= b then serie (g + 1) (10 * p) b                                     -- el nº que contiene el dígito buscado es `p + d`                                     else ((p + d) `div` 10^(g - r - 1)) `mod` 10   productoChampernowne :: [Integer] -> Integer productoChampernowne = product . map (digito . (+1))

   Responder

2. Haskell

   productoChampernowne :: [Int] -> Int productoChampernowne xs = product [champernowne !! x | x <- xs] champernowne :: [Int] champernowne = aux [1..] where aux (x:xs) = digitos x ++ aux xs digitos n | n < 10 = [n] | otherwise = digitos q ++ [r] where (q,r) = divMod n 10

   1 2 3 4 5 6 7 8 9

   productoChampernowne :: [Int] -> Int productoChampernowne xs = product [champernowne !! x | x <- xs]   champernowne :: [Int] champernowne = aux [1..]     where aux (x:xs) = digitos x ++ aux xs           digitos n | n < 10 = [n]                     | otherwise = digitos q ++ [r]                     where (q,r) = divMod n 10

   Responder

3. Haskell

   productoChampernowne :: [Int] -> Int productoChampernowne xs =product $ map digitToInt [p!n|n<-xs] where n = last xs p =listArray (0,n) (take (n+1) champernowne) champernowne :: String champernowne =concatMap show [1..]

   1 2 3 4 5 6 7

   productoChampernowne :: [Int] -> Int productoChampernowne xs =product $ map digitToInt [p!n|n<-xs]             where n = last xs                   p =listArray (0,n) (take (n+1) champernowne)   champernowne :: String champernowne =concatMap show [1..]

   Responder

4. Haskell

   constante = concat[digitos x|x<-[1..]] where digitos x = [read [n]::Int|n<-show x] productoChampernowne xs = product[constante!!x|x<-xs]

   1 2 3

   constante = concat[digitos x|x<-[1..]]           where digitos x = [read [n]::Int|n<-show x] productoChampernowne xs = product[constante!!x|x<-xs]

   Responder

5. Haskell

   productoChampernowne :: [Int] -> Int productoChampernowne xs = product $ map champernowne xs champernowne :: Int -> Int champernowne n = digitToInt $ show (10^(d-1) + x`div`d)!!(x`mod`d) where d = head [ i | i <- [1..], sum [ j*9*10^(j-1) | j <- [1..i]] > n] x = n - sum [ j*9*10^(j-1) | j <- [1..d-1]]

   1 2 3 4 5 6 7

   productoChampernowne :: [Int] -> Int productoChampernowne xs = product $ map champernowne xs   champernowne :: Int -> Int champernowne n = digitToInt $ show (10^(d-1) + x`div`d)!!(x`mod`d) where d = head [ i | i <- [1..], sum [ j*9*10^(j-1) | j <- [1..i]] > n]        x = n - sum [ j*9*10^(j-1) | j <- [1..d-1]]

   Responder