[問題] CodeJam qualification D(Random shuffle

看板Prob_Solve作者 (problem maker)時間13年前 (2012/04/01 01:11), 編輯推噓1(1推 0噓 5→)
留言6則, 3人參與, 最新討論串1/1
假設有兩個數字 初始的時候 並沒有按照順序排列 經由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
→
04/01 02:10, , 1F
1 + 1/2 + 1/4 + ..... = 2
04/01 02:10, 1F
→
04/01 04:07, , 2F
為什麼不是1x(1/2)+2x(1/4)+3x(1/8)+4x(1/16)+5x(1/32)...
04/01 04:07, 2F
推
04/01 07:05, , 3F
那也是 2 啊
04/01 07:05, 3F
→
04/01 07:06, , 4F
S = 上式則 S - S/2 = 1/2 + 1/4 + 1/8 + ... = 1
04/01 07:06, 4F
→
04/01 07:06, , 5F
所以 S = 2
04/01 07:06, 5F
→
04/01 12:56, , 6F
感謝tkcn, LPH66
04/01 12:56, 6F
‣ 更多 shaopin 的文章
文章代碼(AID): #1FTphLZ6 (Prob_Solve)