% Examen de "Programación Declarativa" (8 de Septiembre de 2003) % Apellidos: % Nombre: %============================================================================== %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % El objetivo de los siguientes ejercicios es la simulación de una calculadora % básica. Para ello consideraremos que en cada momento la calculadora se % encuentra en un determinado estado caracterizado por una lista con cuatro % elementos [UCE,UTA,UOA,VIM] donde % UCE es el último cálculo efectuado, % UTA es la última tecla activada, % UOA es el último operador activado y % VIM es el valor impreso. % El estado inicial es [0,=,=,0] y está definido por % estado_inicial([0,=,=,0]). % % Las acciones posibles son pulsar un dígito, una operación aritmética o la de % resultado y están definidas por % acción(X) :- es_dígito(X). acción(X) :- es_operación(X). acción(X) :- es_resultado(X). es_dígito(0). es_dígito(1). es_dígito(2). es_dígito(3). es_dígito(4). es_dígito(5). es_dígito(6). es_dígito(7). es_dígito(8). es_dígito(9). es_operación(+). es_operación(-). es_operación(*). es_operación(/). es_resultado(=). % % En la siguiente tabla se muestran los estados de la calculadora % correspondientes a las acciones indicadas en la última columna % +----------------+------+ % | estado | tecla| % +----------------+------+ % | ( 0, =, =, 0) | 3 | % | ( 0, 3, =, 3) | + | % | ( 3, +, +, 3) | 2 | % | ( 3, 2, +, 2) | 1 | % | ( 3, 1, +, 21) | * | % | (24, *, *, 24) | 2 | % | (24, 2, *, 2) | = | % | (48, =, =, 48) | | % +----------------+------+ % Es decir, si se parte del estado inicial y se realizan las acciones % 3 + 2 1 * 2 = % se obtiene como resultado el número 48. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 1: Define la relación transición(+E1,+X,?E2) que se verifique si E2 % es el estado obtenido aplicando la acción X al estado E1; es decir, si E1 es % [UCE,UTA,UOA,VIM], entonces % 1. Si X es un dígito, entonces % 1.1. si UTA es un dígito, E2 es [UCE,X,UOA,10*VIM+X]; % 1.2. en otro caso, E2 = [UCE,X,UOA,X]. % 2. Si X no es un dígito, entonces % 2.1. si UOA es una operación, E2 = [UOA(UCE,VIM),X,X,UOA(UCE,VIM)] % 2.2. en otro caso, E2 = [VIM,X,X,VIM]. % Por ejemplo, % ?- estado_inicial(E1), % transición(E1,3,E2), % transición(E2,+,E3), % transición(E3,2,E4), % transición(E4,1,E5), % transición(E5,*,E6), % transición(E6,2,E7), % transición(E7,=,E8). % E1 = [0, =, =, 0] % E2 = [0, 3, =, 3] % E3 = [3, +, +, 3] % E4 = [3, 2, +, 2] % E5 = [3, 1, +, 21] % E6 = [24, *, *, 24] % E7 = [24, 2, *, 2] % E8 = [48, =, =, 48] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% transición(E1,A,E2) :- transición_1(E1,A,E2). % 1ª definición de transición/3. % ----------------------------- transición_1([UCE,UTA,UOA,VIM],X,E) :- ( es_dígito(X) -> ( es_dígito(UTA) -> Y is 10*VIM+X, E = [UCE,X,UOA,Y] ; % \+ es_dígito(UTA) -> E = [UCE,X,UOA,X] ) ; % \+ es_dígito(X) -> ( es_operación(UOA) -> T =.. [UOA,UCE,VIM], Y is T, E = [Y,X,X,Y] ; % \+ es_operación(UOA) -> E = [VIM,X,X,VIM] )). % 2ª definición de transición/3. transición_2([UCE,UTA,UOA,VIM],X,E) :- ( es_dígito(X), es_dígito(UTA) -> Y is 10*VIM+X, E = [UCE,X,UOA,Y] ; es_dígito(X), \+ es_dígito(UTA) -> E = [UCE,X,UOA,X] ; \+ es_dígito(X), es_operación(UOA) -> T =.. [UOA,UCE,VIM], Y is T, E = [Y,X,X,Y] ; \+ es_dígito(X), es_resultado(UOA) -> E = [VIM,X,X,VIM] ). % 3ª definición de transición/3. transición_3([UCE,UTA,UOA,VIM],X,[UCE,X,UOA,Y]) :- es_dígito(X), es_dígito(UTA), Y is 10*VIM+X. transición_3([UCE,UTA,UOA,_VIM],X,[UCE,X,UOA,X]) :- es_dígito(X), \+ es_dígito(UTA). transición_3([UCE,_UTA,UOA,VIM],X,[Y,X,X,Y]) :- \+ es_dígito(X), es_operación(UOA), T =.. [UOA,UCE,VIM], Y is T. transición_3([_UCE,_UTA,=,VIM],X,[VIM,X,X,VIM]) :- \+ es_dígito(X). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 2: Define la relación transiciones(+E1,+L,?E2) que se verifique si % E2 es el estado obtenido aplicando las acciones de la lista L al estado % E1. Por ejemplo, % ?- estado_inicial(E1), transiciones(E1,[3,+,2,1,*,2,=],E2). % E1 = [0, =, =, 0] % E2 = [48, =, =, 48] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% transiciones(E,[],E). transiciones(E1,[X|L],E3) :- transición(E1,X,E2), transiciones(E2,L,E3). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 3: Define la relación acciones(?L) que se verifique si L es una % lista de cuyos elementos son acciones. Por ejemplo, % ?- acciones([2,+,3,7]). % Yes % ?- acciones([2,+,37]). % No % Usarlo para calcular el número de posibles listas de acciones de longitud 3. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% acciones([]). acciones([X|L]) :- acción(X), acciones(L). % findall(_L,(length(_L,3), acciones(_L)),_LAL3), length(_LAL3,N). % N = 3375 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 4: Para realizar una operación en la calculadora no todas las % combinaciones de teclas (acciones) son válidas. Por ejemplo, no podemos % teclear dos operaciones consecutivas o dividir por cero. La siguiente % relación define las acciones válidas acciones_válidas(L) :- acciones(L), empieza_por_dígito(L), not(tiene_operaciones_consecutivas(L)), not(tiene_resultado_intermedio(L)), not(divide_por_cero(L)), termina_en_dígito_y_resultado(L). % En los apartados de este ejercicio se definen de las relaciones auxiliares. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 4.1: Define la relación empieza_por_dígito(?L) que se verifique si % el primer elemento de la lista L es un dígito. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% empieza_por_dígito([X|_L]) :- es_dígito(X). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 4.2: Define la relación tiene_operaciones_consecutivas(?L) que se % verifique si la lista L contiene dos operaciones consecutivas. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% tiene_operaciones_consecutivas(L) :- append(_A,[X,Y|_B],L), es_operación(X), es_operación(Y). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 4.3: Define la relación tiene_resultado_intermedio(?L) que se % verifique si la lista L contiene el símbolo = en una posición que no es la % última. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% tiene_resultado_intermedio(L) :- append(_A,[=,_Y|_B],L). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 4.4: Define la relación divide_por_cero(?L) que se verifique si en % la lista L aparecen de manera consecutiva el símbolo / y un cero. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% divide_por_cero(L) :- append(_A,[/,0|_B],L). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 4.5: Define la relación termina_en_dígito_y_resultado(?L) que se % verifique si en la lista L los últimos elementos son un dígito y el % símbolo =. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% termina_en_dígito_y_resultado(L) :- reverse(L,[=,X|_]), es_dígito(X). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 5: Calcula el número de posibles listas de acciones válidas de % longitud 3. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % ?- findall(_L,(length(_L,3), acciones_válidas(_L)),_LAL3), length(_LAL3,N). % N = 100