Práctica 5 (pre 2010, Paradigmas)
Ejercicio 01
A partir de los predicados binarios padre y esposo y de los predicados unarios hombre y mujer, definir en Prolog los predicados binarios: hijo, abuelo, progenitor, hermano, descendiente, tio.
i. Considerar el arbol genealogico de la siguiente figura. Dibuje el arbol de busqueda de Prolog para la consulta abuelo(Who, ron).
padre(-Padre, -Hijo) esposo(-Hombre, -Mujer)
padre(john, sue). padre(john, bill). padre(bob, nancy). padre(bob, jeff). padre(bill, ron). esposo(john, mary). esposo(bob, sue). esposo(bill, jane). hombre(john). hombre(bob). hombre(jeff). hombre(bill). hombre(ron). mujer(mary). mujer(sue). mujer(nancy). mujer(jane).
hijo( -Hijo, -Persona)
hijo(Hijo, Persona) :- hombre(Persona), padre(Persona, Hijo). hijo(Hijo, Persona) :- mujer(Persona), esposo(Esposo, Persona), hijo(Hijo, Esposo).
abuelo(-Abuelo, -Nieto)
abuelo(Abuelo, Nieto) :- hijo(Nieto, Progenitor), hijo(Progenitor, Abuelo).
progenitor(-Progenitor, -Hijo)
progenitor(Progenitor, Hijo) :- hijo(Hijo, Progenitor).
hermano(-Hermano, -Persona)
hermano(Hermano, Persona) :- progenitor(Progenitor, Hermano), progenitor(Progenitor, Persona), Hermano \= Persona.
De la manera anterior, si se le pide hermano(sue, X) me devuelve bill, pero dos veces (uno por la madre (mary) y otro por el padre(john)). Para que funcione correctamente y debido a que en este caso asumimos que dos personas casadas comparten todos sus hijos, podemos definirla de la siguiente manera:
hermano(H1,H2) :- padre(P,H1) , padre(P,H2), H1 \= H2.
descendiente(-Descendiente, -Ascendiente)
descendiente(Descendiente, Ascendiente) :- hijo(Descendiente, Ascendiente). descendiente(Descendiente, Ascendiente) :- hijo(Descendiente, Padre), descendiente(Padre, Ascendiente).
tio(-Tio, -Sobrino)
tio(Tio, Sobrino) :- hijo(Sobrino, Padre), hermano(Tio, Padre).
ii. Defina una nueva relacion primo. ¿Como se puede definir una consulta para conocer todos los primos de ron?
primo(-Primo, -OtroPrimo)
primo(P1, P2) :- progenitor(Pd1, P1) , progenitor(Pd2,P2), hermano(Pd1,Pd2).
La que sigue no anda, porque si le pedís primo(nancy, Primo) devuelve a jeff, porque comparten abuelos pero no son primos.
primo(Primo, OtroPrimo) :- abuelo(Abuelo, Primo), abuelo(Abuelo, OtroPrimo), Primo \= OtroPrimo.
ii. Respuesta: primo(ron, Primo).
iii. Considerar el agregado del siguiente hecho y regla:
ancestro(X, X). ancestro(X, Y) :- ancestro(Z, Y), progenitor(X, Z).
y el arbol genealogico del item anterior. a) Explicar la respuesta a la consulta ancestro(bill, X).
iii. a. ancestro(bill, X). iii. a. salida: X = bill; X = ron; Loop Infinito...
b) Describir las circunstancias en las que puede ocurrir un loop infinito en Prolog.
c) Sugerir un solucion al problema hallado en los puntos anteriores reescribiendo el programa de ancestro.
iii. c. ancestro:
ancestro(X, X). ancestro(X, Y) :- progenitor(X, Z), ancestro(Z, Y).
Ejercicio 02
Usando la definicion de numero natural a partir de cero y sucesor, definir un predicado unario nn, tal que nn(-X) sii X es un numero natural. Definir las siguientes relaciones entre numeros naturales:
data Nat = cero | sucesor Nat
nn(-X).
nn(cero). nn(sucesor(X)) :- nn(X). tonn(0, cero). tonn(X, sucesor(Y)) :- X > 0, PrevX is X - 1, tonn(PrevX, Y).
i. moi(-X, +Y) sii X es menor o igual que Y.
moi(cero, Y) :- nn(Y). moi(sucesor(X), sucesor(Y)) :- moi(X, Y).
menor(-X, +Y) sii X es menor que Y.
menor(cero, sucesor(Y)) :- nn(Y). menor(sucesor(X), sucesor(Y)) :- menor(X, Y).
ii. producto(+X, +Y, -Z) sii Z es el producto de X con Y. suma(-X, -Y, -Z) sii Z es la suma de X con Y.
suma(X, cero, X) :- nn(X). suma(X, sucesor(Y), sucesor(Z)) :- suma(X, Y, Z).
producto(+X, +Y, -Z)
producto(X, cero, cero) :- nn(X). producto(X, sucesor(Y), Z) :- producto(X, Y, XPorY), suma(X, XPorY, Z).
iii. fact(+X, -F) sii F es el factorial de X. iii. fact(+X, -F) sii F es el factorial de X.
fact(cero, sucesor(cero)). fact(sucesor(X), F) :- fact(X, PrevF), producto(sucesor(X), PrevF, F).
iv. mod(+X, +Y, -Z) sii Z es el resto de la division entrera entre X e Y. Definicion recursiva.
mod(X, X, cero) :- X \= cero, nn(X). mod(X, Y, X) :- Y \= cero, X \= Y, moi(X, Y). mod(X, Y, Z) :- Y \= cero, suma(XMenosY, Y, X), mod(XMenosY, Y, Z).
iv. modNR(+X, +Y, -Z) sii Z es el resto de la division entrera entre X e Y. Definicion no recursiva. Propiedad: Z + K * Y = X
modNR(X, X, cero) :- X \= cero, nn(X). modNR(X, Y, X) :- Y \= cero, X \= Y, moi(X, Y). modNR(X, Y, Z) :- Y \= cero, moi(K, X), menor(Z, Y), producto(K, Y, CasiX), suma(CasiX, Z, X).
v. Definir un predicado unario que determine si un numero entero dado es primo. Tener en cuenta que el argumento siempre esta instanciado.
no_es_primo(cero). no_es_primo(sucesor(cero)). no_es_primo(X) :- nn(X), menor(Menor, X), menor(sucesor(cero), Menor), mod(X, Menor, cero). primo(X) :- not(no_es_primo(X)). sumaPrimo(float(Entera1, Dec1), float(Entera2, Dec2)) :- sumaPrimo(float(Entera1, Dec1), float(Entera2, Dec2)) :- noventaYNueve(N99), moi(Dec1, N99), moi(Dec2, N99), producto(Entera1, suc(N99), Ent1), producto(Entera2, suc(N99), Ent2), suma(Ent1, Dec1, Num1), suma(Ent2, Dec2, Num2), moi(Num1, Num2), suma(Entera2, Dec2, Primo), primo(Primo).
Ejercicio 03
Sea el siguiente programa logico:
vecino(X, Y, [X|[Y|Ls]]). vecino(X, Y, [W|Ls]) :- vecino(X, Y, Ls).
i. Mostrar el arbol de derivacion en Prolog para resolver
vecino(5, Y, [5,6,5,3]).
devolviendo todos los valores de que hacen que la meta se deduzca logicamente del programa.
Respuesta
Primero escribamos el programa como fórmulas de Horn
- {vecino(X,Y,[X|[Y|Ls]])
- {¬vecino(X,Y,LS), vecino(X,Y,[W|Ls])}
Error al representar (función desconocida «\extendlatex»): {\displaystyle \extendlatex \Tree [ .{$\{\neg vecino(5,Y,[5,6,5,3])\}$} [ .{$\sigma = \{X \mapsto 5, Y \mapsto 6, Ls \mapsto [5,3]\}$\\$\Box\; \{{\color{blue}Y = 6}\}$} ] [ .{$\sigma = \{X \mapsto 5, W \mapsto 5, Ls \mapsto [6,5,3]\}$\\$\{\neg vecino(5,Y,[6,5,3])\}$} [ .{$\sigma = \{X \mapsto 5, W \mapsto 6, Ls \mapsto [5,3]\}$\\$\{\neg vecino(5,Y,[5,3])\}$} [ .{$\sigma = \{X \mapsto 5, Y \mapsto 3, Ls \mapsto []\}$\\$\Box\; \{{\color{blue}Y = 3}\}$} ] [ .{$\sigma = \{X \mapsto 5, W \mapsto 5, Ls \mapsto [3]\}\\{\color{red}falla}$} ] ] ] ] }
Ejercicio 04
Definir los siguientes predicados:
i. last(-L, -U), donde U es el ultimo elemento de la lista L. Definirlo en forma recursiva, y usando el predicado append definido de la siguiente manera:
append([], X, X). append( [H | T], Y, [H | Z]) :- append(T, Y, Z).
Respuesta
last(L, U) :- append(_, [U], L). last([U], U). last([_|Ls], U) :- last(Ls, U).
ii. reverse(+L, -L1), donde L1 contiene los mismos elementos que L, pero en orden inverso. Ejemplo: reverse([a,b,c], [c,b,a]). Realizar una definicion usando append, y otra sin usarlo. Mostrar el arbol de prueba para el ejemplo dado.
(*) Resolucion incorrecta: reverse([], []). reverse([H | T], [ReversedT | [H]]) :- reverse(T, ReversedT). (*) Resolucion correcta: reverse2([], []). reverse2([H | T], R) :- reverse2(T, ReversedT), append(ReversedT, [H], R).
iii. maxlista(+L, -M) y minlista(+L, -M), donde M es el maximo/minimo de la lista L.
maxlista([H], H). maxlista([H | T], H) :- maxlista(T, M), H >= M. maxlista([H | T], M) :- maxlista(T, M), H < M. minlista([H], H). minlista([H | T], H) :- minlista(T, M), H =< M. minlista([H | T], M) :- minlista(T, M), H > M.
iv. palindromo(+L, -L1), donde L1 es un palindromo construido a partir de L. Ejemplo: palindromo([a,b,c], [a,b,c,c,b,a]).
palindromo(L, P) :- reverse2(L, RevL), append(L, RevL, P).
v. doble(-L, -L1), donde cada elemento de L aparece dos veces en L1. Ejemplo: doble([a,b,c], [a,a,b,b,c,c]).
doble([], []). doble([H | T], [H | H | DT]) :- doble(T, DT).
vi. prefijo(-P, +L), donde P es prefijo de la lista L.
prefijo(P, L) :- append(P, _, L).
vii. sufijo(-S, +L), donde S es sufijo de la lista L.
sufijo(P, L) :- append(_, P, L).
viii. sublista(-S, +L), donde S es sublista de L. Esta version es para sublistas "continuas" en L.
sublista([], _). sublista(S, L) :- append(CasiL, _, L), append(_, S, CasiL), S \= [].
Esta version es para sublistas "no continuas" en L.
sublistaB([], []). sublistaB([H | SubsT], [H | T]) :- sublistaB(SubsT, T). sublistaB(SubsT, [_ | T]) :- sublistaB(SubsT, T).
ix. iesimo(-I, +L, -X), donde X es el I-esimo elemento de la lista L. Ejemplo: iesimo(2, [10, 20, 30, 40], 20).
iesimo(I, L, X) :- append(ListI, [X | _], L), length(ListI, I).
Ejercicio 05
Definir los siguientes predicados: i. mezcla(L1, L2, L3), donde L3 es el resultado de mezclar uno a uno los elementos de las listas L1 y L2. Si una lista tiene longitud menor, entonces el resto de la lista mas larga es pasado sin cambiar. Verificar la reversibilidad, es decir si es posible obtener L3 a partir de L1 y L2, y viceversa. Ejemplo: mezcla([a,b,c], [d,e], [a,d,b,e,c]).
mezcla(L1, [], L1). mezcla([], L2, L2). mezcla([H1 | T1], [H2 | T2], [H1, H2 | T12]) :- mezcla(T1, T2, T12).
ii. split(N, L, L1, L2), donde L1 tiene los N primeros elementos de L, y L2 el resto. Si L tiene menos de N elementos el predicado debe fallar. ¿Cuan reversible es este predicado? Es decir, ¿que elementos pueden estar indefinidos al momento de la invocacion?
split(N, L, L1, L2) :- append(L1, L2, L), length(L1, N).
iii. borrar(+ListaConXs, +X, -ListaSinXs), que elimina todas las ocurrencias de X de la lista ListaConXs.
borrar([], _, []). borrar([H | XS], E, [H | YS]) :- E \= H, borrar(XS, E, YS). borrar([E | XS], E, YS) :- borrar(XS, E, YS).
iv. sacarDuplicados(+L1, -L2), que saca todos los elementos duplicados de la lista L1.
pertenece(E, L1) :- append(Principio, _, L1), append(_, [E], Principio). sacarDuplicados([], []). sacarDuplicados([H | T], [H | SinDups]) :- borrar(T, H, BorrarH), sacarDuplicados(BorrarH, SinDups). sacarDuplicados([H | T], SinDups) :- pertenece(H, T), sacarDuplicados(T, SinDups).
Ejercicio 06
Ejercicio 07
Definir el predicado aplanar(+Xs, -Ys), que es verdadero sii Ys contiene los elementos contenidos en algun nivel de Xs, en el mismo orden de aparicion. Los elementos de Xs son enteros, atomos o nuevamente listas, de modo que Xs puede tener una profundidad arbitraria. Por el contrario, Ys es una lista de un solo nivel de profundidad. Ejemplos:
?- aplanar([a, [3, b, []], [2]], [a, 3, b, 2]). ?- aplanar([[1, [2, 3], [a]], [[[]]]], [1, 2, 3, a]). aplanar([], []). aplanar([H | T], App) :- is_list(H), aplanar(H, AppH), aplanar(T, AppT), append(AppH, AppT, App). aplanar([H | T], App) :- not(is_list(H)), aplanar(T, AppT), append([H], AppT, App).
Ejercicio 08
Definir los siguientes predicados: i. ordenada(+L), que sera cierta si los elementos de L estan ordenados en forma ascendente.
ordenada([]). ordenada([_]). ordenada([X, Y | XS]) :- X =< Y, ordenada([Y | XS]).
ii. quicksort(+L, -L1), donde L1 es el resultado de ordenar L por el metodo de quicksort, que consiste en dividir a L en 2 sublistas con los menores y mayores al primer elemento, ordenar cada una de ellas y luego proceder a concatenarlas.
quicksort_partir([], _, [], []). quicksort_partir([H | T], E, [H | Menores], Mayores) :- (H =< E), quicksort_partir(T, E, Menores, Mayores). quicksort_partir([H | T], E, Menores, [H | Mayores]) :- H > E, quicksort_partir(T, E, Menores, Mayores).
quicksort([], []). quicksort([H | T], S) :- quicksort_partir(T, H, Menores, Mayores), quicksort(Menores, MenOrd), quicksort(Mayores, MayOrd), append(MenOrd, [H | MayOrd], S).
iii. inssort(+L, -L1), donde L1 es el resultado de ordenar L por el metodo de insercion, que consiste en insertar cada elemento en el lugar adecuado del resto de la lista ya ordenada.
insertar_ordenado([], E, [E]). insertar_ordenado([H | T], E, [E, H | T]) :- E =< H. insertar_ordenado([H | T], E, [H | S]) :- E > H, insertar_ordenado(T, E, S).
inssort([], []). inssort([H | T], S) :- inssort(T, SortT), insertar_ordenado(SortT, H, S).
Ejercicio 09
Definir un predicado rotar(+L, +N, -R), tal que R sea la lista L rotada N posiciones (la rotacion se debe hacer hacia la derecha si N>0 y hacia la izquierda si N<0). Ejemplos: rotar([1, a, 2, b, 3], 3, X) debe dar como respuesta X = [2, b, 3, 1, a] rotar([1, a, 2, b, 3], -3, X) debe dar como respuesta X = [b, 3, 1, a, 2]
modulus(N, Modulus, Result) :- Result is ((N mod Modulus) + Modulus) mod Modulus.
rotar(L, N, R) :- length(L, Length), modulus(N, Length, Rotate), append(Init, Tail, L), length(Tail, Rotate), append(Tail, Init, R).
Ejercicio 10
Definir un predicado que reciba una lista de numeros naturales y devuelva otra lista de numeros naturales, en la que cada numero n de la primera lista aparezca repetido n veces en forma consecutiva, respetando su orden de aparicion. Considerar que la lista original siempre esta instanciada. Ejemplo: para la lista [2, 3, 1, 0, 2] la salida es [2, 2, 3, 3, 3, 1, 2, 2].
repetir_n(_, 0, []). repetir_n(E, Times, [E | T]) :- Times > 0, TimesMenos1 is Times - 1, repetir_n(E, TimesMenos1, T).
repetir_numeros([], []). repetir_numeros([H | T], Reps) :- repetir_n(H, H, Hs), repetir_numeros(T, Ts), append(Hs, Ts, Reps).
Ejercicio 11
Escribir en Prolog un predicado que devuelva la mediana de una lista (la mediana es el elemento que se halla en la posicion del medio de dicha lista, tras ser ordenada). Utilizar los predicados definidos anteriormente. Considerar que la lista siempre esta instanciada.
mediana(L, M) :- quicksort(L, S), length(L, Length), Mitad is Length // 2, append(Primeros, [M | _], S), length(Primeros, Mitad).
Ejercicio 12
Escribir en Prolog los siguientes predicados:
interseccion(+X, +Y, -Z), tal que Z es la interseccion sin repeticiones de las listas X e Y, respetando en Z el orden en que aparecen los elementos en X.
interseccion_con_duplicados([], _, []). interseccion_con_duplicados([H | T], Y, [H | IntTY]) :- pertenece(H, Y), interseccion_con_duplicados(T, Y, IntTY). interseccion_con_duplicados([H | T], Y, IntTY) :- not(pertenece(H, Y)), interseccion_con_duplicados(T, Y, IntTY).
interseccion(X, Y, Z) :- interseccion_con_duplicados(X, Y, W), sacarDuplicados(W, Z).
interseccion([],_,[]). interseccion([X|Xs],Y,Z) :- member(X,Y), interseccion(Xs,Y,Z1), not(member(X,Z1)), append([X],Z1,Z). interseccion([X|Xs],Y,Z) :- member(X,Y), interseccion(Xs,Y,Z), member(X,Z). interseccion([X|Xs],Y,Z) :- not(member(X,Y)), interseccion(Xs,Y,Z).
Ejercicio 13
Un arbol binario se representara en Prolog con: nil, si es vacio. bin(sai, v, sad), donde v es el valor del nodo, sai es el subarbol izquierdo y sad es el subarbol derecho. i. Definir predicados en Prolog para las operaciones comunes de arboles: vacio, raiz, altura y cantidadNodos. Asumir siempre que el arbol esta instanciado.
max(X, Y, X) :- X >= Y. max(X, Y, Y) :- X < Y. min(X, Y, X) :- X < Y. min(X, Y, Y) :- X >= Y.
vacio(+Arbol).
vacio(nil).
raiz(+Arbol, -Raiz).
raiz(bin(_, Raiz, _), Raiz).
altura(+Arbol, -Altura).
altura(nil, 0). altura(bin(Izq, _, Der), N) :- altura(Izq, AlturaI), altura(Der, AlturaD), max(AlturaI, AlturaD, N).
cantidadNodos(+Arbol, -Cantidad).
cantidadNodos(nil, 0). cantidadNodos(bin(Izq, _, Der), N) :- cantidadNodos(Izq, CantI), cantidadNodos(Der, CantD), N is CantI + CantD + 1.
ii. Se define la profundidad de un nodo como la distancia desde la raiz hasta el mismo (la raiz tiene profundidad 0). Definir un predicado hpp que permita, dado un arbol binario instanciado, obtener la lista de todos los valores de las hojas que tengan profundidad par. Puede ocurrir que dos o mas hojas distintas tengan el mismo valor, pero en la respuesta de hpp los valores no deben repetirse. Ejemplo:
hpp( bin(bin(nil, 2, nil), 2, bin(bin(nil, 4, nil), 1, nil) ), L). L = [4]; No.
hpp(+Arbol, -L)
hpp_con_duplicados(nil, 0, []). hpp_con_duplicados(nil, 1, []). hpp_con_duplicados(bin(Izq, Root, Der), 0, [Root | Res]) :- hpp_con_duplicados(Izq, 1, ResI), hpp_con_duplicados(Der, 1, ResD), append(ResI, ResD, Res). hpp_con_duplicados(bin(Izq, _, Der), 1, Res) :- hpp_con_duplicados(Izq, 0, ResI), hpp_con_duplicados(Der, 0, ResD), append(ResI, ResD, Res).
iv. sacarDuplicados(+L1, -L2), que saca todos los elementos duplicados de la lista L1.
pertenece(E, L1) :- append(Principio, _, L1), append(_, [E], Principio). sacarDuplicados([], []). sacarDuplicados([H | T], [H | SinDups]) :- borrar(T, H, BorrarH), sacarDuplicados(BorrarH, SinDups). sacarDuplicados([H | T], SinDups) :- pertenece(H, T), sacarDuplicados(T, SinDups).
hpp(Arbol, Res) :- hpp_con_duplicados(Arbol, 0, Dups), append([_], L, Dups), sacarDuplicados(L, Res).
Ejercicio 14
Definir los siguientes predicados, utilizando la misma representacion de arbol binario definida en el ejercicio 13: i. aBB(+T) que sera verdadero si T es un arbol binario de busqueda.
maximo_vs(nil, N, N). maximo_vs(bin(Izq, Root, Der), N, Max) :- maximo_vs(Izq, Root, MaxI), maximo_vs(Der, N, MaxD), max(MaxI, MaxD, Max). minimo_vs(nil, N, N). minimo_vs(bin(Izq, Root, Der), N, Min) :- minimo_vs(Izq, Root, MinI), minimo_vs(Der, N, MinD), min(MinI, MinD, Min).
aBB(nil). aBB(bin(Izq, Root, Der)) :- aBB(Izq), aBB(Der), maximo_vs(Izq, Root, Root), minimo_vs(Der, Root + 1, Root + 1).
ii. aBBInsertar(+X, +T1, -T2) donde T2 resulta de insertar X en orden en el arbol T1.
aBBInsertar(X, nil, bin(nil, X, nil)). aBBInsertar(X, bin(Izq, Root, Der), bin(NuevoIzq, Root, Der)) :- X =< Root, aBBInsertar(X, Izq, NuevoIzq). aBBInsertar(X, bin(Izq, Root, Der), bin(Izq, Root, NuevoDer)) :- X > Root, aBBInsertar(X, Der, NuevoDer).
Ejercicio 15
Un arbol n-ario de naturales se representara en Prolog con: hoja(V), donde V es un natural segun la representaciøn de Prolog. nodo(V, Hijos), donde V es un natural segun la representaciøn de Prolog, e Hijos es una lista no vacia de arboles n-arios de naturales. Definir el predicado mayores(+Arbol, +Max) que dado un arbol n-ario de naturales (que podria contener variables en los nodos) devuelve verdadero si: Los naturales que contiene el arbol son menores o iguales a Max (en caso de ser variables, deberan instanciarse con valores en dicho rango). El valor de cada nodo del arbol es mayor que la suma de los valores de sus hijos.
ejemplo: mayores(nodo(X, [hoja(0), nodo(1,[hoja(0), hoja(0)]),nodo(4,[hoja(1), hoja(0), nodo(1, [hoja(0)])])]),9)
in_range(+Min, +Max, -Num).
in_range(Min, Max, Min) :- Min =< Max. in_range(Min, Max, N) :- Min =< Max, NextMin is Min + 1, in_range(NextMin, Max, N).
valor(hoja(V), V). valor(nodo(V, _), V).
mayores(hoja(V), Max) :- in_range(0, Max, V). mayores(nodo(V, [X]), Max) :- valor(X, Val), in_range(0, Max, Val), Val1 is Val + 1, in_range(Val1, Max, V). mayores(nodo(V, [X, Y | T]), Max) :- valor(X, Val), in_range(0, Max, Val), Val1 is Val + 1, in_range(Val1, Max, V), VMenosX is V - Val, mayores(nodo(VMenosX, [Y | T]), Max).
mayores no anda bien, no hace la suma de todos los subhijos, sino de los inmediatos... como se hace bien? facilmente?
Ejercicio 16
Definir el predicado combinador(+L,+D,+H,-XS), que debe dar verdadero cuando XS es una lista de naturales de longitud L, y cada uno de sus elementos XSi cumple que D ? XSi ? H. No se deben devolver soluciones repetidas. Por ejemplo:
combinador(2,3,5,X). X = [3,3] ; X = [3,4] ; X = [3,5] ; X = [4,3] ; X = [4,4] ; X = [4,5] ; X = [5,3] ; X = [5,4] ; X = [5,5] ;
in_range(+Min, +Max, -Min).
in_range(Min, Max, Min) :- Min =< Max. in_range(Min, Max, N) :- Min =< Max, NextMin is Min + 1, in_range(NextMin, Max, N).
combinador(+L, +D, +H, -XS).
combinador(0, _, _, []). combinador(L, Min, Max, [H | T]) :- L > 0, in_range(Min, Max, H), L1 is L - 1, combinador(L1, Min, Max, T).
Ejercicio 17
Un cuadrado semi-latino es una matriz cuadrada de naturales (incluido el cero) donde todas las filas de la matriz suman lo mismo. Por ejemplo:
1 3 0 2 2 0 todas las filas suman 4 1 1 2
Representamos la matriz como una lista de filas, donde cada fila es una lista de naturales. El ejemplo anterior se representaria de la siguiente manera: [[1,3,0],[2,2,0],[1,1,2]]. Se pide definir el predicado cuadradoSemiLatino(N,XS). El parametro N debe estar instanciado, y XS no puede estar instanciado. El predicado debe ir devolviendo matrices (utilizando la representaci on antes mencionada), que sean cuadrados semi-latinos de dimension N*N. Dichas matrices deben devolverse de manera ordenada: primero aquellas cuyas filas suman 0, luego 1, luego 2, etc.. Ejemplo: cuadradoSemiLatino(2,X). devuelve:
X = [[0, 0], [0, 0]] ; X = [[0, 1], [0, 1]] ; X = [[0, 1], [1, 0]] ; X = [[1, 0], [0, 1]] ; X = [[1, 0], [1, 0]] ; X = [[0, 2], [0, 2]] ;
etc. Para la implementacion de cuadradoSemiLatino se cuenta con el siguiente predicado:
desde(D, D). desde(D, X) :- DD is D+1, desde(DD, X).
desde(+Desde, -Numero).
desde(D, D). desde(D, X) :- DD is D+1, desde(DD, X).
lista_semi_latina(+Longuitud, +Suma, -Lista).
lista_semi_latina(0, 0, []). lista_semi_latina(Long, Suma, [H | T]) :- Long > 0, Suma >= 0, Long1 is Long - 1, in_range(0, Suma, H), NuevaSuma is Suma - H, lista_semi_latina(Long1, NuevaSuma, T).
rectanguloSemiLatino(+Columnas, +Filas, +Suma, -XS).
rectanguloSemiLatino(_, 0, Suma, []) :- Suma >= 0. rectanguloSemiLatino(Columnas, Filas, Suma, [H | T]) :- Filas > 0, Filas1 is Filas - 1, lista_semi_latina(Columnas, Suma, H), rectanguloSemiLatino(Columnas, Filas1, Suma, T).
cuadradoSemiLatino(+N, -XS).
cuadradoSemiLatino(N, X) :- desde(0, Suma), rectanguloSemiLatino(N, N, Suma, X).
Ejercicio 18
Sea la estructura Agenda, y los siguientes predicados disponibles: personas(+Agenda, -Personas), que tiene exito cuando Personas contiene toda la lista personas de la Agenda. edad(+Agenda, +Persona, -Edad), que tiene exito cuando la Persona tiene edad Edad la Agenda. Definir el predicado personasEnPromedio(+Agenda, +Edad, -Conjunto) que tenga exito cuando Conjunto sea una lista de Personas de la Agenda, cuyo promedio de edad sea menor a Edad.
personas(+Agenda, -Personas).
personas(agenda(Personas), Personas).
edad(+Agenda, +Persona, -Edad).
edad(agenda([persona(Nombre, Edad) | _]), Nombre, Edad). edad(agenda([persona(OtroNombre, Edad) | Resto]), Nombre, Edad) :- OtroNombre \= Nombre, edad(agenda(Resto), Nombre, Edad). subconjuntos_personas(agenda([]), []). subconjuntos_personas(agenda([H | T]), [H | Sub]) :- subconjuntos_personas(agenda(T), Sub). subconjuntos_personas(agenda([_ | T]), Sub) :- subconjuntos_personas(agenda(T), Sub).
promedio_edades(Personas, Edad).
suma_edades([persona(_, Edad)], Edad). suma_edades([persona(_, Edad) | T], Suma) :- suma_edades(T, SumaT), Suma is SumaT + Edad.
personasEnPromedio(+Agenda, +Edad, -Conjunto).
personasEnPromedio(Agenda, Edad, Conjunto) :- subconjuntos_personas(Agenda, Conjunto), suma_edades(Conjunto, Suma), length(Conjunto, Cantidad), Promedio is (Suma // Cantidad), Edad > Promedio.
caso: personasEnPromedio(agenda([persona(0, 0), persona(0, 1), persona(0, 2), persona(0, 3), persona(0, 4), persona(0, 5)]), 0, X).
Ejercicio 19
(opcional) Torres de Hanoi. Se tienen tres estacas A, B y C, y N discos de distintos tama˜nos, perforados en el centro. Los discos pueden apilarse en las estacas formando torres, y estan ubicados inicialmente en la estaca A en orden decreciente de tama˜no. El problema consiste en mover los discos de A a C de tal manera que terminen ordenados como lo estaban originalmente. La tarea debe efectuarse bajo las siguientes restricciones: En cada paso solo un disco puede moverse de una estaca a otra. Nunca puede ubicarse un disco sobre otro mas peque˜no. Usando Prolog, modelar y resolver el problema de las torres de Hanoi para tres estacas y N discos.
data Estacas = a | b | c data Movimiento = Mover Estacas Estacas
es_estaca(+E).
es_estaca(a). es_estaca(b). es_estaca(c).
estacas_diferentes(-E1, -E2, -E3).
estacas_diferentes(a, b, c). estacas_diferentes(a, c, b). estacas_diferentes(b, a, c). estacas_diferentes(b, c, a). estacas_diferentes(c, a, b). estacas_diferentes(c, b, a).
hanoi_mover(+N, +Desde, +Hasta, -Movimientos).
hanoi_mover(0, Desde, Hasta, []) :- es_estaca(Desde), es_estaca(Hasta). hanoi_mover(N, Desde, Hasta, Movimientos) :- N > 0, N1 is N - 1, estacas_diferentes(Desde, Hasta, Otra), hanoi_mover(N1, Desde, Otra, MovsDesdeOtra), hanoi_mover(N1, Otra, Hasta, MovsOtraHasta), append(MovsDesdeOtra, [mov(Desde, Hasta) | MovsOtraHasta], Movimientos).
hanoi(+N, -Movimientos).
hanoi(N, Movimientos) :- hanoi_mover(N, a, c, Movimientos).
