Tarefa 5: DNA

Nesse extenso intervalo sem postar, especifiquei três laboratórios: python (listas generalizadas), do qual falei no post anterior; dna (árvores binárias), que comentarei nesse post; e avl, a tarefa que está sendo feita atualmente.

A tarefa basicamente pede para avaliar uma expressão através de árvores binárias. Não é difícil encontrar implementações que envolvam avaliações de expressões do tipo:

E para não acontecer de o pessoal pegar código pronto, optei por modificar ligeiramente a especificação. Ao invés de avaliar expressões envolvendo números, o laboratório consistia em avaliar conjuntos. Ao invés de números a expressão consistia de variáveis representando um conjunto de características e no lugar dos operadores de adição, subtração, etc, inclui os operadores de união, interseção e diferença.

A partir daí, deixei os alunos implementarem do jeito que quisessem. Porém, alguns truques facilitam a tarefa:

1) As características eram dadas como strings. Porém, podemos guardar as strings em um dicionário (vetor de strings) e trabalhar só com o índice das strings nesse dicionário (int).

2) Quando os elementos do conjunto estão ordenados, é mais simples (e eficiente) implementar as operações sobre conjuntos. A ideia é parecida com a do merge sort: mantemos ponteiros para cada um dos conjuntos A e B. No começo cada qual aponta para o primeiro elemento do seu respectivo conjunto. Seja o valor do elemento apontado pelo ponteiro do conjunto A e o equivalente para o conjunto B. Na união, se , incluímos na união e andamos com o ponteiro de A. Se fazemos o mesmo com o ponteiro de B, se , incluímos qualquer um dos dois, mas apenas um, pois em conjuntos não consideramos elementos repetidos, e então andamos com ambos os ponteiros. Entendida a ideia, é simples derivar o algoritmo para a operação de interseção e diferença.

Para padronizar a resposta e comparar com minha saída no SuSy, exigi que as características do conjunto final estivessem ordenadas. Porém os alunos não tinham visto ordenação ainda, então passei um código que supostamente iria ordenar um vetor de strings:

qsort(saida, n, sizeof(char*MAXLEN), cmp);

Para quem não sabe, o qsort é uma função que implementa o quicksort e está disponível na biblioteca padrão do C. A função exige que você passe uma função de comparação por parâmetro, que compara duas strings. Porém, se o vetor de strings foi alocado estaticamente (minha sugestão inicial), a função não funciona. Uma alternativa é declarar o vetor como um vetor de ponteiros de char e alocar cada string dinamicamente (porém com tamanho fixo MAXLEN). Aí sim funciona. Outra alternativa, a que acabei sugerindo após descobrir o erro, é ordenar apenas os índices do vetor. Para isso nós orderamos um vetor auxiliar (vetor de permutação), indicando que a posição do i-ésimo elemento é . Inicialmente .

A função de comparação recebe dois inteiros i e j, mas na verdade compara as respectivas linhas da matriz (com strcmp). A vantagem desse método é que as strings continuam no mesmo lugar. O que muda são apenas os índices.

Os comentários estão fechados.

%d bloggers like this: