A demonstração desta semana é inspirada no jogo Labyrinth (1983) [por Axis para o ZX Spectrum]. Este programa tem como único objectivo familiarizar os concorrentes com esta técnica insólita de programar no ZX Spectrum.
A versão desta semana tem um gerador de labirintos que usa um algoritmo recursivo (prima uma tecla para ver o gerador em slow motion), na próxima semana mostraremos um algoritmo tão simples que até uma criança de cinco anos consegue perceber.
Os algoritmos recursivos são mais simples mas mais abstratos. Os fundamentos desta técnica são ensinados na disciplina de matemática (indução matemática). A ideia principal da recursividade é uma rotina invocar-se a si própria. Em BASIC do ZX Spectrum isto não costuma ser feito porque o ZX Spectrum não tem variáveis locais a uma rotina.
Vejamos uma explicação simplificada da recursividade com um exemplo da função factorial:
Método iterativo:factorial(N) = N * (N-1) * (N-2) * .. * 5 * 4 * 3 * 2 * 1
Exemplo:
factorial(5) = 5 * 4 * 3 * 2 * 1
Método recursivo:
factorial(0) = 1
factorial(N) = N * factorial(N-1)
Exemplo:
factorial(5) = 5 * factorial(4)
Aqui, factorial(4) vai ser substituído por 4 * factorial(3), isto dá:
etc.
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1 * factorial(0)
= 5 * 4 * 3 * 2 * 1 * 1
Para correr o programa online, clicar aqui.
Para ver a listagem e fazer o download dos ficheiros clicar aqui.
Convidamos os leitores a examinar a listagem e a fazer alterações no programa. Todos os programas BASIC Apascalado que apresentamos nesta série podem ser melhorados e todos os leitores estão convidados a melhorá-los. Por exemplo, a versão da Axel mostrava o caminho percorrido no labirinto e alguns jogos têm monstros dentro do labirinto.
Quem estiver interessado no concurso, pode ler o regulamento aqui.
Quem estiver interessado em saber mais sobre esta linguagem e sobre como compilar os programas, pode clicar aqui.
Em caso de dúvidas, não hesitem em perguntar.
Sem comentários:
Enviar um comentário