Implemente e submeta uma solução para o problema [DAA 021] Bakugans.
Para efeitos da nota atribuída à resolução de exercícios ao longo do semestre, os exercícios a submeter desta aula são:
Prazo de submissão: 22 de Novembro (submeter no Mooshak de DAA)
Não se esqueçam que qualquer ajuda que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem.
Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota. Relebre que cada aula vale 10% da nota desta componente.
Para um problema contar tem acertar todos os testes. Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.
Nesta aula iremos abordar conceitos de programação dinâmica. Será por isso conveniente ver o que foi falado nas teóricas:
Quase todas as linguagens têm uma implementação de árvores de pesquisa equilibradas que garantem operações logarítmicas para pesquisa, inserção e remoção. O objectivo deste exercício é conhecer duas dessas estruturas, que nas versões actuais dos compiladores respectivos são implementadas usando árvores red-black:
Para os estudantes que usam C, a ideia neste exercício é verem o código de C++. Vão notar que o código é quase igual, incluindo na maneira de ler e escrever (podem pensar no C como um subset do C++), mas que usa pedaços de C++ quando necessário. Para compilarem basta usar g++ na linha de comando em vez de gcc (ex: g++ -Wall -o bst bst.cpp)
Façam download do programa respectivo, executem-no e procurem perceber o que o programa faz, seguindo a documentação dada quando necessário.
Nota: o código de C++ dado apenas funciona em versões de C++ ≥ 11 (por causa do uso do auto e do "range-for"). Se tiverem uma versão antiga do gcc pode ser necessário ativar esse modo (compilar com a flag -std=c++11). Se tiverem um gcc mesmo antigo que ainda não suporte C++11 fica aqui uma versão do código mais "antiga": bst_beforecpp11.cpp
Implemente e submeta uma solução para o problema [DAA 021] Bakugans.
Implemente e submeta uma solução para o problema [DAA 022] Árvores Red-Black.
Use como ponto de partida o seguinte código base que já tem definida uma estrutura de dados para guardar uma árvore e que já lê o input:
Este exercício é um extra, e não é considerado essencial no contexto desta aula. Use-o se quiser consolidar os seus conhecimentos.
Implemente e submeta uma solução para o problema [DAA 023] Palavras Numeradas.
Todas as semanas vou colocar disponível pelo menos mais um exercício um pouco mais desafiante.
Para esta semana o desafio é mais fácil que os das semanas anteriores, e não envolve nenhum tipo de matéria de que não tenhamos já falado. A dificuldade passa unicamente em como ser eficiente na resposta das queries (que podem ser 100 mil), sendo que por isso um algoritmo quadrático não passará no tempo. O problema está disponível para submissão no Mooshak:
Se já tiverem feito tudo e estiverem "presos" neste, e quiserem mesmo fazer o desafio, podem contactar-me para eu "dosear" as dicas.