ProjectEuler 323 Bitwise-OR operatio … - 拼圖

※ 引述《LPH66 (-858993460)》之銘言：
: 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 的期望值，四捨五入到小數點後十位。


原本以為y_n是0 ~ 2^32-1 的一個排列，那就真的難到爆炸，相當於 2^32 顆球的
取後不放回。那個有限和算不算的出來都是問題。

大概下一題會出吧 (我亂說的)。


現在因為y隨機，y的每位數是0或1的機率一半一半，所以可以拆成32個位數分別看。

題目就等同於，32個人搏杯，沒擲到聖杯退出，撐到最後的人得到N個聖杯，求N的
期望值。


算是算出來了，但封閉式找不出來中......


= = = = = = = = = = = = = 閒談543的分隔線 = = = = = = = = = = = = = =

過節 －尤其是元宵節－ 有時新聞會報寺廟的"乞龜"活動，常會出現某個人連擲 30
幾個聖杯的報導。

(乞龜的解釋 http://taiwanpedia.culture.tw/web/content?ID=11669 )

由這題的結果估計，這種事發生的機率是天文數字，幾乎肯定是有作弊例如輕輕丟軟
的地方防止彈跳之類的。

以這題作模型，可以知道連丟30個的機率並不是(0.5^30) ≒ 1/11億，

我估計的結果是大約兩千三百多萬分之一，也就是全台灣的人去丟都不一定能丟到30
個 XD

意外的長知識了。


--