#author("2022-06-24T12:10:51+00:00;2022-06-17T19:21:42+00:00","","")
*[[Problem 323:http://projecteuler.net/problem=323]] 「ランダムな整数のビット論理和演算」 [#vd66dc52]

y&sub{0};, y&sub{1};, y&sub{2};,... を, ランダムな 32 ビット符号なし整数からなる数列とする. ~
(つまり 0≦y&sub{i};<2&sup{32}; で全ての値が同様に確からしい. )
&tex{y_{0}};, &tex{y_{1}};, &tex{y_{2}};,... を, ランダムな 32 ビット符号なし整数からなる数列とする. ~
(つまり 0 ≦ &tex{y_{i}}; < &tex{2^{32}}; で全ての値が同様に確からしい. )

数列 x&sub{i}; に対し次の反復が与えられる:
数列 &tex{x_{i}}; に対し次の反復が与えられる:

- x&sub{0}; = 0
- x&sub{i}; = x&sub{i-1}; | y&sub{i-1}; (i>0)(| はビット単位のOR演算)
- &tex{x_{0}}; = 0
- &tex{x_{i}}; = &tex{x_{i-1}}; | &tex{y_{i-1}}; (i > 0)( | はビット単位の OR 演算)

すべての i≧N に対し x&sub{i}; = 2&sup{32};-1(ビットがすべて1となるパターン)となるような添え字 N が最終的に存在することが分かる.
すべての &tex{i}; ≧ N に対し &tex{x_{i}}; = &tex{2^{32}};-1(ビットがすべて1となるパターン)となるような添え字 N が最終的に存在することが分かる.

N の期待値を求めよ. ~
答を小数点以下 10 桁に四捨五入して求めよ.


トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS