Numero stimato di tentativi

Question

Numero stimato di tentativi

#1 da (2 voti)

0

Problema:

Il Comitato Oscar vuole decidere quale persona dovrebbe ottenere il premio come miglior attore tra gli attori N. Per questo ha deciso di utilizzare una funzione casuale random_bit () che restituisce 0 o 1 con eguale probabilità. Perché i risultati siano equi, al comitato è stato chiesto di generare un numero casuale compreso tra 1 e N (inclusi), tale che tutti gli attori hanno la stessa probabilità di essere scelti (che in questo caso dovrebbe essere sempre uguale a 1 / N.

Prima di tutto il Comitato vuole sapere il numero atteso di volte in cui dovranno chiamare la funzione random_bit () per generare un numero casuale compreso tra 1 e N.Also, mentre chiamano la funzione, dovrebbero seguire la strategia ottimale (es. strategia che minimizza il numero previsto di chiamate di funzione)

Questo è un problema dei precedenti concorsi su codechef.com e il link ad esso.

Questo sito consente di vedere la soluzione di altri utenti e finora è stata accettata solo una soluzione. La soluzione è in codice C ++:

#include <iostream>
using namespace std
int main() {
    int T;
    cin >> T;
    for(int ii = 0; ii<T; ++ii) 
    {
         int N;
         cin >> N;
         double p = 1, ans = 0;
         int x = 1 % N;
         for(int i = 0; i<100000; ++i)
         {
              ans += x * p;
              x = (x * 2) % N;
              p /= 2;
         }
         cout << ans;
    }
    return 0;
}

So come funziona il codice e cosa fa, ma non riesco a trovare la logica dietro. Qualsiasi aiuto / indizio?

Sarebbe anche bello se qualcuno potesse pubblicare un altro algoritmo.

c++ algorithms problem-solving

posta Stefan4024 19.04.2014 - 21:07

fonte

1 risposta

Leggi altre domande sui tag c++ algorithms problem-solving

Come misurare la qualità dei miei casi d'uso? Perché la casella nera viene chiamata test funzionale quando esegue il test anche non funzionale?

score 2 · Answer 1

Sembra che il codice interpreti la stringa di bit casuali come una frazione binaria, la converta in una frazione N-ary e guardi la prima cifra di quella frazione N-ary per determinare il vincitore.

La domanda diventa: Quanti bit casuali abbiamo bisogno fino a quando la prima cifra della frazione N-ary è stabile?

Per tutti gli esempi, userò N = 3. La frazione 3-ary inizierà con

a 0 quando la frazione è compresa tra 0 e 0,333333
a 1 quando tra 0,333333 e 0,666667
a 2 quando tra 0.666667 e 1.000000

es. 0.11 ... (binario) = almeno 0.75 ... (decimale) = 0.2 .. (3-ary) poiché si trova tra 0.666667 e 1.

In questo caso, potremmo fermarci dopo 2 bit di input. Tuttavia, in alcuni casi, non possiamo ancora decidere perché il numero è ancora troppo vicino a un confine.

es. 0.01 .... (binario) = tra 0,25 e 0,5, quindi potrebbe essere 0,0 ... (3-ary) o 0,1 ... (3-ary). Quindi dobbiamo guardare più bit:

Se il prossimo bit è 1: 0,011 ... (binario) = tra 0,375 e 0,5, quindi inizierà sempre con 0,1 ... (3-ary).
Se il prossimo bit è zero: 0.010 ... (binario) = tra 0.25 e 0.375, quindi non possiamo decidere se è 0.0 ... (3-ary) o 0.1 ... (3- ary). Quindi chiediamo un altro bit.

Quindi abbiamo sempre bisogno di almeno due bit, a volte un terzo, in anche meno casi un quarto e così via.

A quanto pare, ma non ne sono sicuro, x*p tiene traccia della possibilità di aver bisogno ancora di un altro bit. ans è la somma di tali probabilità. Non riesco a spiegare completamente questa parte dell'algoritmo, forse qualcun altro può?

x*p diventa più piccolo nel tempo. All'inizio è stabile, poiché ogni iterazione viene dimezzata e x viene raddoppiata. Ma a volte x viene ridotto dalla parte % N . Ad un certo punto, il valore corrente di ans sarà nano x*p e la risposta è il più vicino possibile. (Tuttavia, 100000 iterazioni mi sembrano orribili. Vedi sotto)

Spero che questo aiuti a capire cosa sta succedendo.

Alcune osservazioni aggiuntive sul codice:

Una volta che x diventa uguale a zero, rimarrà zero e ans non cambierà più. Il ciclo for potrebbe rompersi a quel punto. Questo accade solo quando N è una potenza di 2, quindi è piuttosto raro (ad esempio per N = 3, x passa da 1, 2 e torna a 4 = 1).
100000 sembra un limite superiore incredibilmente alto. p è un double e inizia a 1.0, quindi può essere dimezzato al massimo 1024 volte prima di diventare denormalizzato. 53 halvations dopo, p sarà così piccolo da essere arrotondato a zero.
Ancora più strong: poiché x e p iniziano entrambi a 1, ans verrà impostato su 1 durante la prima iterazione. Ad un certo punto, x*p diventerà inferiore a 2 ^ -53, e quando aggiunto a ans sarà troppo piccolo per la materia e verrà ignorato a causa dell'arrotondamento. Poiché p sarà dimezzato per ogni iterazione, ciò richiederà tra 53 e, ad esempio, 100 iterazioni massime, a seconda di N.