Suma de divisores

Definir la función

tal que (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Número de divisores

Definir la función

tal que (numeroDivisores x) es el número de divisores de x. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Conjunto de divisores

Definir la función

tal que (divisores x) es el conjunto de divisores de x. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Particiones de enteros positivos

Una partición de un entero positivo n es una manera de escribir n como una suma de enteros positivos. Dos sumas que sólo difieren en el orden de sus sumandos se consideran la misma partición. Por ejemplo, 4 tiene cinco particiones: 4, 3+1, 2+2, 2+1+1 y 1+1+1+1.

Definir la función

tal que (particiones n) es la lista de las particiones del número n. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Números con todos sus dígitos primos

Definir la lista

cuyos elementos son los números con todos sus dígitos primos. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

La elaboración de las soluciones se describe en el siguiente vídeo

Eliminación de las ocurrencias aisladas.

Definir la función

tal que (eliminaAisladas x ys) es la lista obtenida eliminando en ys las ocurrencias aisladas de x (es decir, aquellas ocurrencias de x tales que su elemento anterior y posterior son distintos de x). Por ejemplo,

Soluciones

El código se encuentra en GitHub.

La elaboración de las soluciones se describe en el siguiente vídeo

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Trenzado de listas

Definir la función

tal que (trenza xs ys) es la lista obtenida intercalando los elementos de xs e ys. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

La elaboración de las soluciones se describe en el siguiente vídeo

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Espacio de estados del problema de las N reinas

El problema de las N reinas consiste en colocar N reinas en tablero rectangular de dimensiones N por N de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal. Por ejemplo, una solución para el problema de las 4 reinas es

Los estados del problema de las N reinas son los tableros con las reinas colocadas. Inicialmente el tablero está vacío y, en cda paso se coloca una reina en la primera columna en la que aún no hay ninguna reina.

Cada estado se representa por una lista de números que indican las filas donde se han colocado las reinas. Por ejemplo, el tablero anterior se representa por [2,4,1,3].

Usando la librería de árboles Data.Tree, definir las funciones

tales que

  • (arbolReinas n) es el árbol de estados para el problema de las n reinas. Por ejemplo,

  • (nEstados n) es el número de estados en el problema de las n reinas. Por ejemplo,

  • (soluciones n) es la lista de estados que son soluciones del problema de las n reinas. Por ejemplo,

  • (nSoluciones n) es el número de soluciones del problema de las n reinas. Por ejemplo,

Soluciones

Período de una lista

El período de una lista xs es la lista más corta ys tal que xs se puede obtener concatenando varias veces la lista ys. Por ejemplo, el período «abababab» es «ab» ya que «abababab» se obtiene repitiendo tres veces la lista «ab».

Definir la función

tal que (periodo xs) es el período de xs. Por ejemplo,

Soluciones

Combinaciones divisibles

Definir la función

tal que (tieneCombinacionDivisible xs m) se verifica si existe alguna forma de combinar todos los elementos de la lista (con las operaciones suma o resta) de forma que el resultado sea divisible por m. Por ejemplo,

En el primer ejemplo, 1 – 2 + 3 + 4 + 6 = 12 es una combinación divisible por 4. En el segundo ejemplo, las combinaciones de [1,3,9] son

y ninguna de las 4 es divisible por 2.

Soluciones

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Cálculo de pi con el producto de Wallis

El producto de Wallis es una expresión, descubierta por John Wallis en 1655, para representar el valor de π y que establece que:

Definir las funciones

tales que

  • factoresWallis es la sucesión de los factores del productos de Wallis. Por ejemplo,

  • productosWallis es la sucesión de los productos de los primeros factores de Wallis. Por ejemplo,

  • (aproximacionPi n) es la aproximación de pi obtenida multiplicando los n primeros factores de Wallis. Por ejemplo,

  • (errorPi x) es el menor número de factores de Wallis necesarios para obtener pi con un error menor que x. Por ejemplo,

Soluciones

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Pensamiento

«¿Por qué son hermosos los números? Es como preguntar por qué es bella la Novena Sinfonía de Beethoven. Si no ves por qué, alguien no puede decírtelo. Yo sé que los números son hermosos. Si no son hermosos, nada lo es.»

Paul Erdös.

Búsqueda de la mina

En este ejercicio, se representa un mapa mediante una lista de listas de la misma longitud donde todos sus elementos son 0 menos uno (que es un 1) que es donde se encuentra la mina. Por ejemplo, en el mapa

la posición de la mina es (2,1).

Definir la función

tal que (posicionMina m) es la posición de la mina en el mapa m, Por ejemplo,

Soluciones

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Pensamiento

«La vida de un matemático está dominada por una insaciable curiosidad, un deseo que raya en la pasión por resolver los problemas que estudia.»

Jean Dieudonné.

Cálculo de pi mediante la serie de Nilakantha

Una serie infinita para el cálculo de pi, publicada por Nilakantha en el siglo XV, es

Definir las funciones

tales que

  • (aproximacionPi n) es la n-ésima aproximación de pi obtenido sumando los n primeros términos de la serie de Nilakantha. Por ejemplo,

  • (tabla f ns) escribe en el fichero f las n-ésimas aproximaciones de pi, donde n toma los valores de la lista ns, junto con sus errores. Por ejemplo, al evaluar la expresión

hace que el contenido del fichero «AproximacionesPi.txt» sea

al evaluar la expresión

hace que el contenido del fichero «AproximacionesPi.txt» sea

Soluciones

Nodos y conexiones de un grafo

Un grafo no dirigido se representa por la lista de sus arcos. Por ejemplo, el grafo

se representa por [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)].

Se define el tipo de grafo por

Definir las funciones

tales que

  • (nodos g) es la lista de los nodos del grafo g. Por ejemplo,

  • (conectados g x y) se verifica si el grafo no dirigido g posee un arco con extremos x e y. Por ejemplo,

Nota: Escribir la solución en el módulo Grafo para poderlo usar en los siguientes ejercicios.

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

Soluciones

Pensamiento

«La elegancia de un teorema es directamente proporcional al número de ideas que puedes ver en él e inversamente proporcional al esfuerzo que requiere verlas.»

George Pólya.

Átomos de FNC (fórmulas en forma normal conjuntiva)

Nota: En este ejercicio usaremos las mismas notaciones que en el anterior importando el módulo Evaluacion_de_FNC.

Definir las siguientes funciones

tales que

  • (atomosClausula c) es el conjunto de los átomos de la cláusula c. Por ejemplo,

  • (atomosFNC f) es el conjunto de los átomos de la FNC f. Por ejemplo,

Nota: Escribir la solución en el módulo Atomos_de_FNC para poderlo usar en los siguientes ejercicios.

Soluciones

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

Pensamiento

«La esencia de las matemáticas es su libertad.»

Georg Cantor.

Números de Bell

Una partición de un conjunto A es un conjunto de subconjuntos no vacíos de A, disjuntos dos a dos y cuya unión es A. Por ejemplo, el conjunto {1, 2, 3} tiene exactamente 5 particiones:

El n-ésimo número de Bell, B(n), es el número de particiones de un conjunto de n elementos. Por lo visto anteriormentem B(3) = 5.

Definir las funciones

tales que

  • (particiones xs) es el conjunto de las particiones de xs. Por ejemplo,

  • (bell n) es el n-ésimo número de Bell. Por ejemplo,

Comprobar con QuickCheck que (bell n) es equivalente a la función B(n) definida por

  • B(0) = 1
  • B(n) = \displaystyle \sum_{k=0}^{n-1} \binom{n-1}{k} B(k)

Soluciones

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

Pensamiento

«Cambiemos nuestra actitud tradicional en la construcción de programas. En lugar de imaginar que nuestra tarea principal es indicarle a una computadora lo que debe hacer, concentrémonos más bien en explicarle a los seres humanos lo que queremos que haga una computadora.»

Donald Knuth.

Números sin 2 en base 3

Definir la sucesión

cuyos términos son los números cuya representación en base 3 no contiene el dígito 2. Por ejemplo,

Se observa que

  • 12 está en la sucesión ya que su representación en base 3 es 110 (porque 1·3² + 1·3¹ + 0.3⁰ = 12) y no contiene a 2.
  • 14 no está en la sucesión ya que su representación en base 3 es 112 (porque 1·3² + 1·3¹ + 2.3⁰ = 14) y contiene a 2.

Comprobar con QuickCheck que las sucesiones numerosSin2EnBase3 y sucesionSin3enPA (del ejercicio anterior) son iguales; es decir, para todo número natural n, el n-ésimo término de numerosSin2EnBase3 es igual al n-ésimo término de sucesionSin3enPA.

Soluciones

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

Pensamiento

O que yo pueda asesinar un día
en mi alma, al despertar, esa persona
que me hizo el mundo mientras yo dormía.

Antonio Machado

Teorema de Liouville sobre listas CuCu

Una lista CuCu es una lista de números enteros positivos tales que la suma de sus Cubos es igual al Cuadrado de su suma. Por ejemplo, [1, 2, 3, 2, 4, 6] es una lista CuCu ya que

La lista de Liouville correspondiente al número entero positivo n es la lista formada por el número de divisores de cada divisor de n. Por ejemplo, para el número 20 se tiene que sus divisores son

puesto que el número de sus divisores es

  • El 1 tiene 1 divisor (el 1 solamente).
  • El 2 tiene 2 divisores (el 1 y el 2).
  • El 4 tiene 3 divisores (el 1, el 2 y el 4).
  • El 5 tiene 2 divisores (el 1 y el 5).
  • El 10 tiene 4 divisores (el 1, el 2, el 5 y el 10).
  • El 20 tiene 6 divisores (el 1, el 2, el 4, el 5, el 10 y el 20).

la lista de Liouville de 20 es [1, 2, 3, 2, 4, 6] que, como se comentó anteriormente, es una lista CuCu.

El teorema de Lioville afirma que todas las lista de Lioville son CuCu.

Definir las funciones

tales que

  • (esCuCu xs) se verifica si la lista xs es CuCu; es decir, la suma de los cubos de sus elementos es igual al cuadrado de su suma. Por ejemplo,

  • (liouville n) es la lista de Lioville correspondiente al número n. Por ejemplo,

Comprobar con QuickCheck

  • que para todo entero positivo n, (liouville (2^n)) es la lista [1,2,3,…,n+1] y
  • el teorema de Lioville; es decir, para todo entero positivo n, (liouville n) es una lista CuCu.

Nota: Este ejercicio está basado en Cómo generar conjuntos CuCu de Gaussianos.

Soluciones