PDF de programación - Ejercicios de programación declarativa con Prolog

Ejercicios de programación declarativa

con Prolog

José A. Alonso Jiménez

Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla
Sevilla, 1 de Enero de 2006 (Versión de 20 de septiembre de 2007)

2

Esta obra está bajo una licencia Reconocimiento–NoComercial–CompartirIgual 2.5 Spain
de Creative Commons.

Se permite:

copiar, distribuir y comunicar públicamente la obra

hacer obras derivadas

Bajo las condiciones siguientes:

Reconocimiento. Debe reconocer los créditos de la obra de la manera especificada
por el autor.

No comercial. No puede utilizar esta obra para fines comerciales.

Compartir bajo la misma licencia. Si altera o transforma esta obra, o genera una
obra derivada, sólo puede distribuir la obra generada bajo una licencia idéntica a
ésta.

Al reutilizar o distribuir la obra, tiene que dejar bien claro los términos de la licencia
de esta obra.

Alguna de estas condiciones puede no aplicarse si se obtiene el permiso del titular
de los derechos de autor.

h://
eaive


.g/i
ee/by 
a/2.5/e/

Esto es un resumen de la licencia completa. Para ver una copia de esta licencia, visite

o envie una carta a

Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Índice general

Introducción

1. Operaciones con listas

.
.

.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

. .
. .
. .
. .
. .
. .
. .
. .
. .
. .

. .
. .
. .
. .
. .
. .
. .
. .
. .
. .

.
. .
1.1. Primer elemento . .
.
.
. .
1.2. Resto de una lista .
.
.
1.3. Construcción de listas
. .
.
1.4. Relación de pertenencia .
.
1.5. Concatenación de listas . .
.
.
. .
. .
1.6. Lista inversa .
.
. .
.
1.7. Palíndromo .
. .
.
.
1.8. Último elemento . .
. .
.
1.9. Penúltimo elemento .
. .
1.10. Selección de un elemento .
.
1.11. Inserción de un elemento en una lista .
.
. .
1.12. Sublista .
. .
.
1.13. Permutación .
. .
1.14. Lista con todos sus elementos iguales
.
.
1.15. Paridad de la longitud de una lista . .
.
. .
1.16. Rotación de un elemento .
1.17. Subconjunto .
. .
. .
.

. .
. .

. .
. .

. .
. .

. .
. .

.
.
.
.

. .

.
.

.
.

.
.

.
.

.

.

.
.

.

.
.

.

.
.

.
.

.
.

. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .

. .
. .
. .
. .
. .
. .
. .
. .
. .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .

. .
. .
. .
. .
. .
. .
. .
. .
. .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .

. .
. .
. .
. .
. .
. .
. .
. .
. .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .

. .
. .
. .
. .
. .
. .
. .
. .
. .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

6

9
. .
9
. . 10
. . 10
. . 11
. . 12
. . 14
. . 14
. . 15
. . 16
. . 16
. . 17
. . 17
. . 18
. . 18
. . 19
. . 20
. . 20

21
. . 21
. . 21
. . 22
. . 22
. . 23
. . 23
. . 24
. . 24
. . 25

2. Aritmética

.

.

.

. .

. .

.
.
.
.
.

. .
. .
. .
. .
. .

. .
2.1. Máximo de dos números .
. .
.
2.2. Factorial
. .
. .
2.3. Sucesión de Fibonacci .
. .
. .
2.4. Máximo común divisor . .
. .
2.5. Longitud de una lista .
. .
2.6. Lista de números acotada por su longitud .
. .
2.7. Máximo de una lista de números .
. .
. .
2.8. Suma de los elementos de una lista . .
2.9. Lista de números ordenada . .
. .
. .

. .
. .
. .
. .
. .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.

.

.

3

2.11. Lista de veces el número . .

. .

4

.

2.10. Suma parcial de una lista .

.
.
.
.
.
2.12. Generación de lista de números .
.
2.13. Intervalo entero . .
.
2.14. K–ésimo elemento .
.
.
2.15. Multiplicación de las ocurrencias de los elementos de una lista .

. .
. .
. .
. .
. .

. .
. .
. .
. .
. .

. .
. .
. .
. .
. .

. .
. .
. .
. .
. .

. .
. .
. .
. .
. .

. .
. .

. .
. .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.

.
.

.
.

Índice general

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

. .
. .
. .
. .
. .
. .

. .
. .
. .
. .
. .
. .

. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

. . 25
. . 26
. . 27
. . 27
. . 28
. . 28

31
. . 31
. . 33
. . 39
. . 44
. . 45
. . 47

49
. . 49
. . 53
. . 53
. . 55
. . 56
. . 56
. . 58
. . 58
. . 60
. . 60
. . 61
. . 62
. . 63
. . 64
. . 64
. . 65
. . 66
. . 67
. . 67
. . 68
. . 69
. . 70
. . 71
. . 72
. . 73

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

3. Estructuras

.
.

.
.

. .

. .
. .

3.1. Segmentos como objetos estructurados .
.
. .
3.2. Base de datos familiar
.
. .
3.3. Autómata no–determinista .
.
.
3.4. El problema del mono y el plátano . .
3.5. Movimientos del caballo del ajedrez .
.
3.6. Máximo elemento de un árbol binario .

4.2. Árboles de deducción de
e
be
hk .

. .

. .

.

.

4. Retroceso, corte y negación

. .
. .
. .
. .
. .
. .

.
.
.
.
.
.

.
.
.
.
.
.

. .
. .
. .
. .
. .
. .

