Tarefa 3: Minotauro

O professor da disciplina sugeriu que o laboratório 3 de MC202 fizesse uso de recursão. Apesar de ser uma técnica ensinada em MC102, é um conceito que demora a ser aprendido, ao meu ver porque exige maior abstração. Enfim, devido a essa dificuldade tal tópico costuma ser revisto em MC202.

A ideia que tive foi a de um problema de percorrer labirintos. A tarefa foi contextualizada com uma história da mitologia grega em que Teseu procura o Minotauro e para não se perder no caminho de volta utiliza uma corda cedida por Ariadne.

Para não ter que tratar múltiplas soluções, especifiquei uma regra de percurso: primeiro tenta-se ir em frente, se não houver sucesso, tente ir à direita e finalmente à esquerda. O primeiro passo consiste em encontrar a entrada, representada por um buraco na parede mais externa. É garantido que haverá exatamente um buraco. Depois disso, aplicamos a técnica de backtracking seguindo as regras acima até encontrar o Minotauro (representado pela letra ‘M’).

Para especializar um pouco mais o problema, exigi no enunciado que fosse impresso, além do caminho utilizado para chegar da entrada ao Minotauro, o caminho por onde ele passou. Essa informação adicional seria útil no caso em que o Minotauro não fosse encontrado, pois sem imprimir o caminho por onde Teseu passou, o mapa de saída seria igual ao de entrada. Porém, por distração acabei especificando que apenas fosse impressa uma string caso o Minotauro não fosse encontrado. Só percebi o erro que tinha cometido quando fui corrigir o laboratório de um aluno, cujo programa era mais ou menos o seguinte:

#include <stdio.h>
int main (){
    printf("O Minotauro eh lenda.");
}

Ele ia passar em 2 dos 12 testes do SuSy se não tivesse esquecido de pular linha.

Alguns alunos também tentaram detectar a existência do Minotauro pelo mapa de entrada: se o caracter ‘M’ fosse rodeado por paredes (‘X’) então ele não poderia ser encontrado. Essa é uma condição suficiente, mas não necessária (por quê?)

Finalmente, não sei se o enunciado é que ficou confuso demais ou se o conceito ainda não foi absorvido, mas o fato é que a maior parte dos alunos não entendeu que não era preciso voltar explicitamente para trás quando uma das direções não era a certa. Isso porque depois de retornar das chamadas recursivas obtemos esse efeito implicitamente.

Os comentários estão fechados.

%d bloggers like this: