Menu Close

Etiqueta: isSuffixOf

Terminaciones de Fibonacci

José A. Alonso, ,

Definir la sucesión

   sucFinalesFib :: [(Integer,Integer)]

cuyos elementos son los pares (n,x), donde x es el n-ésimo término de la sucesión de Fibonacci, tales que la terminación de x es n. Por ejemplo,

   λ> take 6 sucFinalesFib
   [(0,0),(1,1),(5,5),(25,75025),(29,514229),(41,165580141)]
   λ> head [(n,x) | (n,x) <- sucFinalesFib, n > 200]
   (245,712011255569818855923257924200496343807632829750245)
   λ> head [n | (n,_) <- sucFinalesFib, n > 10^4]
   10945

Soluciones

import Data.List (genericIndex, isSuffixOf)
 
sucFinalesFib :: [(Integer, Integer)]
sucFinalesFib =
  [(n, fib n) | n <- [0..]
              , show n `isSuffixOf` show (fib n)]
 
sucFib :: [Integer]
sucFib = 0 : 1 : zipWith (+) sucFib (tail sucFib)
 
-- (fib n) es el n-ésimo término de la sucesión de Fibonacci.
fib :: Integer -> Integer
fib n = sucFib `genericIndex` n
Leer más →

Acrónimos

José A. Alonso, ,

Introducción

A partir de una palabra de puede formar un acrónimo uniendo un prefijo de la primera con un sufijo de la segunda. Por ejemplo,

  • “ofimática” es un acrónimo de “oficina” e “informática”
  • “informática” es un acrónimo de “información” y “automática”
  • “teleñeco” es un acrónimo de “televisión” y “muñeco”

Enunciado

-- Definir la función
--    esAcronimo :: String -> String -> String -> Bool
-- tal que (esAcronimo xs ys zs) se verifica si xs es un acrónimo de ys
-- y zs. Por ejemplo,
--    esAcronimo "ofimatica" "oficina" "informatica"       ==  True
--    esAcronimo "informatica" "informacion" "automatica"  ==  True
import Data.List
import Test.QuickCheck
 
-- 1ª definición
-- =============
 
esAcronimo1 :: String -> String -> String -> Bool
esAcronimo1 xs ys zs =
    xs `elem` acronimos ys zs
 
-- (acronimos xs ys) es la lista de acrónimos de xs e ys. Por ejemplo,
--    ghci> acronimos "ab" "cde"
--    ["cde","de","e","","acde","ade","ae","a","abcde","abde","abe","ab"]
acronimos :: String -> String -> [String]
acronimos xs ys =
    [us++vs | us <- inits xs, vs <- tails ys]
 
-- 2ª definición
-- =============
 
esAcronimo2 :: String -> String -> String -> Bool
esAcronimo2 xs ys zs = 
    or [isPrefixOf us ys && isSuffixOf vs zs | 
        (us,vs) <- [splitAt n xs | n <- [0..length xs]]]
 
-- Verificación de equivalencia
-- ============================
 
-- La propiedad es
prop_esAcronimo :: String -> String -> String -> Bool
prop_esAcronimo xs ys zs =
    esAcronimo1 xs ys zs == esAcronimo2 xs ys zs
 
-- La comprobación es
--    ghci> quickCheck prop_esAcronimo
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    ghci> let r = replicate
--    
--    ghci> let n = 500 in esAcronimo1 (r n 'a' ++ r n 'b') (r n 'a') (r n 'b')
--    True
--    (3.76 secs, 1779334696 bytes)
--    
--    ghci> let n = 500 in esAcronimo2 (r n 'a' ++ r n 'b') (r n 'a') (r n 'b')
--    True
--    (0.04 secs, 16715376 bytes)
--
-- La 2ª definición es más eficiente
Leer más →