Re: [中譯] ProjectEuler 323 Bitwise-OR operatio …

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者jurian0101 (小維)時間15年前 (2011/02/08 23:39)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

※ 引述《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 意外的長知識了。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.164.5.104 ※ 編輯: jurian0101 來自: 218.164.5.104 (02/08 23:44)