「 2021年01月 」一覧

Project Euler 323. Bitwise-OR operations on random integers

Project Euler 323. Bitwise-OR operations on random integers

\(y_0, y_1, y_2, \ldots\) をランダムな符号なし32ビット整数とする(つまり,\(0\leq y_i<2^{32}\), 任意の値が同様に確からしく現れるとする). 列\(x_i\)に対して,次の漸化式が与えられている: \(x_0=0\), \(x_i=x_{i-1}|y_{i-1}\), (i>0). (\( | \)はビットごとのORをとる操作) 最終的に,ある添字\(N\)が存在して全ての\(i\geq N\)に対して\(x_i=2^{32}-1\)(すべての桁が1であるビットパターン)となることが分かる. \(N\)の期待値を求めよ.答えは小数点以下10桁に四捨五入して答えよ.

記事を読む

スポンサーリンク
sub2
sub2