Programação em Lógica, 2004/05
1º Teste
DI-FCT/UNL
13 de Maio de 2005
Programação em Lógica
1º Teste
Sem consulta - Duração: 2 horas
Notas Prévias: Deverá entregar exactamente 3 folhas, cada uma delas com a sua resolução de um
dos grupos do teste. Cada uma das folhas deve ter o seu nome, número de aluno e número do grupo
em causa (Grupo 1, Grupo 2 ou Grupo 3). Mesmo que não resolva um qualquer grupo, deve na mesma
entregar a folha, neste caso apenas com os dados acima.
Note que com estas regras não pode usar mais do que uma folha para responder a um grupo. Mas
uma folha para cada grupo deverá ser mais do que suficiente!
Grupo 1
Implemente em Prolog os predicados abaixo indicados. Em cada uma das alíneas, pode usar os
predicados das alíneas anteriores, mesmo que não os tenha feito. Neste grupo serão valorizadas as
respostas com recursividade terminal.
1 a)
divisivel(+N1,+N2) que sucede se e só se o número N1 for divisível por N2 (i.e se
N1 dividido por N2 der resto 0).
1 b)
divisivelNenhum(+N,+LN) que, dado um número N e uma lista de números em LN,
sucede se e só se o número N não for divisível por nenhum dos números em LN.
1 c)
primos(+N,-Primos), que devolve em Primos a lista de todos os números primos
menores ou iguais a um N dado. Por exemplo:
?- primos(40,P).
P = [37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2];
no
Como sugestão, note que se já souber todos os números primos P até um dado X qualquer é
muito fácil determinar se Y=X+1 é primo: é primo se e só se não for divisível por nenhum
dos números em P.
Grupo 2
O que se pretende neste grupo é fazer um programa que ajude no plágio de trabalhos feitos em Prolog.
Claro que não deverá tentar fazer isto fora deste teste ☺
Mas vamos lá a isto. Para começar a primeira ideia é simples: arranja-se uma lista de “substituições” de
nomes; lê-se um ficheiro com o programa original, e cria-se um novo ficheiro igualzinho ao original
mas depois de feitas todas as substituições de nomes.
2 a)
Comece por implementar o predicado substituiTermo(+T1,-T2,+Subs) que aplica
no termo T1 todas as substituições na lista Subs, devolvendo o termo resultado em T2.
Uma lista de substituições é uma lista de pares V1-V2, denotando tal par que o valor V1
deve ser substituído por V2. Por exemplo:
?- substituiTermo( a(f(1),b(X,a)), T2, [a-aa,b-ola]).
T2 = aa(f(1),ola(X,aa));
no
2 b)
Faça agora o predicado plagio(+Original,+NovoFich,+Subs) que, dado em
Original o nome do ficheiro do programa original e em Subs a lista de substituições de
nomes, cria o ficheiro plagiado com o nome NovoFich.
Página 1 de 2
Programação em Lógica, 2004/05
1º Teste
Grupo 3
Todos vocês conhecem o jogo do galo. Por isso nem irei entrar em muitos detalhes sobre o que se trata
e como se joga. Apenas relembrando rapidamente: é um jogo de dois jogadores (chamemos x a um
deles e o ao outro), que se joga num tabuleiro de 3 por 3; de cada vez um jogador coloca uma marca
numa posição livre do tabuleiro; ganha aquele que primeiro conseguir 3 peças suas em linha (vertical,
horizontal ou diagonal); se se chegar a uma situação em que não há posições livres, e ninguém ganhou,
então o jogo termina empatado.
o
Para implementar um jogo do galo, a primeira coisa a fazer é escolher uma
estrutura de dados para representar o tabuleiro. Neste grupo, iremos assumir que
o
o tabuleiro é representado por uma lista com 3 listas (cada uma representando
uma linha do tabuleiro) de 3 elementos (cada um representando uma posição da
linha). Uma posição livre é representada por uma variável livre. Por exemplo, o
tabuleiro inicial, com todas as posições livres, pode ser representado por
[[P1,P2,P3],[P4,P5,P6],[P7,P8,P9]], e o tabuleiro da figura
[[o,x,P3],[o,x,x],[P7,o,P9]].
x
x
x
o
pela
lista
Vamos então fazer em Prolog alguns predicados que ajudam a jogar ao galo…
3 a)
posicaoLivre(+Tabuleiro,-Posicao) que sucede unificando a variável
Posicao com uma das variáveis livres (que corresponde a uma posição livre) no
Tabuleiro. Em backtracking deverão ser devolvidas, uma a uma, todas as possíveis
posições livres. Por exemplo, para o tabuleiro da figura:
?- T
P
P
P
no
=
=
=
=
[[o,x,P3],[o,x,x],[P7,o,P9]], posicaoLivre(T,P).
P3;
P7;
P9;
3 b)
jogada(?Tabuleiro,+Jogador) que sucede instanciando uma das posições livres do
Tabuleiro com a marca em Jogador. Em backtracking deverão ser devolvidas, uma a
uma, todas as possíveis instanciações.
3 c)
vitoria(+Tabuleiro,+Jogador) que sucede se e só se no Tabuleiro o
Jogador ganha (i.e. tem 3 peças em linha horizontal, vertical ou diagonal).
3 d)
boaJogada(?Tabuleiro,+Jogador), que instancia uma posição livre do tabuleiro
com uma jogada do Jogador, calculada de acordo com a seguinte estratégia: Se existe
alguma jogada que possibilita ao jogador ganhar imediatamente, então essa jogada deve ser
feita; caso contrário, se existir alguma posição livre onde caso o outro jogador aí jogasse
ganhava, então deve-se jogar para essa posição (evitando assim que o outro aí ganhe
imediatamente); caso contrário deve ser escolhida uma qualquer jogada. Por exemplo, para o
tabuleiro da figura, se for o o a jogar:
?- T = [[o,x,P3],[o,x,x],[P7,o,P9]], boaJogada(T,o).
T = [[o,x,P3],[o,x,x],[o,o,P9]]
P3=_
P7=o
no
porque assim o o ganha imediatamente. Se fosse o x a jogar:
P9=_ ;
?- T = [[o,x,P3],[o,x,x],[P7,o,P9]], boaJogada(T,x).
T = [[o,x,P3],[o,x,x],[x,o,P9]]
P3=_
P7=x
P9=_ ;
no
porque não lhe é possível ganhar imediatamente, e assim evita que o opositor ganhe logo a
seguir jogando para P7.
Note que, obviamente, esta não é a melhor estratégia para jogar ao galo. Mas a
implementação da melhor estratégia seria um pouco mais complicada e por isso neste teste
apenas vos é exigida esta simplificada.
Página 2 de 2