ing. informatico

INDICACIONES PARA LA SOLUCIÓN A ALGUNOS PROBLEMAS DE LA
RELACION 6
PINTAR UN SOBRE
COLOREADO DE MAPAS
MOCHILA
REINAS
ENCASILLADO
Se usarán los siguiente predicados genéricos en todos los ejemplos
miembro(X,[X|Xs]).
miembro(X,[Y|Xs]):miembro(X,Xs).
selecciona(X,[X|Xs],Xs).
selecciona(X,[Y|Xs],[Y|Ys]):selecciona(X,Xs,Ys).
longitud([],0).
longitud([X|Xs],N):longitud(Xs,N1),
N is N1+1.inversa([],[]).
inversa([X|Xs],Zs):inversa(Xs,Ys),
concatena(Ys,[X],Zs).
concatena([],Ys,Ys).
concatena([X|Xs],Ys,][X|Zs]):concatena(Xs,Ys,Zs).

1. PINTAR UN SOBRE SIN LEVANTAR EL LAPIZ
La figura del sobre es
e
d

c

a

b

Las líneas puede representarse por
par(a,b).
par(a,c).
par(a,d).
par(b,c).
par(b,d).
par(c,d).
par(c,e).
par(d,e).
y un trazo estrazo(X,Y):par(X,Y).
trazo(X,Y):par(Y,X).
“sobre(+S) = S es la lista de la forma [tr(a,b),tr(b,c),...] “
sobre(S):genera([],S1),
inversa(S1,S).
Debe escribirse el predicado genera:
− El primer argumento de genera actúa de acumulador de los trazos realizados
− El segundo argumento de genera es para devolver el resultado
− El resultado se invierte para que salga según se traza

2. COLOREADO DE MAPAS
Dadoun mapa con países, se pretende colorear el mapa sin que países fronterizos tengan
colores repetidos.
Se indicaran los colores disponibles como hechos.
color(az).
color(vd).
color(rj).
color(am).
Se indicaran la relación de vecindad de países como hechos.
Por ejemplo, para el mapa
a

b
c
d

e

se tienen los hechos
vecino(a,b).
vecino(a,c).
vecino(a,d).
vecino(b,c).vecino(b,d).
vecino(b,e).
vecino(c,d).
vecino(c,e).
vecino(d,e).
El predicado frontera indica cuando dos países tienen frontera común
frontera(X,Y):- vecino(X,Y).
frontera(X,Y):- vecino(Y,X).

2.a SOLUCION AL COLOREADO DE MAPAS CON ESTRUCTURAS DE
DATOS INCOMPLETAS
Se llama al predicado colorear con una estructura de datos incompleta (con variables
libres) y se pretende que Prolog complete dichaestructura (asigne valor a las variables).
colorear([cl(a,CA),cl(b,CB),cl(c,CC),cl(d,CD),cl(e,CE)])

El procedimiento a seguir es:
− se llama a colorear con la estructura de datos incompleta,
− se colorea la cola,
− se busca para la cabeza un color compatible con los asignados a la cola.

2.b SOLUCION ITERATIVA AL COLOREADO DE MAPAS
Se debe escribir el predicado colorear2(+Paises,+Acumulador, -Sol)
donde:
− La lista Países (de entrada) será [a,b,c,d,e]
− La lista Acumulador es un acumulador donde se guardan las asignaciones de
colores y que inicialmente debe ser vacía
− La lista Sol (de salida) será [cl(a,az),cl(b,..),cl(c,..),...]
El procedimiento a seguir es:
− Se parte de la lista de países a colorear
− Se van coleccionando la asignación de color que se hace para cadapaís
cl(pais,color)
− Si la lista de países que falta por asignar es vacía, la asignación que se ha hecho
hasta el momento es la solución.
− Si la lista tiene cabeza y cola,
− Se le asigna color a la cabeza,
− Se comprueba que ese color es compatible con los colores ya asignados
− Se llama recursivamente a colorear guardando la nueva asignación en la lista de
asignaciones

3. ELPROBLEMA DE LA MOCHILA
Consiste en llenar una mochila de capacidad limitada con una serie de objetos de los que
se conoce su nombre, volumen y precio. Diseñar un programa que devuelva todas las
soluciones, con su costo, es decir con la suma de los precios de los artículos
introducidos.
Los datos de los objetos disponibles se tendrán en la forma
art(nombre,volumen,precio)
Los datos los extraemos deuna estructura (para no tener que escribirlos varias veces)
datos([art(oro,20,35),
art(plata,30,25),
art(mercurio,10,40),
art(hierro,40,20),
art(aluminio,30,50),
art(cobre,20,15),
art(paja,70,5),
art(madera,60,10),
art(papel,40,25),
art(cristal,20,30),
art(barro,70,15),
art(aceite,35,20)]).
Debe escribirse el predicado:
mochila(+VolumenLibre,-PrecioTotal,-Solucion)
en donde:
−...