Sustitución en una posición

Los árboles binarios se pueden representar con el de dato algebraico

Por ejemplo, los árboles

se pueden representar por

Para indicar las posiciones del árbol se define el tipo

donde

representa un movimiento hacia la derecha (D) o a la izquierda. Por ejemplo, las posiciones de los elementos del ej1 son

Definir la función

tal que (sustitucion ds z x) es el árbol obtenido sustituyendo el elemento de x en la posición ds por z. Por ejemplo,

Soluciones

Mínima suma de las 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 (minimaSuma a) es el mínimo de las sumas de las ramas del árbol a. Por ejemplo,

Soluciones

Mínimo número de operaciones para transformar un número en otro

Se considera el siguiente par de operaciones sobre los números:

  • multiplicar por dos
  • restar uno.

Dados dos números x e y se desea calcular el menor número de operaciones para transformar x en y. Por ejemplo, el menor número de operaciones para transformar el 4 en 7 es 2:

y el menor número de operaciones para transformar 2 en 5 es 4

Definir las siguientes funciones

tales que

  • (arbolOp x n) es el árbol de profundidad n obtenido aplicándole a x las dos operaciones. Por ejemplo,

  • (minNOp x y) es el menor número de operaciones necesarias para transformar x en y. Por ejemplo,

Soluciones

Referencias

Basado en el artículo Minimum number of operation required to
convert number x into y
de Vipin Khushu en
GeeksforGeeks.

Problema de las puertas

Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puestas (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

Expresiones aritmética normalizadas

El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos

Por ejemplo, x.(y+z) se representa por (P (V «x») (S (V «y») (V «z»)))

Una expresión es un término si es un producto de variables. Por ejemplo, x.(y.z) es un término pero x+(y.z) ni x.(y+z) lo son.

Una expresión está en forma normal si es una suma de términos. Por ejemplo, x.(y,z) y x+(y.z) está en forma normal; pero x.(y+z) y (x+y).(x+z) no lo están.

Definir las funciones

tales que

  • (esTermino a) se verifica si a es un término. Por ejemplo,

  • (esNormal a) se verifica si a está en forma normal. Por ejemplo,

Soluciones