É encorajado que vão falando com os docentes e outros colegas se tiverem dificuldades. No entanto, qualquer ajuda mais direta 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.
Cada aula vale 11% da nota desta componente. Como existem 11 aulas com submissões, pode ter pontuação máxima mesmo sem ter feito tudo.
Para um problema contar tem acertar todos os testes (ou seja, ter accepted). Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.
Para ter 100% bastará sempre resolver os exercícios do guião principal.
Conteúdos das teóricas
Nesta aula iremos abordar conceitos de árvores binárias de pesquisa. Será por isso conveniente ver o que foi falado nas teóricas:
Exercício 1) Compreender Árvores Binárias de Pesquisa
Código de árvores binárias de pesquisa.
Faça download do código dado nas teóricas e compile-o:
BSTree - Árvore binária de pesquisa (ex. métodos: número de nós, altura, contains, inserção e remoção; impressões preorder, inorder, postorder, em largura)
(note que também precisa do código de listas, pilhas e filas, por causa dos métodos de DFS e BFS)
Espreite o ficheiro BSTNode.java para ver como um nó é descrito, e note na assinatura como o tipo T tem de ser comparavél ou seja, implementa o interface Comparable.
Um primeiro teste.
Execute a classe de teste das árvores binárias de pesquisa: $ java TestBSTree
Espreite e acompanhe a implementação do método insert da classe BSTree. Relembre que numa árvore binária de pesquisa, para um qualquer nó, todos os elementos da subárvore esquerda são menores e todos os elementos da subárvore direita são maiores. Para o ajudar a compreender, a imagem seguinte mostra o conteúdo da árvore após cada inserção (em cada passo o elemento inserido está indicada a amarelo):
Depois da remoção de 14, que número ficou na raíz? Acompanhe a implementação do método remove da classe BSTree para verificar como isto é feito.
Visualizando Inserções e remoções.
Procure desenhar no seu caderno como ficaria uma árvore binária de pesquisa depois de inserir os seguintes elementos (por esta ordem): 4 8 1 3 9 2 7 6.
Depois de desenhar, use a seguinte página para verificar se acertou no desenho da árvore:
Experimente retirar e inserir mais alguns elementos, procurando primeiro confirmar como ficaria a árvore, e depois usando a página para confirmar o que previu.
Exercício 2) Um exercício envolvendo árvores binárias de pesquisa
Neste exercício vai pode garantir que percebe como internamente a árvore binária de pesquisa está organizada.
Procure aproveitar as características duma árvore binária de pesquisa
O menor elemento está sempre na folha mais à esquerda
O maior elemento está sempre na folha mais à direita
// [ED208] Minimo e Maximo// Pedro Ribeiro (DCC/FCUP)public T minValue(){
BSTNode<T> cur = root;while(cur.getLeft()!=null) cur = cur.getLeft();return cur.getValue();}public T maxValue(){
BSTNode<T> cur = root;while(cur.getRight()!=null) cur = cur.getRight();return cur.getValue();}
Exercício 3) Usando árvores binárias de pesquisa para representar conjuntos
Uma árvore binária de pesquisa mapeia muito bem num TAD conjunto. Este exercício pede-lhe precisamente para resolver de forma simples um pequeno problema que na sua essência pode ser resolvido pensando em conjuntos.
Este problema é uma versão simplificada de um problema resolvido nas aulas teóricas (ver slides 70 e 71)
Crie uma árvore binária de pesquisa para guardar strings
Insira as palavras na árvore de pesquisa (método insert()). Os elementos iguais são descartados. Para ler palavras pode usar o método next() da classe Scanner.
No final imprima o número de nós da árvore (método numberNodes())
// [ED164] Quantas palavras?// Pedro Ribeiro (DCC/FCUP)importjava.util.Scanner;publicclassED164{publicstaticvoidmain(String[] args){
Scanner in =new Scanner(System.in);
BSTree<String> set =new BSTree<>();int n = in.nextInt();for(int i=0; i<n; i++) set.insert(in.next());
System.out.println(set.numberNodes());}}
Exercício 4) Dicionários e for-each
Um TAD dicionário (também conhecido como mapa ou array associativo) é uma estrutura de dados que guarda pares (chave,valor), associando a cada chave um determinado valor. Uma implementação possível é precisamente usar uma árvore binária de pesquisa que usa a chave para decidir a posição na árvore (garantindo que só existe uma cópia de cada chave).
Código de dicionários
Faça download do código de dado nas teóricas e compile-o:
BSTMap - Dicionário de pares (chave,valor) implementado com árvores binárias de pesquisas (ex. métodos: put, get e keys)
Espreite o ficheiro BSTMapNode.java para ver como um nó é descrito, e note na assinatura como o tipo K (a chave) tem de ser comparável, mas o tipo V não (o valor).
Um primeiro teste.
Execute a classe de teste dos dicionários: $ java TestBSTMap
Espreite e acompanhe a implementação do método put da classe BSTMap, muito semelhante ao insert de uma árvore binária de pesquisa normal. Note também a assinatura dos principais métodos e o que fazem (get, put, remove e keys). Veja também como são percorridas as chaves do mapa (que são devolvidas numa lista ligada de Java). De um modo geral, quanto temos algo iterável no Java, podemos usar a sintaxe for-each:
for (TipoElemento variavel : Sequencia) {
InstrucoesCiclo
}
Um exemplo seria algo como:
importjava.util.LinkedList;importjava.util.TreeSet;importjava.util.Set;publicclassTestForEach{publicstaticvoidmain(String[] args){// Criação de Lista Ligada usando a estrutura de dados do próprio Java// Exemplo de inicialização usando sintaxe "diamond" (<>). Se não// colocarmos o tipo no construtor, o Java consegue inferir qual é// olhando para a variável que estamos a inicializar
LinkedList<String> list =new LinkedList<>();// Adicionando algumas strings à lista ligada
list.addLast("testing");
list.addLast("just");
list.addLast("for");
list.addLast("fun");// Para percorrer a lista podemos usar um for-eachfor(String s : list)
System.out.println(s);// Qualquer TAD iterável pode ser usado com um for each// Aqui fica um exemplo com... conjuntos (interface Set)// TreeSet implementa um conjunto usando árvores binárias de pesquisa
Set<Integer> set =new TreeSet<>();
set.add(42);
set.add(24);
set.add(0);// Podemos usar int por causa do autounboxingfor(int i : set)
System.out.println(i);}}
Um pequeno exercício para usar dicionários
Resolva e submeta o problema [ED172] Contagem de palavras, usando como estrutura de dados base um BSTMap.
Este problema é semelhante a problema resolvido nas aulas teóricas (ver slide 79 do capítulo 7)
Crie um dicionario do tipo <String,Integer>
Para ler as palavras use os métodos hasNext() (para saber se ainda existem palavras para ler) e next() (para ler a próxima palavra)
Para cada palavra lida:
Se a palavra ainda não existe no dicionário (usar método get()), então colocá-la no dicionário com valor igual a 1 (usar método put())
Se palavra já existe, incrementar o seu valor (usar método get() para ler valor e depois método put() para actualizar o valor)
No final é só percorrer a lista de chaves (método keys()) usando um for-each e imprimir os valores. Como é uma árvore binária de pesquisa e o keys é feito inorder, as chaves já vêm por ordem alfabética.
// [ED172] Contagem de palavras// Pedro Ribeiro (DCC/FCUP)importjava.util.Scanner;publicclassED172{publicstaticvoidmain(String[] args){
Scanner in =new Scanner(System.in);
BSTMap<String, Integer> map =new BSTMap<>();while(in.hasNext()){
String s = in.next();if(map.get(s)==null) map.put(s,1);else map.put(s, map.get(s)+1);}for(String s : map.keys())
System.out.printf("%s: %d%n", s, map.get(s));}}
Exercícios extra de treino para o 2º teste prático
Para o ajudar a preparar o 2º teste prático (13 de janeiro), estão também disponíveis para submissão os quatro problemas usados no teste prático equivalente de 19/20 (a estrutura e objetivos do teste eram semelhantes, com a diferença que este ano aparece um primeiro problema mais simples - os 3 problemas aqui colocados correspondem a exemplos similares ao 2º, 3º e 4º problemas deste ano):
Para esta semana vou colocar um exercício que envolve árvores mas também eficiência algorítmica. É um problema da minha autoria que que foi usado nas Olimpíadas de Informática:
O limite de tempo de execução para cada caso de teste é de 1 segundo, pelo que a solução só será aceite e com pontuação máxima no Mooshak se for eficiente. Não será por isso possível para cada pergunta simular realmente todas as bolas a cair até chegar n-ésima bola.
Para estes problemas de desafio não vou dar logo dicas, para vos deixar pensar, mas se quiserem mesmo resolver o problema e não estejam a conseguir (mesmo depois de terem realmente tentado), podem falar comigo para obter pistas, ou ter uma ideia de como os "atacar".