T01 Embaralhamento
Completion requirements
Opened: Monday, 23 August 2021, 12:00 AM
Due: Tuesday, 31 August 2021, 11:59 PM
Considere o seguinte trecho de código, que permuta os elementos do vetor deck:
for (int i = 0; i < N; i++) {
int r = (int) (Math.random() * N);
String t = deck[r];
deck[r] = deck[i];
deck[i] = t;
}
Suponha que deck[0..N-1] contém \(N\) strings diferentes. Prove que, se \(N>2\), então a permutação que obtemos ao executar o código acima não resulta em uma permutação uniforme de deck (isto é, há permutações mais prováveis que outras). O que acontece no caso \(N=2\)?
Sugestão. Use o postulado de Bertrand: para todo número real \(x>1\), existe um número primo \(p\) com \(x<p\leq2x\).