Ir al contenido principal

Reconocimiento de subcadenas

Definir, por recursión, la función

   esSubcadena :: String -> String -> Bool

tal que esSubcadena xs ys se verifica si xs es una subcadena de ys. Por ejemplo,

   esSubcadena "casa" "escasamente"   ==  True
   esSubcadena "cante" "escasamente"  ==  False
   esSubcadena "" ""                  ==  True

Leer más…

Mayúsculas iniciales

Se consideran las siguientes reglas de mayúsculas iniciales para los títulos:

  • la primera palabra comienza en mayúscula y
  • todas las palabras que tienen 4 letras como mínimo empiezan con mayúsculas

Definir la función

   titulo :: [String] -> [String]

tal que titulo ps es la lista de las palabras de ps con las reglas de mayúsculas iniciales de los títulos. Por ejemplo,

   λ> titulo ["eL","arTE","DE","La","proGraMacion"]
   ["El","Arte","de","la","Programacion"]

Leer más…

Números de Lychrel

Un número de Lychrel es un número para el que nunca se obtiene un capicúa mediante el proceso de invertir las cifras y sumar los dos números. Por ejemplo, los siguientes números no son números de Lychrel: + 56, ya que en un paso se obtiene un capicúa: 56+65=121. + 57, ya que en dos pasos se obtiene un capicúa: 57+75=132, 132+231=363 + 59, ya que en dos pasos se obtiene un capicúa: 59+95=154, 154+451=605, 605+506=1111 + 89, ya que en 24 pasos se obtiene un capicúa. En esta serie de ejercicios vamos a buscar el primer número de Lychrel.

Leer más…

El algoritmo de Luhn

El objetivo de este ejercicio es estudiar un algoritmo para validar algunos identificadores numéricos como los números de algunas tarjetas de crédito; por ejemplo, las de tipo Visa o Master Card.

El algoritmo que vamos a estudiar es el algoritmo de Luhn consistente en aplicar los siguientes pasos a los dígitos del número de la tarjeta.

  1. Se invierten los dígitos del número; por ejemplo, [9,4,5,5] se transforma en [5,5,4,9].
  2. Se duplican los dígitos que se encuentra en posiciones impares (empezando a contar en 0); por ejemplo, [5,5,4,9] se transforma en [5,10,4,18].
  3. Se suman los dígitos de cada número; por ejemplo, [5,10,4,18] se transforma en 5 + (1 + 0) + 4 + (1 + 8) = 19.
  4. Si el último dígito de la suma es 0, el número es válido; y no lo es, en caso contrario.

A los números válidos, se les llama números de Luhn.

Definir las siguientes funciones:

   digitosInv    :: Integer -> [Integer]
   doblePosImpar :: [Integer] -> [Integer]
   sumaDigitos   :: [Integer] -> Integer
   ultimoDigito  :: Integer -> Integer
   luhn          :: Integer -> Bool

tales que

  • digitosInv n es la lista de los dígitos del número n, en orden inverso. Por ejemplo,
     digitosInv 320274  ==  [4,7,2,0,2,3]
  • doblePosImpar ns es la lista obtenida doblando los elementos de ns en las posiciones impares (empezando a contar en cero y dejando igual a los que están en posiciones pares. Por ejemplo,
     doblePosImpar [4,9,5,5]    ==  [4,18,5,10]
     doblePosImpar [4,9,5,5,7]  ==  [4,18,5,10,7]
  • sumaDigitos ns es la suma de los dígitos de ns. Por ejemplo,
     sumaDigitos [10,5,18,4] = 1 + 0 + 5 + 1 + 8 + 4 =
                             = 19
  • ultimoDigito n es el último dígito de n. Por ejemplo,
     ultimoDigito 123 == 3
     ultimoDigito   0 == 0
  • luhn n se verifica si n es un número de Luhn. Por ejemplo,
     luhn 5594589764218858  ==  True
     luhn 1234567898765432  ==  False

Leer más…

Subconjuntos de un conjunto

Definir la función

   subconjuntos :: [a] -> [[a]]

tal que subconjuntos xs es la lista de las subconjuntos de la lista xs. Por ejemplo,

   λ> subconjuntos [2,3,4]
   [[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]]
   λ> subconjuntos [1,2,3,4]
   [[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1],
      [2,3,4],  [2,3],  [2,4],  [2],  [3,4],  [3],  [4], []]

Comprobar con QuickChek que el número de elementos de subconjuntos xs es 2 elevado al número de elementos de xs.

Leer más…

Producto cartesiano de dos conjuntos

Definir la función

   producto :: [a] -> [b] -> [(a,b)]

tal que producto xs ys es el producto cartesiano de xs e ys. Por ejemplo,

   producto [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)]

Comprobar con QuickCheck que el número de elementos de producto xs y es el producto del número de elementos de xs y de ys.

Leer más…

Exponente de la mayor potencia de x que divide a y

Definir la función

   mayorExponente :: Integer -> Integer -> Integer

tal que mayorExponente a b es el exponente de la mayor potencia de a que divide a b. Por ejemplo,

   mayorExponente 2 8    ==  3
   mayorExponente 2 9    ==  0
   mayorExponente 5 100  ==  2
   mayorExponente 2 60   ==  2

Nota: Se supone que a > 1 y b > 0.

Leer más…