→ penguin7272:sigma後面應該接g(...) 12/28 22:16
※ 編輯: utomaya 來自: 219.70.181.249 (12/29 00:27)
ProjectEuler 第316題 [Numbers in decimal expansions]
http://projecteuler.net/index.php?section=problems&id=316
令P=P_1P_2P_3....為一個由數字組成的無限序列, 每一個數字是從 {0,1,2,3,4,5,6,7,8,
9} 集合中以均等的機率選出來的
很顯然的，p等同於以0開頭的實數，0.P_1P_2P_3....
而且我們可以知道，從[0,1)區間任選一個實數，就等同於 從{0,1,2,3,4,5,6,7,8,9}
集合中以均等的機率選擇一個隨機數字所組成的無限序列
對於任何有d位數的正整數n，令k代表n在任意隨機數列中第一次出現的位置
令g(n)為k的期望值，我們可以證實g(n)永遠是有限的，而且有趣的是，永遠是整數
例如，n=535
p = 31415926535897...., k = 9
p = 355287143650049560000490848764084685354..., k = 36
我們可以發現 g(535)=1008
│ 10^6│
999 │ ___ │
你被告知 Σ g(│ n │) = 27280188
n=2 └ ┘
│10^16│
999999 │ ___ │
試求 Σ g(│ n │) = ?
n=2 └ ┘
註:│x│代表對x做無條件捨去的運算
└ ┘
--
鋪了好長的梗，其實就是丟骰子的問題
假設骰子有10面，分別寫上0~9
g(535)就是一直丟，直到出現連在一起的"535"，要丟幾次的期望值，也就是1010次
再減掉2，因為是first index
所以是1008
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.70.181.249