T01 Embaralhamento
Abschlussbedingungen
Geöffnet: Montag, 23. August 2021, 00:00
Fällig: Dienstag, 31. August 2021, 23:59
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\).