作者shaopin (problem maker)
看板Prob_Solve
標題[問題] CodeJam qualification D(Random shuffle
時間Sun Apr 1 01:11:47 2012
假設有兩個數字 初始的時候 並沒有按照順序排列
經由random shuffle的方法, 要平均幾次纔會讓這
兩個數字按照順序排列?
問題是來自於google codejam 2011 qualification
probelm D, GoroSort
在網頁
https://code.google.com/codejam/contest/975485/dashboard#s=p3
最下面的"Explanation"中說要random shuffle兩個數字
使之按照順序排列的expected number of shuffle
是2次...我的問題就是不知道為什麼是2次
這個2是怎麼得出來的?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 69.111.166.59
→ tkcn:1 + 1/2 + 1/4 + ..... = 2 04/01 02:10
→ shaopin:為什麼不是1x(1/2)+2x(1/4)+3x(1/8)+4x(1/16)+5x(1/32)... 04/01 04:07
推 LPH66:那也是 2 啊 04/01 07:05
→ LPH66:S = 上式則 S - S/2 = 1/2 + 1/4 + 1/8 + ... = 1 04/01 07:06
→ LPH66:所以 S = 2 04/01 07:06
→ shaopin:感謝tkcn, LPH66 04/01 12:56