.
.
.
.
.
.

.
.
.
.
.
.

. .
. .
. .
. .
. .
. .

.
.
.
.
.
.

. .
. .
. .
. .
. .
. .

.

.

.

.

.

.

.

.

.
.
.

. .

. .

. .

. .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

. .
. .
. .
. .

. .
. .
. .
. .

4.1. Ejemplos de uso del corte .

. .
. .
. .
. .
. .
4.3. Diferencia de conjuntos . .
. .
4.4. Agregación de un elemento a un conjunto .
. .
4.5. Separación de una lista de números en positivos y negativos .
. .
. .
4.6. Suma de los números pares de una lista de números
. .
. .
4.7. Exponente de dos en la factorización de un número .
. .
. .
4.8. Transformación de lista a conjunto . .
.
. .
. .
. .
.
4.9. Signos de crecimientos de sucesiones numéricas .
. .
. .
.
. .
4.10. Descomposición en factores primos . .
.
. .
. .
.
. .
4.11. Menor elemento que cumple una propiedad .
. .
4.12. Números libres de cuadrados .
.
. .
.
. .
. .
. .
. .
.
. .
.
4.13. Suma de los números libres de cuadrados .
. .
. .
4.14. Máximo número de una lista .
. .
.
. .
.
. .
4.15. Longitud de las subsucesiones comunes maximales .
. .
. .
. .
.
4.16. Elementos repetidos en una lista .
. .
4.17. Subconjunto maximal .
. .
.
.
4.18. Suma de los elementos con posiciones múltiplos de n . .
. .
.
. .
. .
. .
4.19. Compresión de listas .
. .
.
. .
. .
. .
4.20. Empaquetamiento de listas
.
. .
4.21. Codificación por longitud .
. .
. .
.
. .
. .
4.22. Codificación reducida por longitud . .
. .
. .
.
. .
4.23. Decodificación de lista . .
. .
. .
. .
4.24. Codificación reducida directa .
.
. .
4.25. Cota superior de una lista de números .
. .
. .

. .
. .
. .
. .
. .
. .
. .

. .
. .
. .
. .
. .
. .
. .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

. .
. .
. .

. .
. .

. .
. .

. .
. .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

. .

. .

. .

. .

.
.
.

.
.
.

.
.
.

.

.

.

.

.

.

.
.

.

.

.

.
.

.
.

.
.

.
.

.
.

.

Índice general

4.26. Dientes de sierra . .

.

.

. .

.

. .

.

.

. .

.

. .

.

.

. .

.

.

. .

.

. .

5. Programación lógica de segundo orden

.
.

.
.

.
.

.

.
.

.

.
.

. .

. .

. .
.

. .
. .

. .
. .

5.1. Determinación de un número por su factorial .
.
5.2. Árbol de resolución y definiciones equivalentes
.
5.3. Nodos de una generación en una lista de árboles binarios .
.
. .
.
5.4. Lista de elementos únicos .
.
.
. .
5.5. Elementos más frecuentes de una lista .
.
.
.
. .
.
5.6. Problema 3n + 1 . .
.
.
.
5.7. Números perfectos .
. .
.
.
5.8. Determinación de triángulos equiláteros . .
.
.
.
. .
5.9. Operación binaria aplicada a listas . .
.
.
. .
. .
5.10. Números en un término .
.
5.11. Palabra sin vocales .
. .
. .
. .
.
.
.
. .
5.12. Palabras maximales .
. .
. .
.
.
. .
5.13. Clausura transitiva de una relación . .
.
5.14. Traducción de cifras a palabras .
.
. .
. .
5.15. Transformación de lista dependiente de la posición .
.
.
.
5.16. Aplanamiento de listas . .

. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .

. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .

. .
. .
. .

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

. .
. .

. .
. .

.
.
.
.
.
.

. .

. .

. .

. .

.
.
.

.
.
.

.
.
.

.

.

.

.

.
.

.
.

.

.

.

.

. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .

6. Estilo y eficiencia en programación lógica
. .
. .
. .

6.1. Número de Hardy .
. .
6.2. Subconjuntos de suma dada . .
6.3. Coloreado de mapas .
. .

. .

. .

.
.
.

.
.
.

.

.

.

.

.
.
.

. .
. .
. .

.
.
.

.
.
.

. .
. .
. .

.
.
.

.
.
.

. .
. .
. .

.
.
.

. .
. .
. .

7. Aplicaciones de programación declarativa

7.1. Formación de grupos minimales de asignaturas compatibles .
7.2. Simulación de una calculadora básica .
. .
. .
.
7.3. Problema de las subastas .

. .
. .

. .
. .

. .
. .

. .

. .

.
.

.
.

.
.

.
.

.
.

.

.

.

Bibliografía

Indice de definiciones

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.

. .

. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .

. .
. .
. .

. .
. .
. .

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.

5

. . 74

77
. . 77
. . 79
. . 80
. . 83
. . 83
. . 84
. . 86
. . 89
. . 90
. . 90
. . 91
. . 91
. . 92
. . 93
. . 94
. . 96

97
. . 97
. . 101
. . 103

107
. . 107
. . 110
. . 117

121

122

6

Índice general

Introducción

El objetivo del presente trabajo es presentar una colección de ejercicios para la asig-

natura “Programación declarativa” de tercer curso de la Ingeniería Informática.

Estos ejercicios complementa los apuntes de introducción a la programación decla-

rativa con Prolog ([1]) y a las transparencias de clase ([2]).

Todos los ejercicios s