IF672
- Algoritmos e Estruturas de Dados
novembro
2002 a março 2003
4 - Freqüência de Colisão
Considere a função
de hash f(n) = (n + k) % v.
Obviamente haverá colisões após no máximo v
elementos inseridos pelo princípio do pigeon hole.
Esse problema pede apenas que se faça uma simulação
para se saber a freqüência das quantidades
de elementos por índice após inseridos s * v elementos aleatoriamente
.
Entrada e Saída de dados
Cada linha terá
(k > 0) e (0 < v < 200) e s (variando de 0.0 a 2.0).
Deve-se utilizar para a simulação a função
java.lang.Math.random().
Essa servirá para gerar floor(s*v) inteiros não-negativos
para a simulação.
A saída consiste de v linhas com a quantidade de elementos com mesmo
índice i do array.
Note que a saída pode ser diferente uma da outra, logo não
se preocupem caso o resultado
tenha dado diferente do abaixo.
Entrada exemplo
0 10 0.8
0 10 0.9
0 10 1.0
Saída correspondente
Conjunto #1:
0 -> 1
1 -> 1
2 -> 0
3 -> 2
4 -> 1
5 -> 1
6 -> 0
7 -> 0
8 -> 1
9 -> 1
Conjunto #2:
0 -> 1
1 -> 0
2 -> 1
3 -> 2
4 -> 1
5 -> 0
6 -> 3
7 -> 0
8 -> 1
9 -> 0
Conjunto #3:
0 -> 0
1 -> 1
2 -> 1
3 -> 1
4 -> 1
5 -> 2
6 -> 2
7 -> 1
8 -> 1
9 -> 0