Espacio De Estados

5. EJEMPLOS de PROGRAMAS

79

Tema 5. EJEMPLOS de PROGRAMAS 5.1. 5.2. 5.3. 5.4. Las Torres de Hanoi Reconocedor de Polinomios Consulta a un Diccionario Búsqueda en Espacio de Estados

Apuntes: Curso de PROGRAMACION LOGICA

Marisa Navarro 2008-09

80

5. EJEMPLOS de PROGRAMAS

Apuntes: Curso de PROGRAMACION LOGICA

Marisa Navarro 2008-09

5. EJEMPLOS de PROGRAMAS

81

TEMA5. EJEMPLOS de PROGRAMAS
En este tema se presentan 4 ejemplos para ilustrar cómo se representan y solucionan problemas conocidos en PROLOG.

5.1

Las Torres de Hanoi

iz

cen

der

N

El problema consiste en trasladar una torre de N discos de la varilla izquierda (iz) a la derecha (der) con ayuda de la varilla central (cen), con las dos restricciones siguientes: a)- Mover un discoen cada movimiento. b)- No colocar nunca un disco sobre otro menor. La solución óptima se consigue en 2N - 1 movimientos. Deseamos conocer la lista de movimientos necesaria. Representación del problema: hanoi(N, A, B, C, L): "L es una lista de movimientos para trasladar una torre de N discos de A a B con ayuda de C" mov(A,B): "El movimiento de pasar el disco más alto de A a B" (paso de un disco)Programa: hanoi(1, A, B, C, [mov(A,B)]). hanoi(N, A, B, C, L) :- N>1, M is N-1, hanoi(M, A, C, B, L1), hanoi(M, C, B, A, L2), concatenar(L1, [mov(A,B)|L2], L).

Apuntes: Curso de PROGRAMACION LOGICA

Marisa Navarro 2008-09

82

5. EJEMPLOS de PROGRAMAS

5.2

Reconocedor de Polinomios

El programa consiste en reconocer una expresión dada como un polinomio de una incógnita.Representación: polinomio (E,X): "La expresión E es un polinomio en la incógnita X" (La expresión x2 - 3x + 2 se representará en Prolog mediante el término X^2 - 3*X + 2, usando declaración de operadores). Programa: :- op(12, yfx, '+'). :- op(12, yfx, '-'). :- op(10, yfx, '*'). :- op(10, yfx, '/'). :- op( 8, xfx, '^'). polinomio(Y,X) :- var(Y), ! , Y==X. polinomio(T,X) :- constante(T). polinomio(T1+T2, X) :-polinomio(T1,X), polinomio(T2,X). polinomio(T1-T2, X) :- polinomio(T1,X), polinomio(T2,X). polinomio(T1*T2, X) :- polinomio(T1,X), polinomio(T2,X). polinomio(T1/N, X) :- polinomio(T1,X), constante(N). polinomio(T^N, X) :- polinomio(T,X), constante(N). constante(N) :- integer(N). Preguntas: ? polinomio(X^2 - 3*X + 2, X). si (X = H3)
Apuntes: Curso de PROGRAMACION LOGICA

% declaración deoperadores

? polinomio(X^2 - 3*Y + 2, X). no
Marisa Navarro 2008-09

5. EJEMPLOS de PROGRAMAS

83

5.3

Consulta a un Diccionario

El problema consiste en representar en Prolog un diccionario y las operaciones de crearlo, consultar una palabra y traducir un texto. Representación: Para representar el diccionario usaremos árboles binarios ordenados cuyos nodos consistan en pares de palabras(una palabra y su traducción). El orden vendrá dado por una clave de los nodos (la primera palabra del par ) y un orden dado (el orden alfabético). 1. Representación general de un árbol binario:

arb_binario(vacio). arb_binario(arb(R, HI, HD)) :- nodo(R), arb_binario(HI), arb_binario(HD).

2.

Ordenación general según una clave (de los nodos) y un orden dado:

ordenado(vacio, _ ).ordenado(arb(R, HI, HD), Orden) :menort(X, vacio, _ ). menort(X, arb(R, HI, HD), Orden) :("mayort" será similar)

clave(R,X), mayort(X, HI, Orden), menort(X, HD, Orden), ordenado(HI, Orden), ordenado(HD, Orden). clave(R,Y), menor(X, Y, Orden), menort(X, HI, Orden), menort(X, HD, Orden).

Apuntes: Curso de PROGRAMACION LOGICA

Marisa Navarro 2008-09

84 3. Representación del diccionario:

5.EJEMPLOS de PROGRAMAS

diccionario(D) :- arb_binario(D), ordenado(D, alf). nodo(item(P,T)). clave(item (P,T), P). menor(X, Y, alf) :- X @< Y. mayor (X, Y, alf) :- X @> Y. 4. Operación "insertar" palabra en un diccionario:

insertar(X, vacio, arb(X, vacio, vacio)). insertar(X, arb(X, HI, HD), arb(X, HI, HD)). insertar(item(P,T), arb(item(P1,T1), HI, HD), arb(item(P1,T1), NHI, HD)) :- menor(P,...