MC600 - Segundo semestre de 2003 - LISTA 8
------------------------------------------
 

1. Defina os seguintes predicados em PROLOG:
    * mother(X,Y).
    * father(X,Y).
    * grandmother(X,Y).
    * grandfather(X,Y).
    * sibling(X,Y).    Não se esqueça que ninguém é irmão de si mesmo. 
    * aunt(X,Y).
    * uncle(X,Y).
    * cousin(X,Y).  

Respostas:

mother(X,Y) :- female(X), parent(X,Y).

father(X,Y) :- male(X), parent(X,Y).

grandmother(X,Y):- mother(X, Z), parent(Z, Y).

grandfather(X,Y):- father(X,Z), parent(Z, Y).

Meio-Irmãos:
sibling(X,Y) :- parent(P,X), parent(P,Y), X \= Y.

Irmãos:
sibling(X,Y) :- mother(M,X), mother(M,Y), father(F,X), father(F,Y), X\=Y.

aunt(X,Y) :- female(X), sibling(X,K), parent(K,Y).

uncle(X,Y) :- male(X), sibling(X,K), parent(K,Y).

cousin(X,Y) :- parent(P1,X), parent(P2,Y), sibling(P1,P2).


2. Monte uma base de dados usando apenas fatos do tipo parent(fulano,
ciclano), male(beltrano) e female(fulana) de modo que esta base de
dados represente a sua família desde seus avós até sua geração e teste
seus predicados do exercício 1.  O fato parent(fulano, ciclano)
significa que fulano é pai ou mãe de ciclano.


3. Os números de Fibonacci são definidos da seguinte forma:
    F(0) = 0
    F(1) = 1
    F(n) = F(n-1) + F(n-2), para n > 1.

  Defina um predicado fib(N,F) que calcule o valor do N-ésimo número de
  Fibonacci.

Resposta:

fib(0,0).
fib(1,1).
fib(N,F):- N>1,
	   N1 is N-1,
	   Fib(N1,F1),
	   N2 is N-2,
	   Fib(N2,F2),
	   F is F1+F2.
Apesar de correta, esta definição roda em tempo exponencial (uma
chamada gera duas, que geram duas cada, etc.)

Eis uma definição que roda em tempo linear:

% fib(N,F,F1) é satisfeito quando F é o n-ésimo número de Fibonacci, e
% F1 é o (n+1)-ésimo número de Fibonacci.  Ou seja, dado N, ela calcula
% F(n) e F(n+1) junto!

fib(0,0,1).
fib(N,F,F1) :- N>1,
	       N1 is N-1,
	       fib(N1,Fant,F),
	       F1 is Fant+F.

fib(N,F) :- fib(N,F,_).


4. Defina um predicado member(X,L) que é satisfeito quando X é um
elemento da lista L.

Resposta:

member(X,[X|_]).
member(X,[_|T]):-member(X,T).


5. Defina um predicado count(X,L,N) que é satisfeito quando o elemento
X ocorre em L exatamente N vezes.

Resposta:

count( _ , [ ], 0).
count( X, [H | T], N) :- X\=H, count( X, T, N).
count( X, [X | T], N) :- count( X , T , N1), N is N1+1.