Desafios de Prolog

Degraus / Os dez degraus do Miguel

Saíu no CENPL'98

``À 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?"
in "Pierre Berloquin, 100 Jogos Lógicos, O Prazer da Matemática, no 4, Gradiva"

Tarefa

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

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.

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

Sugestão para resolver

Espreite o que faz o predicado findall/3 na documentação do YAP. E já agora o que fazem o all/3, bagof/3 e setof/3? Sim, vocês já deram isso nas aulas téoricas e por isso não era necessário lembrar, pois não? ;-)

Desafio Extra (não saíu no CENPL'98)

Consegue detectar alguma lógica no N, ou seja, no número de possibilidades diferentes? Consegue explicá-la? É alguma sequência conhecida? Consegue fazer um novo predicado degraus_num/2 que devolva apenas o número de possibilidades diferentes, mas funcione para números muitos maiores?

Exemplo: 

         ?-degraus_num(45,N).
           N = 1836311903
nota: é suposto o Yap dar instantaneamente o resultado acima descrito :-)

Alunos que enviaram soluções correctas

Resolveram problema e desafio extra

Uma possível solução

Última actualização: