Puntos en regiones rectangulares

Los puntos se puede representar mediante pares de números

y las regiones rectangulares mediante el siguiente tipo de dato

donde

  • (Rectangulo p1 p2) es la región formada por un rectángulo cuyo vértice superior izquierdo es p1 y su vértice inferior derecho es p2.
  • (Union r1 r2) es la región cuyos puntos pertenecen a alguna de las regiones r1 y r2.
  • (Diferencia r1 r2) es la región cuyos puntos pertenecen a la región r1 pero no pertenecen a la r2.

Definir la función

tal que (enRegion p r) se verifica si el punto p pertenece a la región r. Por ejemplo, usando las regiones definidas por

se tiene

Comprobar con QuickCheck que si el punto p está en la región r1, entonces, para cualquier región r2, p está en (Union r1 r2) y en (Union r2 r1), pero no está en (Diferencia r2 r1).

Soluciones

El código se encuentra en GitHub.

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

Enumeración de árboles binarios

Los árboles binarios se pueden representar mediante el tipo Arbol definido por

Por ejemplo, el árbol

se puede definir por

Definir la función

tal que (enumeraArbol a) es el árbol obtenido numerando las hojas y los nodos de a desde la hoja izquierda hasta la raíz. Por ejemplo,

Gráficamente,

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>

[/schedule]

Ramas de un árbol

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

Por ejemplo, los árboles

se representan por

Definir la función

tal que (ramas a) es la lista de las ramas del árbol a. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

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

Subexpresiones aritméticas

Las expresiones aritméticas pueden representarse usando el siguiente tipo de datos

Por ejemplo, la expresión 2*(3+7) se representa por

Definir la función

tal que (subexpresiones e) es el conjunto de las subexpresiones de e. Por ejemplo,

Soluciones

Problema de las puertas

Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puertas (es decir, abrir las cerradas y cerrar las abiertas). El proceso es el siguiente:

  • Inicialmente todas las puertas están cerradas.
  • El primer camarero cambia de estado las puertas de todas las habitaciones.
  • El segundo cambia de estado de las puertas de las habitaciones pares.
  • El tercero cambia de estado todas las puertas que son múltiplos de 3.
  • El cuarto cambia de estado todas las puertas que son múltiplos de 4
  • Así hasta que ha pasado el último camarero.

Por ejemplo, para n = 5

Los estados de las puertas se representan por el siguiente tipo de datos

Definir la función

tal que (final n) es la lista de los estados de las n puertas después de que hayan pasado los n camareros. Por ejemplo,

Soluciones

[schedule on=’2020-06-05′ at=»06:00″]

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>