% Examen de "Programación Declarativa" (8 de Febrero de 2001) % Apellidos: % Nombre: %============================================================================== %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 1: Juanito acaba de terminar una división de un número de cinco % cifras entre un número de tres cifras, pero sin querer se ha apoyado en la % pizarra y ha borrado algunas cifras. Marcamos con * las cifras % borradas. Escribe un programa Prolog para ayudar a Juanito a encontrar las % cifras borradas. % % * 7 * 9 * | 2 1 5 % +--------------- % * 5 * 9 1 * * % % 0 * 4 * % % 0 0 0 % % (Ayuda: Asigna una variable a cada cifra borrada. La solución será el % valor que deben tomar las variables para verificar la operación. El % predicado principal debe ser "division(L)" donde L es una lista con los % nueve valores que faltan) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Solución: Usaremos las siguientes variables: % % A 7 B 9 C | 2 1 5 % +--------------- % D 5 E 9 1 H I % % 0 F 4 G % % 0 0 0 % Primera solución: % ----------------- solucion_1([A,B,C,D,E,F,G,H,I]) :- between(0,9,A), between(0,9,B), between(0,9,C), between(0,9,D), between(0,9,E), between(0,9,F), between(0,9,G), between(0,9,H), between(0,9,I), Dividendo is A*10000 + 7000 + B*100 + 90 + C, Cociente is 100 + H*10 + I, Dividendo is Cociente * 215, 215 + D*100 + 50 + E =:= A*100 + 70 + B, F*100 + 40 + G =:= I * 215. % Segunda solución: % ----------------- % Tendremos en cuenta los siguiente: % (1) C y G tienen que ser iguales % (2) I * 215 es "0F4G", esto es, I * 215 es un número de tres cifras % distinto de cero, luego I está entre 1 y 4. % (3) "D 5 E 9" = H * 215 + "F 4" por tanto H no puede ser par. % (4) Además haremos las comprobaciones lo antes posible. solucion_2([A,B,C,D,E,F,C,H,I]) :- member(C,[0,5]), between(1,4,I), between(0,9,F), F*100 + 40 + C =:= I * 215, between(0,9,D), between(0,9,E), member(H,[1,3,5,7,9]), Segunda_linea is 1000*D + 500 + 10*E + 9, Segunda_linea is 215 * H + 10 * F + 4, between(0,9,A), between(0,9,B), A*10000 + 7000 + B*100 + 90 + C =:= 215 * (100+ 10*H + I). % ?- time(solucion_2(L)). % 585 inferences in 0.01 seconds (58500 Lips) % L = [3, 1, 5, 1, 6, 6, 5, 7, 3] ; % No % Con lo que la solución queda % % 3 7 1 9 5 | 2 1 5 % +--------------- % 1 5 6 9 1 7 3 % % 0 6 4 5 % % 0 0 0 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 2: Angel, Boris, César y Diego se reunieron un día. Se sentaron y % bebieron. El que se sentó a la izquierda de Boris bebió agua. Angel estaba % frente al que bebía vino. El que se sentaba a la derecha de Diego bebía % anís. El del café y el del anís estaban frente a frente. ¿Cuál era la bebida % de cada hombre?. % % Ayuda: Representaremos la reunión en una mesa rectangular % % A B % +-------------------+ % | | % +-------------------+ % D C % % que a su vez la representaremos mediante la lista % [p(X1,Beb_X1),p(X2,Beb_X2),p(X3,Beb_X3),p(X4,Beb_X4)]. % Escribiremos la solución con un predicado "solucion(L)". Para evitar % soluciones simétricas podemos fijar al principio X1=angel. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 3: Los primeros niveles del triángulo de Tartaglia son los % siguientes: % Nivel 1: 1 % Nivel 2: 1 1 % Nivel 3: 1 2 1 % Nivel 4: 1 3 3 1 % Nivel 5: 1 4 6 4 1 % Nivel 6: 1 5 10 10 5 1 % ... ... % El nivel N tiene N elementos donde el el primero y el último son iguales a % 1 y el resto de los elementos se forma sumando los dos elementos del % triángulo del nivel superior. Definir el predidado tartaglia(N,L) que % reciba como entrada un entero positivo y devuelva la lista L que % representa el N-ésimo nivel del triángulo de Tartaglia. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Solución 1: % ----------- tartaglia_1(1,[1]). tartaglia_1(N,[X|L]) :- N > 1, N1 is N-1, tartaglia_1(N1,[X|L1]), construye([X|L1],L). construye([X],[X]). construye([X,Y|Z],[H|R]) :- H is X+Y, construye([Y|Z],R). % Solución 2: % ----------- tartaglia_2(1,[1]) :-!. tartaglia_2(N,[X|L]) :- N1 is N-1, tartaglia_2(N1,[X|L1]), construye([X|L1],L). % Solución 3: % ----------- tartaglia_3(N,L) :- tartaglia_3_aux(N,1,[1],L). tartaglia_3_aux(N,N,L,L) :- !. tartaglia_3_aux(N,M,Ac,Sal) :- M1 is M+1, construye(Ac,Ac1), tartaglia_3_aux(N,M1,[1|Ac1],Sal). % Solución 4: % ----------- tartaglia_4(N,L_sal) :- Paridad is N mod 2, tartaglia_4_aux(N,1,[1],L,impar), duplica(Paridad,L,L_sal). tartaglia_4_aux(N,N,L,L,_) :- !. tartaglia_4_aux(N,M,Ac,Sal,Signo) :- M1 is M+1, cons_3(Signo,Ac,Ac1), cambia_signo(Signo,Signo_c), tartaglia_4_aux(N,M1,[1|Ac1],Sal,Signo_c). cambia_signo(par,impar). cambia_signo(impar,par). cons_3(impar,[_],[]). cons_3(impar,[X,Y|R1],[Z|R2]) :- Z is X+Y, cons_3(impar,[Y|R1],R2). cons_3(par,[X],[Y]) :- Y is X*2. cons_3(par,[X,Y|R1],[Z|R2]) :- Z is X+Y, cons_3(par,[Y|R1],R2). duplica(0,L1,L2) :- duplica_par(L1,[],L2). duplica(1,L1,L2) :- duplica_impar(L1,[],L2). duplica_impar([X],R,[X|R]). duplica_impar([X|L1],Acum,[X|L2]) :- duplica_impar(L1,[X|Acum],L2). duplica_par([],R,R). duplica_par([X|L1],Acum,[X|L2]) :- duplica_par(L1,[X|Acum],L2).