18 diciembre 2012 – Vestigium

I1M2012: Ceros finales del factorial

PorJosé A. Alonso 18 diciembre 20128 marzo 2013

En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la solución con Haskell de un problema propuesto para la Olimpiada Internacional de Matemáticas de 1987 cuyo enunciado es

”Calcular el menor número natural n tal que n! termina exactamente en 1987 ceros.”

Resolverlo con Haskell.

Para resolverlo, empezamos definiendo la función cerosDelFactorial tal que (cerosDelFactorial n) es el número de ceros en que termina el factorial de n. Por ejemplo,

cerosDelFactorial1 24  ==  4
cerosDelFactorial1 25  ==  6

1 2	cerosDelFactorial1 24 == 4 cerosDelFactorial1 25 == 6

Presentamos dos definiciones la primera es

cerosDelFactorial1 :: Integer -> Integer
cerosDelFactorial1 n = ceros (factorial n)

1 2	cerosDelFactorial1 :: Integer -> Integer cerosDelFactorial1 n = ceros (factorial n)

donde (ceros n) es el número de ceros en los que termina el número n. Por ejemplo,

ceros 320000  ==  4

1	ceros 320000 == 4

ceros n | rem n 10 /= 0 = 0
        | otherwise     = 1 + ceros (div n 10)

1 2	ceros n \| rem n 10 /= 0 = 0 \| otherwise = 1 + ceros (div n 10)

y (factorial n) es el factorial n. Por ejemplo,

factorial 3  ==  6

1	factorial 3 == 6

factorial n = product [1..n]

1	factorial n = product [1..n]

La segunda es

cerosDelFactorial2 :: Integer -> Integer
cerosDelFactorial2 n | n < 5     = 0
                     | otherwise = m + cerosDelFactorial2 m
                     where m = n `div` 5

cerosDelFactorial2 :: Integer -> Integer

cerosDelFactorial2 n | n < 5 = 0

| otherwise = m + cerosDelFactorial2 m

where m = n `div` 5

Se puede comprobar la equivalencia de las dos definiciones

ghci> and [cerosDelFactorial1 n == cerosDelFactorial2 n | n <- [1..100]]
True

1 2	ghci> and [cerosDelFactorial1 n == cerosDelFactorial2 n \| n <- [1..100]] True

y que la segunda es más eficiente

ghci> cerosDelFactorial1 (10^4)
2499
(0.64 secs, 131287116 bytes)
ghci> cerosDelFactorial2 (10^4)
2499
(0.01 secs, 725088 bytes)

ghci> cerosDelFactorial1 (10^4)

2499

(0.64 secs, 131287116 bytes)

ghci> cerosDelFactorial2 (10^4)

2499

(0.01 secs, 725088 bytes)

En lo que sigue, usaremos la segunda definición

cerosDelFactorial :: Integer -> Integer
cerosDelFactorial = cerosDelFactorial1

1 2	cerosDelFactorial :: Integer -> Integer cerosDelFactorial = cerosDelFactorial1

A continuación definimos la función menorFactorial tal que (menorFactorial m) es el menor número cuyo factorial termina en m ceros exactamente. Por ejemplo,

menorFactorial 1  ==  5
menorFactorial 4  ==  20
menorFactorial 6  ==  25

menorFactorial 1 == 5

menorFactorial 4 == 20

menorFactorial 6 == 25

menorFactorial :: Integer -> Integer
menorFactorial k = head [n | n <- [1..], cerosDelFactorial n == k]

1 2	menorFactorial :: Integer -> Integer menorFactorial k = head [n \| n <- [1..], cerosDelFactorial n == k]

Finalmente definimos la solución del problema; es decir, el menor número natural n tal que n! termina exactamente en 1987 ceros.

solucion :: Integer
solucion = menorFactorial 1987

1 2	solucion :: Integer solucion = menorFactorial 1987

El cálculo de la solución es

ghci> solucion
7960

1 2	ghci> solucion 7960

I1M2012: Problemas 8 y 9 y ejercicios sobre cadenas

PorJosé A. Alonso 18 diciembre 20128 marzo 2013

En la primera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones de los problemas 8 (números bonitos y números feos) y 9 (ceros finales del factorial).

En la segunda parte hemos comentado las soluciones de los ejercicios 4 y 6 de la 12ª relación de funciones sobre cadenas.

Los ejercicios, y sus soluciones, se muestran a continuación:
Read More “I1M2012: Problemas 8 y 9 y ejercicios sobre cadenas”

LI2012: Modelos de Herbrand

PorJosé A. Alonso 18 diciembre 20128 marzo 2013

En la clase de hoy del curso Lógica Informática se estudiado cómo se puede puede reducir la consistencia de conjuntos de cláusulas de primer orden a la consistencia de conjuntos de cláusulas proposicionales.

En primer lugar, se ha observado que la reducción es inmediata en el caso de fórmulas sin variables.

A continuación se han presentado procedimientos para construir los universos de Herbrand, las bases de Herbrand y las interpretaciones de Herbrand. Así como un procedimiento que transforma modelos de conjuntos de cláusulas en modelos de Herbrand. Por tanto, la consistencia de un conjunto de cláusulas se reduce a la búsqueda de modelos de Herbrand.

Finalmente, se ha explicado el teorema de Herbrand y su aplicación para decidir la consistencia de un conjunto de cláusulas buscando un subconjunto finito de su extensión de Herbrand que sea consistente (en el sentido proposicional).

Las transparencias de la clase son las del tema 11.

I1M2012: El problema de las números bonitos y números feos en Haskell

PorJosé A. Alonso 18 diciembre 201216 marzo 2013

En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la solución con Haskell el desafío matemáticos Números bonitos, números feos publicado en EL PAÍS con motivo del sorteo de la Lotería de Navidad. Su enunciado es

Desde el año 2011 en la Lotería Navidad se sortean los premios entre los cien mil números que van del 00000 al 99999 (en los décimos los números siempre se escriben con cinco cifras). Aunque todos los números tienen exactamente las mismas posibilidades de resultar premiados, con frecuencia se habla de números bonitos y números feos. Como es una valoración estética, que un número sea bonito o feo depende de los gustos de cada uno.

En este caso un número de lotería nos parecerá bonito si cumple
exactamente una, y solamente una, de estas tres condiciones:

a) es divisible entre 5,

b) da resto 2 al dividirlo entre 7,

c) la suma de sus cifras es divisible entre 9.

Por ejemplo, el 00037 es bonito porque cumple la condición b pero no las otras dos; sin embargo, el 00324 es feo, ya que cumple las condiciones b y c. De igual forma, podríamos decir que el 00041 y el 00450 son horribles. El primero, porque no cumple ninguna de las tres condiciones; y el segundo, porque es un exagerado y cumple las tres.

El desafío que se propone es decidir cuántos de los números que participan en el sorteo de Lotería de Navidad (recordad, del 00000 al 99999) son bonitos según el criterio expresado anteriormente.

A continuación, se presentan 5 soluciones en Haskell y se comparan sus eficiencias.
Read More “I1M2012: El problema de las números bonitos y números feos en Haskell”