É 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.
Exercício 1) TAD Conjunto - exemplo de implementação e utilização
Introdução e Conceitos Associados.
Nas teóricas falamos de vários conceitos que devem rever, em particular:
Interface: definição dos métodos de um TAD (em
abstracto, sem indicar implementação)
Implementação de um interface: uma classe X que
implementa um interface Y é declarada
como class X implements Y e tem de
implementar todos os métodos definidos no interface.
TAD Conjunto: um tipo abstracto de dados que
implementa um conjunto (foi usado como exemplo um conjunto de
números inteiros e operações como adicionar, remover ou
verificar se um número está contido no conjunto)
Resolva o problema [ED247] TAD
Conjunto (ArrayListIntSet) e poderá também submeter a sua
solução no Mooshak.
Note que terá de implementar dois métodos novos: equals e intersection.
Deve submeter um ficheiro apenas com a classe que implementa o interface ArrayListIntSet
Para ambos os métodos a implementar, como recebe um IntSet s, apenas pode chamar os métodos do interface a esse objecto s.
Para fazer o equals(IntSet s) pode por exemplo verificar se o tamanho de ambos os objectos (this e s) são iguais e depois percorrer todos os elementos de this e verificar se estão em s (usando o método contains)
Para fazer o intersection(IntSet s) deve começar por criar um novo conjunto tmp (como criar? veja o código exemplo no enunciado... e deve ter espaço para quantos elementos?); depois pode percorrer todos os elementos de this e verificar se estão em s (usando o método contains); caso estejam, adicione-os a tmp.
Exercício 2) Medir o tempo de execução do TAD Conjunto
Descobrindo a quantidade de números únicos.
Use a implementação de conjunto para descobrir a quantidade de números únicos (não repetidos) no input. O algoritmo a usar deverá ser algo como:
Criar um conjunto s vazio
Enquanto houver um número x para ler, adicionar x ao conjunto s
No final, escrever a quantidade de elementos em s
Teste o seu programa com os seguintes ficheiros N.txt, cada um contendo N números entre 1 e N (se precisar, pode parar a execução com ctrl + C):
Meça o tempo de execução para cada um destes casos de teste. Por exemplo, para medir o tempo para o caso de 1000 números execute, e supondo que o seu programa está numa classe Unique, pode fazer o seguinte: $ time java Unique < 1000.txt
Como é que foi crescendo o tempo?
Exercício 3) Um TAD conjunto mais eficiente
O objectivo deste exercício é criar uma nova implementação do TAD conjunto que seja mais eficiente do ponto de vista do tempo de execução para os métodos contains, add e remove. Deverá por isso criar uma nova classe que implemente o interface IntSet (como definido no problema [ED247]):
classBooleanArrayIntSetimplements IntSet {// Deverá colocar aqui os atributos e métodos}
A ideia é usar um array de valores booleanos para dizer se um número está ou não num conjunto:
Manter um array isElem[] de valores booleanos (verdadeiro ou falso)
isElem[i] diz-nos se o número i está ou não no conjunto
O tamanho do array determina o tamanho do número máximo
Manter numa outra variável size o número de elementos
Por exemplo, o conjunto {1,5,7} seria representado por:
isElem[]={F,T,F,F,F,T,F,T,F,F,F} e size=3
0
1
2
3
4
5
6
7
8
9
F
T
F
F
F
T
F
T
F
F
Criando o código.
Crie um ficheiro BooleanArrayIntSet.java implementando a ideia para o TAD conjunto atrás descrita (como poderá ser um construtor da classe?). Teste os seus métodos - usando por exemplo a classe TestSet que já tem definida - tem de mudar a declaração da variável s para passar a usar esta nova implementação.
Verificação da eficiência.
Modifique o código anterior para verificar a quantidade de números únicos para passar a usar a sua nova implementação de IntSet. Teste o funcionamento, medindo o tempo de execução. É melhor ou pior que a anterior implementação? Deverá conseguir agora executar em muito menos tempo o caso de 1 milhão de números.
Vantagens e desvantagens.
Sabendo que esta nova implementação é mais eficiente na inserção de números, que outra vantagens e desvantagens vê em relação à anterior implementação de uma lista de números usando arrays?
Exercício de submissão extra para consolidação de conhecimentos
TAD BigNumber - Números arbitrariamente grandes
Os tipos de dados primitivos do Java têm limites para os números
que conseguem representar. O objectivo deste exercício é a
implementação de um TAD destinado a representar números inteiros
positivos arbitrariamente grandes, ou seja, com suporte para o
número de dígitos que desejarmos (o Java já contém
uma classe
para representar números com precisão arbitrária, mas aqui a
ideia é serem vocês a implementarem uma).
Uma sugestão (simples) é usar um array contendo em cada posição um dígito, o que lhe vai simplificar a vida depois para somar e multiplicar. Deve colocar o digito menos significativo na posição zero e por ai adiante.
Por exemplo, o número "23454760" ficaria guardado num array como o que se segue:
0
6
7
4
5
4
3
2
Se optar pelo array de digitos, pode simplesmente declará-lo com o tamanho máximo permitido (1000 dígitos) e guardar o número de dígitos significativos actualmente armazenados numa outra variável size, por exemplo.
Para converter um caracter no dígito correspondente, basta subtrair-lhe '0' (por exemplo, char c = '2'; int d = c - '0'; colocaria um 2 no inteiro d).
Somar dois números
Ainda se recordam como somar manualmente dois números? Exemplo:
123
+ 789
-----
912
Multiplicar dois números
Ainda se recordam como multiplicar manualmente dois números? Exemplo: