RSS Feed
Precedenta
Următoarea

Problema 323

06 Februarie 2011

Operații OR aplicate bit-cu-bit pe numere întregi aleatorii


Fie y0, y1, y2,... un șir de numere întregi aleatorii de 32 de biți fiecare
(adică 0 ≤ yi < 232, fiecare valoare având aceeași șansă să apară).

Pentru șirul xi următoarea relație de recurență este dată:

  • x0 = 0 și
  • xi = xi-1 | yi-1, pentru i > 0. ( | e operatorul OR aplicat bit cu bit)

Se poate vedea că până la urma o să existe un index N astfel încât xi = 232 -1 (un șir de biți format în totalitate din bitul 1) pentru toate valorile i ≥ N.

Găsește valoarea așteptată a lui N.
Introdu ca răspuns rezultatul rotunjit la 10 cifre fracționare.


>> Vezi problema originală <<