Come affrontare questa domanda sull'algoritmo?

Question

• Un sito Web ha un database di n domande.
• Si fa clic su un pulsante e viene visualizzata una domanda casuale per clic. La probabilità che una particolare domanda venga mostrata all'evento click è 1/n.

In media, quanti clic sarebbero necessari per visualizzare tutte le domande nel database?

Qual è l'approccio richiesto per tali domande?

Answer 1

Vedere coupon collector's problem.

Answer 2

Perché non eseguiamo una simulazione e l'abbiamo scoperto?

<?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 />"; 
} 

uscita:

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 

Answer 3

Questa è una domanda matematico piuttosto che un algoritmico. Come sdcvvc said, questo è il famoso problema del collezionista di coupon.

Supponiamo di avere n domande da "raccogliere". Sia X un random variable che denota il numero richiesto di clic. Se definiamo Xi di essere il numero di clic dal momento in cui abbiamo (i-1) domande al momento abbiamo i domande, allora:

X = X1 + X2 + ... + Xn

a causa della linearity of the expected value:

E (X) = E (X1 + X2 + ... + Xn) = + EX1 EX2 + ... + Exn

Se controlliamo Xi, vediamo che in realtà ha geometric distribution con p = (n-i + 1)/n, quindi un valore medio di n/(n-i + 1). Pertanto:

EX = n * (1/n + 1/(n-1) + ... + 1/2 + 1/1) = n * Hn

Dove Hn rappresenta l'ennesima Harmonic number, che può essere approssimata da ln n:

EX ~ = n * ln n

È possibile eseguire una simulazione semplice e testare questa approssimazione.