UNIP - Ciência da Computação e Sistemas de Informação
Estrutura de Dados
AULA 10
Recursividade e Tabelas Hash
Estrutura de Dados
1
Recursividade
• Ao atingir o topo da escada, a tarefa de a subir está terminada;
– Enquanto o topo não for atingido;
• Avançar um degrau;
• e retomar a tarefa de subir as escadas, mas agora, tendo já
avançado um dos degraus, a dimensão do problema aparece
mais reduzida.
• Uma função que é dita recursiva é aquela que invoca ela mesma.
• Porém é preciso um cuidado especial para não cairmos em um
looping infinito.
• Geralmente, para que uma função não fique invocando ela mesma
indefinidamente, devemos definir, na função, testes condicionais
sobre o parâmetro para saber onde devemos parar de invocar a
função.
• Recursividade brinda soluções simples e elegantes, evitando
estruturas de repetição.
Estrutura de Dados
2
Recursividade
• Fatorial
–
–
–
–
–
–
–
0! = 1 (por convenção)
1! = 1 = 1 * 0!
2! = 2 * 1 = 2 * 1! = 2 * 1 = 2
3! = 3 * 2 * 1 = 3 * 2! = 3 * 2 = 6
4! = 4 * 3 * 2 * 1 = 4 * 3! = 4 * 6 = 24
...
n! = n * (n-1) * (n-2) * ... * 1 = n * (n - 1)!
•
•
Podemos daqui concluir que:
Caso base: 0! = 1 ; caso em que o valor é conhecido por definição
ou convenção
• Caso geral n! = n * (n-1)! ; caso que recorre à própria função que se
pretende resolver
Estrutura de Dados
3
Recursividade
public class Fatorial{
public static void main (String args []){
Scanner ler = new Scanner(System.in);
int n;
System.out.printf("Digite um inteiro positivo: ");
n = ler.nextInt ();
System.out.printf("%d! = %d\n", n, fatorial(n));
System.exit(0);
}//fim main
public static int fatorial(int n){
if(n == 1)
return 1;
else
return (n * fatorial(n-1));
}//fim método fatorial
}//fim classe
Estrutura de Dados
4
Tabelas Hash
• Uma tabela hash é uma estrutura que permite associar
uma chave a um valor e, posteriormente, ter acesso ao
valor a partir de sua chave associada. A chave é
transformada por uma função em uma posição na tabela;
usando sempre essa transformação, a localização de
chaves na tabela é realizada rapidamente.
Fonte: http://www.dca.fee.unicamp.br/cursos/PooJava/collections/h_hasht.html
Estrutura de Dados
5
Tabelas Hash
• Hashing é uma tabela composta por um vetor com M
posições e cada posição representa um endereço onde
os elementos a serem armazenado nele possuem um
valor chave que é utilizado para calcular o endereço na
tabela onde deverão ser alocados.
• Para criação da função hashing é o método da divisão
onde uma chave X é mapeada em M endereços da tabela
hashing calculando o resto da divisão de X por M, ou
seja: h(x) = x mod m.
Fonte: http://www.manfred.com.br/index.php/bsi/estrutura-de-dados-i/146-aula14-tabela-hash-em-java
Estrutura de Dados
6
Tabelas Hash
h(x) = x mod m.
• Exemplo:
• Em uma tabela hashing de tamanho 10 e a chave inserida é
100 será armazenado na posição 0.
• Ao aplicar a função de hashing sobre um conjunto de chaves,
duas ou mais chaves podem ser mapeadas para o mesmo
endereço, esta situação é chamada de colisão, para resolver
este problema é utilizado o encadeamento dos endereços da
tabela hashing ou se usa de outra alternativa, como a do
endereçamento aberto.
Estrutura de Dados
7
Tabelas Hash
• Exemplo de codificação em Java de tabelas Hash
pode ser encontrado em:
Fonte: http://www.manfred.com.br/index.php/bsi/estrutura-de-dados-i/146-aula14-tabela-hash-em-java
Estrutura de Dados
8