323. Bitwise-OR operations on random integers
http://projecteuler.net/index.php?section=problems&id=323
令 y0, y1, y2... 是隨機的 32 位元無號整數。
(即 0 ≦ y_i ＜ 2^32, 每個數字機會均等)
由此定義 x_i 這個序列:
* x0 = 0
* x_i = x_(i-1) | y_(i-1) (其中 | 是 bitwise-OR 運算子)
我們知道最終這個數列會到達 2^32 - 1 此數(即所有位元均為 1 的數)，
亦即存在一個整數 N，使得對所有 i≧N 都有 x_i = 2^32 - 1。
求 N 的期望值，四捨五入到小數點後十位。
--
以下是給不懂什麼是 bitwise-OR 的人的說明:
例如 204 | 394 = 462:
...0000000011001100 (204)
| ...0000000110001010 (394)
-------------------------------
...0000000111001110 (462)
每一位二進位都由原來兩數的同一位數決定，只要有一個是 1 答案的那一位就是 1
前面的 ... 是因為都是 0 所以省略了 XD
--
這題意料之外的單純...只有文字嚇人而已
--
"LPH" is for "Let Program Heal us"....
--
All Comments