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: