Biparticiones de una lista

Definir la función

tal que (biparticiones xs) es la lista de pares formados por un prefijo de xs y el resto de xs. 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>

Grafo de una FNC (fórmula en forma normal conjuntiva)

Para reducir el problema del clique a SAT se comienza asociando a cada fórmula F en FNC un grafo G de forma que F es saisfacible si, y sólo si, G tiene un clique con tantos nodos como cláusulas tiene F.

Los nodos del grafo de F son los literales de las cláusulas de F junto con el número de la cláusula. Por ejemplo, la lista de nodos de la FNC [[1,-2,3],[-1,2],[-2,3]] es

En el grafo de F, hay un arco entre dos nodos si, y solo si, corresponden a cláusulas distintas y sus literales no son complementarios. Por ejemplo,

  • hay un arco entre (0,1) y (1,2) [porque son de cláusulas distintas (0 y 1) y sus literales (1 y 2) no son complementarios.
  • no hay un arco entre (0,1) y (1,-1) [porque sus literales (1 y -1) no son complementarios.
  • no hay un arco entre (0,1) y (0,3) [porque son de la misma cláusula (la 0)].

Nota: En este ejercicio se usará los conceptos de los anteriores importando los módulos Evaluacion_de_FNC y Grafo.

Definir las funciones

tales que

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

  • (grafo FNC f) es el grafo de f. 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

«Las matemáticas tienen dos caras: son la ciencia rigurosa de Euclides, pero también son algo más. La matemática presentada a la manera euclidiana aparece como una ciencia sistemática y deductiva; pero la matemática en ciernes aparece como una ciencia experimental e inductiva. Ambos aspectos son tan antiguos como la propia ciencia de las matemáticas.»

George Pólya.

Cliques de un grafo

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

Un clique (en español, pandilla) de un grafo g es un conjunto de nodos de g tal que todos sus elementos están conectados en g.

Definir las funciones

tales que

  • (esClique g xs) se verifica si el conjunto de nodos xs del grafo g es un clique de g. Por ejemplo,

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

Nota: Escribir la solución en el módulo Cliques 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

«Para enseñar de manera efectiva, un profesor debe desarrollar un sentimiento por su asignatura; no puede hacer que sus alumnos sientan su vitalidad si no la siente él mismo. No puede compartir su entusiasmo cuando no tiene entusiasmo que compartir. La forma en que expone su tema puede ser tan importante como el tema que expone; debe sentir personalmente que es importante.»

George Pólya.

Parejas de un conjunto

Definir la función

tal que (parejas xs) es la lista de las parejas formados por los elementos de xs y sus siguientes en xs. 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 primera regla del descubrimiento es tener inteligencia y buena suerte. La segunda regla del descubrimiento es sentarse y esperar hasta que se tenga una idea brillante.»

George Pólya.

Conjuntos con más sumas que restas

Dado un conjunto de números naturales, por ejemplo A = {0, 2, 3, 4}, calculamos las sumas de todos los pares de elementos de A. Como A tiene 4 elementos hay 16 pares, pero no todas sus sumas son distintas. En este caso solo hay 8 sumas distintas: {0, 2, 3, 4, 5, 6, 7, 8}. Procediendo análogamente hay 9 diferencias distinatas entre los pares de A: {-4, -3, -2, -1, 0, 1, 2, 3, 4}.

Experimentando con más conjuntos, se puede conjeturar que el número de restas es mayor que el de sumas y argumentar que que mientras que con dos números distintos sólo se produce una suma distints sin embargo se producen dos restas distintas. Por ejemplo, con 5 y 7 sólo se produce una suma (ya que 5+7 y 7+5 ambos dan 12) pero dos restas (ya que 5-7 y 7-5 dan -2 y 2, respectivamente).

Sin embargo, la conjetura es falsa. Un contraejemplo en el conjunto {0, 2, 3, 4, 7, 11, 12, 14}, que tiene 26 sumas distintas con sus pares de elementos pero sólo 25 restas.

Los conjuntos con más sumas distintas con sus pares de elementos que restas se llaman conjuntos MSQR (por «más sumas que restas»).

El objetivo de este ejercicio es calcular los conjuntos MSQR.

Definir las funciones

tales que

  • (tieneMSQR xs) se verifica si el conjunto xs tiene más sumas que restas. Por ejemplo,

  • conjuntosMSQR es la lista de los conjuntos MSQR. Por ejemplo,

Soluciones

Pensamiento

¡Qué fácil es volar, qué fácil es!
Todo consiste en no dejar que el suelo
se acerque a nuestros pies.

Antonio Machado

Mayor producto de n dígitos consecutivos de un número

Definir la función

tal que (mayorProducto n x) es el mayor producto de n dígitos consecutivos del número x (suponiendo que x tiene al menos n dígitos). Por ejemplo,

Nota: Este ejercicio está basado en el problema 8 del Proyecto Euler

Soluciones

Pensamiento

«El control de la complejidad es la esencia de la programación.» ~ B.W. Kernigan

Mayor producto de n dígitos consecutivos de un número

Definir la función

tal que (mayorProducto n x) es el mayor producto de n dígitos consecutivos del número x (suponiendo que x tiene al menos n dígitos). Por ejemplo,

Soluciones

Pensamiento

A las palabras de amor
les sienta bien su poquito
de exageración.

Antonio Machado

Máxima suma de los segmentos

Un segmento de una lista xs es una sublista de xs formada por elementos consecutivos en la lista. El problema de la máxima suma de segmentos consiste en dada una lista de números enteros calcular el máximo de las sumas de todos los segmentos de la lista. Por ejemplo, para la lista [-1,2,-3,5,-2,1,3,-2,-2,-3,6] la máxima suma de segmentos es 7 que es la suma del segmento [5,-2,1,3] y para la lista [-1,-2,-3] es 0 que es la suma de la lista vacía.

Definir la función

tal que (mss xs) es la máxima suma de los segmentos de xs. Por ejemplo,

Soluciones

Pensamiento

Nubes, sol, prado verde y caserío
en la loma, revueltos. Primavera
puso en el aire de este campo frío
la gracia de sus chopos de ribera.

Antonio Machado

Números en una cadena

Definir la función

tal que (numeros cs) es la lista de los números enteros no negativos de la cadena cs. Por ejemplo,

Soluciones

Pensamiento

Tu profecía, poeta.
— Mañana hablarán los mudos:
el corazón y la piedra.

Antonio Machado

Árboles cuyas ramas cumplen una propiedad

Los árboles se pueden representar mediante el siguiente tipo de dato

Por ejemplo, los árboles

se representan por

Definir la función

tal que (todasDesdeAlguno p ar) se verifica si para toda rama existe un elemento a partir del cual todos los elementos de la rama verifican la propiedad p. Por ejemplo,

Soluciones

Pensamiento

Por dar al viento trabajo,
cosía con hilo doble
las hojas secas del árbol.

Antonio Machado

El problema del número perdido

Sea xs una lista de números consecutivos (creciente o decreciente), en la que puede faltar algún número. El problema del número perdido en xs consiste en lo siguiente:

  • si falta un único número z, devolver Just z
  • si no falta ninguno, devolver Nothing

Definir la función

tal que (numeroPerdido xs) es el resultado del problema del número perdidio en xs. Por ejemplo,

Soluciones

Pensamiento

¡Reventó de risa!
¡Un hombre tan serio!
… Nadie lo diría.

Antonio Machado

Límites de sucesiones

El límite de una sucesión, con una aproximación a y una amplitud n, es el primer término x de la sucesión tal que el valor absoluto de x y cualquiera de sus n siguentes elementos es menor que a.

Definir la función

tal que (limite xs a n) es el límite de xs xon aproximación a y amplitud n. Por ejemplo,

Soluciones

Pensamiento

De diez cabezas, nueve
embisten y una piensa.
Nunca extrañéis que un bruto
se descuerne luchando por la idea.

Antonio Machado

Posiciones del 2019 en el número pi

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

Definir la función

tal que (posicion cs k) es es la lista de las posiciones iniciales de cs en la sucesión formada por los k primeros dígitos decimales del número pi. Por ejemplo,

Calcular la primera posición de 2019 en los decimales de pi y el número de veces que aparece 2019 en en el primer millón de decimales de pi.

Soluciones

Pensamiento

Aprendió tantas cosas, que no tuvo tiempo para pensar en ninguna de ellas.

Antonio Machado

Búsqueda en los dígitos de pi

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

Definir la función

tal que (posicion n) es (Just k) si k es la posición de n en la sucesión formada por un millón dígitos decimales del número pi y Nothing si n no ocurre en dicha sucesión. Por ejemplo,

Nota. Se puede comprobar la función mediante The pi-search page o Pi search engine.

Soluciones

Vértices de un cuadrado

Definir la función

tal que (esCuadrado p q r s) se verifica si los puntos p, q, r y s son los vértices de un cuadrado. Por ejemplo,

Soluciones

El problema 3SUM

El problem 3SUM consiste en dado una lista xs, decidir si xs posee tres elementos cuya suma sea cero. Por ejemplo, en [7,5,-9,5,2] se pueden elegir los elementos 7, -9 y 2 que suman 0.

Definir las funciones

tales que
+ (sols3Sum xs) son las listas de tres elementos de xs cuya suma sea cero. Por ejemplo,

  • (pb3Sum xs) se verifica si xs posee tres elementos cuya suma sea cero. Por ejemplo,

Soluciones

Pares a distancia dada

Definir la función

tal que (pares xs k) es la lista de pares de elementos de xs que están a distancia k (se supone que los elementos de xs son distintos). Por ejemplo,

Soluciones

Subnúmeros pares

Los subnúmeros de un número x son los números que se pueden formar con dígitos de x en posiciones consecutivas. Por ejemplo, el número 254 tiene 6 subnúmeros: 2, 5, 4, 25, 54 y 254.

Definir las funciones

tales que

  • (subnumerosPares x) es la lista de los subnúmeros pares de x. Por ejemplo,

  • (nSubnumerosPares x) es la cantidad de subnúmeros pares de x. Por ejemplo,

Soluciones

Búsqueda en los dígitos de pi

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

Definir la función

tal que (posicion n) es (Just k) si k es la posición de n en la sucesión formada por un millón dígitos decimales del número pi y Nothing si n no ocurre en dicha sucesión. Por ejemplo,

Nota. Se puede comprobar la función mediante The pi-search page o Pi search engine.

Soluciones

Segmentos comunes maximales

Los segmentos de «abcd» son

Los segmentos comunes de «abcd» y «axbce» son

Los segmentos comunes maximales (es decir, no contenidos en otros segmentos) de «abcd» y «axbce» son

Definir la función

tal que (segmentosComunesMaximales xs ys) es la lista de los segmentos comunes maximales de xs e ys. Por ejemplo,

Soluciones

Centro de gravedad de una lista

Se dice que una lista de números xs es equilibrada si existe una posición k tal que la suma de los elementos de xs en las posiciones menores que k es igual a la de los elementos de xs en las posiciones mayores que k. La posición k se llama el centro de gravedad de xs. Por ejemplo, la lista [1,3,4,5,-2,1] es equilibrada, y su centro de gravedad es 2, ya que la suma de [1,3] es igual a la de [5,-2,1]. En cambio, la lista [1,6,4,5,-2,1] no tiene centro de gravedad.

Definir la función

tal que (centro xs) es justo el centro e gravedad de xs, si la lista xs es equilibrada y Nothing en caso contrario. Por ejemplo,

Soluciones

Máxima suma de elementos consecutivos

Definir la función

tal que (sumaMaxima xs) es el valor máximo de la suma de elementos consecutivos de la lista xs. Por ejemplo,

Comprobar con QuickCheck que

Soluciones

Índices de números de Fibonacci

Los primeros términos de la sucesión de Fibonacci son

Se observa que el 6º término de la sucesión (comenzando a contar en 0) es el número 8.

Definir la función

tal que (indiceFib x) es justo el número n si x es el n-ésimo términos de la sucesión de Fibonacci o Nothing en el caso de que x no pertenezca a la sucesión. Por ejemplo,

Soluciones

En Maxima

Sumas digitales de primos consecutivos

Definir la función

tal que (primosConsecutivosConSumasDigitalesPrimas k) es la sucesión de listas de k primos consecutivos tales que las sumas ordenadas de sus dígitos también son primos consecutivos. Por ejemplo,

Soluciones

Referencias

Basado en el artículo DigitSums of some consecutive primes del blog Fun With Num3ers.

Ternas con suma acotada

Definir la función

tal que (ternasAcotadas xs n) es el conjunto de ternas de números naturales de xs cuya suma es menor que n. Por ejemplo,

Soluciones