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.