% Examen de "Programación Declarativa" (1 de Diciembre de 2003) % Apellidos: % Nombre: %============================================================================== %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 1: Consideremos la función siguiente definida sobre los números % naturales: % f(x)= 3x+1 si x es impar % f(x)= x/2 si x es par % se pide: % % (a) Definir la relación sucesión(+X,?L) que se verifica si L es la lista de % los elementos X, f(X), f(f(X)), ..., f^n(X) tal que f^n(X)=1. Por % ejemplo, % ?- sucesión(3,L). % L = [3, 10, 5, 16, 8, 4, 2, 1] % % (b) Definir la relación longitudes(+X,?L) que se verifica si L la lista de % pares Y-N donde Y es un número de X a 1 y N es la longitud de la lista % L tal que sucesión(Y,L). Por ejemplo, % ?- longitudes(3,L). % L = [3-8, 2-2, 1-1] % % (b) Definir la relación longitud_max(+X,?P) que se verifica si P es un par de % la forma Y-N donde Y es un número entre 1 y X tal que la longitud de la % sucesión generada por Y es la más larga de las sucesiones generadas por % 1,2,...,X y N es la longitud de dicha sucesión. Por ejemplo, % ?- longitud_max(10,L). % L = 9-20 % % (c) Determinar a qué valor entre 1 y 200 corresponde la lista de mayor % longitud. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % sucesión(+X,?L) % se verifica si L es la lista de los elementos X, f(X), f(f(X)), ..., % f^n(X) tal que f^n(X)=1. Por ejemplo, % ?- sucesión(3,L). % L = [3, 10, 5, 16, 8, 4, 2, 1] sucesión(1,[1]) :- !. sucesión(X,[X|L]) :- % X =/= 1, f(X,Y), sucesión(Y,L). % f(+X,-Y) % se verifica si X es impar e Y=3X+1 o % X es par e Y=X/2. f(X,Y):- X mod 2 =:= 0, !, Y is X/2. f(X,Y):- % X mod 2 =/= 0, Y is 3*X+1. % longitudes(+X,?L) % se verifica si L la lista de pares Y-N donde Y es un número de X a 1 y N % es la longitud de la lista L tal que sucesión(Y,L). Por ejemplo, % ?- longitudes(3,L). % L = [3-8, 2-2, 1-1] longitudes(1,[1-N]) :- !, sucesión(1,L), length(L,N). longitudes(X,[X-N|L]) :- % X > 1, sucesión(X,L1), length(L1,N), Y is X-1, longitudes(Y,L). % longitud_max(+X,?P) % se verifica si P es un par de la forma Y-N donde Y es un número entre 1 y % X tal que la longitud de la sucesión generada por Y es la más larga de las % sucesiones generadas por 1,2,...,X y N es la longitud de dicha % sucesión. Por ejemplo, % ?- longitud_max_1(10,L). % L = 9-20 longitud_max(X,Y-N) :- longitudes(X,L), member(Y-N,L), \+ (member(_Z-M,L), M > N). /* ?- longitud_max(200,L). L = 171-125 */ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 2: Un mapa puede representarse mediante la relación mapa(N,L) % donde N es el nombre del mapa y L es la lista de los pares formados por cada % una de las regiones del mapa y la lista de sus regiones vecinas. Por ejemplo, % los mapas siguientes % +----------+----------+ +----+-----+-----+----+ % | a | b | | a | b | c | d | % +----+-----+-----+----+ +----+-----+-----+----+ % | | | | | e | | f | % | c | d | e | +----+ k +----+ % | | | | | g | | h | % +----+-----+-----+----+ +----+-----+-----+----+ % | f | g | | i | j | % +----------+----------+ +----------+----------+ % se pueden representar por % mapa(ejemplo_1, % [a-[b,c,d], b-[a,d,e], c-[a,d,f], d-[a,b,c,e,f,g], % e-[b,d,g], f-[c,d,g], g-[d,e,f]]). % mapa(ejemplo_2, % [a-[b,e,k], b-[a,c,e,k], c-[b,d,f,k], d-[c,f,k], e-[a,b,g,k], % f-[c,d,h,k], g-[e,i,k], h-[f,j,k], i-[g,j,k], j-[i,h,k], % k-[a,b,c,d,e,f,g,h,i,j]]). % Definir la relación coloración(+M,+LC,-S) que se verifica si S es una % lista de pares formados por una región del mapa M y uno de los colores de la % lista de colores LC tal que las regiones vecinas tengan colores % distintos. Por ejemplo, % ?- coloración(ejemplo_1,[1,2,3],S). % S = [a-1, b-2, c-2, d-3, e-1, f-1, g-2] % ¿Qué número de colores se necesitan para colorear el segundo mapa?. ¿De % cuántas formas distintas puede colorearse con dicho número?. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% mapa(ejemplo_1, [a-[b,c,d], b-[a,d,e], c-[a,d,f], d-[a,b,c,e,f,g], e-[b,d,g], f-[c,d,g], g-[d,e,f]]). mapa(ejemplo_2, [a-[b,e,k], b-[a,c,e,k], c-[b,d,f,k], d-[c,f,k], e-[a,b,g,k], f-[c,d,h,k], g-[e,i,k], h-[f,j,k], i-[g,j,k], j-[i,h,k], k-[a,b,c,d,e,f,g,h,i,j]]). % coloración(+M,+LC,-S) % se verifica si S es una lista de pares formados por una región del mapa M % y uno de los colores de la lista de colores LC tal que las regiones % vecinas tengan colores distintos. coloración(M,LC,S) :- coloración_2(M,LC,S). % 1ª definición de coloración/3 (por generación y prueba): coloración_1(M,LC,S) :- mapa(M,L), coloración_1_aux(L,LC,S). coloración_1_aux([],_,[]). coloración_1_aux([R-V|L],LC,[R-C|S]) :- member(C,LC), coloración_1_aux(L,LC,S), not((member(R1,V), member(R1-C,S))). % 2ª definición de coloración/3 (por generación y prueba con acumulador): coloración_2(M,LC,S) :- mapa(M,L), coloración_2_aux(L,LC,[],S). coloración_2_aux([],_,S,S). coloración_2_aux([R-V|L],LC,A,S) :- member(C,LC), not((member(R1,V), member(R1-C,A))), coloración_2_aux(L,LC,[R-C|A],S). /* Comparación ?- time(coloración_1(ejemplo_2,[1,2,3,4],S)). % 16,705,282 inferences in 22.61 seconds (738845 Lips) S = [a-1, b-2, c-1, d-2, e-3, f-3, g-1, h-1, i-2, j-3, k-4] ?- time(coloración_2(ejemplo_2,[1,2,3,4],S)). % 546 inferences in 0.00 seconds (Infinite Lips) S = [k-4, j-3, i-2, h-1, g-1, f-3, e-3, d-2, c-1, b-2, a-1] ?- findall(_S,coloración_2(ejemplo_2,[1,2,3,4],_S),_L), length(_L,N). N = 1032 */