Guião para a Sexta Aula Prática de IPL

Delfim F. Marado Torres

16 de Abril de 1999

Agradeço comentários, sugestões ou correccões. O meu endereço de correio electrónico é < delfim@mat.ua.pt > . Desde já obrigado.

1  Objectivos da aula

Resolução dos seguintes problemas:

2  Élle-é-érre: Ler sequências de algarismos

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.

2.1  Tarefa

Escreva, em Prolog, um predicado binário eleiturade(S,E) em que a lista de algarismos S é a leitura da lista de algarismos E.

2.2  Os Resultados

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])

2.3  Uma solução

         %%
         %% 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.

3  Os dez degraus do Miguel

``À 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

3.1  Tarefa

A sua tarefa consiste em desenvolver um programa em Prolog que resolva este problema, para um número qualquer de degraus.

3.2  Os Dados

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.

3.3  Os Resultados

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]]

3.4  Uma solução

         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %% 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).

Footnotes:

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.