En promedio, ¿cuántos clics se necesitarían para ver todas las preguntas en la base de datos?¿Cómo abordar este algoritmo?
¿Cuál es el enfoque requerido para estas preguntas?
¿Por qué no ejecutamos una simulación y descubrimos?
<?php
function simulate($size) {
$range = range(1, $size);
$hits = 0;
$hit = array();
while(count($hit) != $size) {
$rand = array_rand($range);
$hit[$rand] = 1;
$hits++;
}
return $hits;
}
for ($j=10; $j<101; $j+=10) {
$res = array();
for ($i=0; $i<10; $i++) {
$res[] = simulate($j);
}
echo "for size=$j, avg=" . array_sum($res)/10 . "<br />";
}
Salida:
for size=10, avg=35.9
for size=20, avg=68.8
for size=30, avg=123.3
for size=40, avg=176.9
for size=50, avg=205.9
for size=60, avg=276.8
for size=70, avg=304.9
for size=80, avg=401.9
for size=90, avg=371
for size=100, avg=617.7
Ésta es una cuestión matemática en lugar de uno algorítmica. Como sdcvvc said, este es el problema del famoso coleccionista de cupones.
Supongamos que tiene n preguntas para "reunir". Deje X ser un random variable que denota la cantidad requerida de clics. Si definimos Xi sea el número de clics desde el momento en que tenemos preguntas (i-1) hasta el momento en que tenemos i preguntas, entonces:
X = X1 + X2 + ... + Xn
debido a la linearity of the expected value:
E (X) = E (X1 + X2 + ... + Xn) = EX1 + EX2 + ... + EXn
Si inspeccionamos Xi, vemos que, de hecho, tiene geometric distribution con p = (n-i + 1)/n, de ahí un valor medio de n/(n-i + 1). Por lo tanto:
EX = n * (1/n + 1/(n-1) + ... + 1/2 + 1/1) = n * Hn
Dónde Hn es el n-ésimo Harmonic number, que se puede aproximar por ln n:
EX ~ = n * ln n
puede ejecutar una simulación sencilla y poner a prueba esta aproximación.
¿Tenemos una probabilidad 1/n'th de aleatorizar cada pregunta con cada clic? –
@Zenzen: sí, tenemos. – Lazer
Ya encontró el enfoque correcto para una pregunta así: publíquelo en stackoverflow. ;) – x4u