Agradeço comentários, sugestões ou correccões. O meu endereço de correio electrónico é < delfim@mat.ua.pt > . Desde já obrigado.
Resolução dos seguintes problemas:
Considere a seguinte cadeia de algarismos: 118. Se a ler, em voz alta agrupando os algarismos homónimos, leria: dois uns um oito, que pode por sua vez ser representada por uma cadeia de algarismos: 2118. Esta cadeia pode agora por sua vez ser lida, obtendo-se: 122118.
Escreva, em Prolog, um predicado binário eleiturade(S,E) em que a lista de algarismos S é a leitura da lista de algarismos E.
Como exemplos, tem que os seguintes predicados são verdadeiros:
eleiturade([2,1,1,8],[1,1,8])
eleiturade([1,2,2,1,1,8],[2,1,1,8])
eleiturade([1,1,1,2,1,3],[1,2,3])
eleiturade([3,1,1,2,1,1,1,3],[1,1,1,2,1,3])
eleiturade([1,3,2,1,1,2,3,1,1,3],[3,1,1,2,1,1,1,3])
Como estamos a usar o Prolog, e queremos que cada algarismo seja um elemento da lista, temos que:
eleiturade([1,0,1],[1,1,1,1,1,1,1,1,1,1])
%%
%% Realizado pelos alunos de IPL'99 na aula teorico-pratica
%% -- 16/Abril/1999 -- partindo de uma ideia da Daxa.
%%
%% Introduzido em computador por Cristina.
%%
%% Testado por Delfim.
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ?- desmembra(123,L).
% L = [1,2,3]
%
% ?- desmembra(7,L).
% L = [7]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
desmembra(N,L):- name(N,LA),
conv_ascii(LA,L).
conv_ascii([],[]).
conv_ascii([XA|RA],[X|R]) :-
name(X,[XA]),
conv_ascii(RA,R).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ?- tabela(L,[1,1,1]).
% L = [3,1]
%
% ?- tabela(L,[3,3,3,3,3,3,3,3,3,3,3,3]).
% L = [1,2,3]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
tabela(LF,[X|R]) :- tamanho([X|R],N),
desmembra(N,L),
junta(L,[X],LF).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ?- agrupa([1,1,8],L).
% L = [[1,1],[8]]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
agrupa([],[]).
agrupa(L,[L1|R]) :- separa(L,L1,L2),
agrupa(L2,R).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ?- separa([1,1,8,2,2],L1,L2).
% L1 = [1,1]
% L2 = [8,2,2]
%
% ?- separa([8,2,2,1],L1,L2).
% L1 = [8]
% L2 = [2,2,1]
%
% L1 possui os primeiros elementos todos iguais
% L2 possui os restantes elementos
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
separa([],[],[]).
separa([X],[X],[]).
separa([X,X|R],[X|C],L2) :- separa([X|R],C,L2).
separa([X,Y|R],[X],[Y|R]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% PREDICADO PRINCIPAL %%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
eleiturade(O,I) :- agrupa(I,LL),
usa_tabela(LL,O), !.
usa_tabela([],[]).
usa_tabela([X|R],L) :- tabela(Y,X),
usa_tabela(R,T),
junta(Y,T,L).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% PREDICADOS AUXILIARES %%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
junta([],L,L).
junta([X|R],L,[X|RR]) :-
junta(R,L,RR).
tamanho([],0).
tamanho([_|R],N) :-
tamanho(R,N1),
N is N1 + 1.
``À entrada da casa do Miguel há uma escada com 10 degraus. Cada vez que entra em casa, o Miguel avança pelas escadas subindo um ou dois degraus em cada passada. De quantas maneiras diferentes pode o Miguel subir as escadas?''1
A sua tarefa consiste em desenvolver um programa em Prolog que resolva este problema, para um número qualquer de degraus.
O único dado necessário para a resolução deste problema é o número de degraus. Esse valor será um parâmetro do predicado jogo_degraus que tem de desenvolver, como se explica a seguir.
O seu programa deve ser activado através do predicado jogo_degraus/3 que
recebe o número de degraus e devolve o número de possibilidades diferentes de subir as
escadas, assim como a respectiva lista de possibilidades (cada possibilidade é, por sua
vez, também representada por uma lista).
Exemplo:
?-jogo_degraus(3,N,L).
N = 3
L = [[1,1,1],[1,2],[2,1]]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Realizado por Delfim F. Marado Torres
%% -- 07/Abril/1998 --
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% jogo_degraus(NumeroDegraus,
%% NumPossibilidades,
%% ListaPossibilidades)
%%
%% Exemplo:
%% ?- jogo_degraus(5,N,L).
%% N = 8
%% L = [[1,1,1,1,1],[1,1,1,2],[1,1,2,1],
%% [1,2,1,1],[1,2,2],[2,1,1,1],
%% [2,1,2],[2,2,1]]
%% yes
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
jogo_degraus(ND,NP,LP) :-
degraus(ND,LP),
comprimento(LP,NP),!.
comprimento([],0).
comprimento([_|R],N) :-
comprimento(R,N1),
N is N1 + 1.
degraus(1,[[1]]).
degraus(2,[[1,1],[2]]).
degraus(N,L) :-
N1 is N-1,
N2 is N-2,
degraus(N1,L1),
degraus(N2,L2),
adiciona(1,L1,NL1),
adiciona(2,L2,NL2),
concatena(NL1,NL2,L).
adiciona(_,[],[]).
adiciona(N,[X|R],[NX|NR]) :-
concatena([N],X,NX),
adiciona(N,R,NR).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Predicados auxiliares normalmente disponibilizados
%% nos interpretadores de Prolog:
%% concatena/3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
concatena([],L,L).
concatena([X|R],L,[X|C]) :-
concatena(R,L,C).
1 José Paulo Viana e Cristina Sampaio, desafios, Pública (revista integrante do Jornal Público), Domingo, 29 Março (também 5 Abril), 1998.