作者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
1F：→ tkcn:1 + 1/2 + 1/4 + ..... = 2 04/01 02:10
2F：→ shaopin:为什麽不是1x(1/2)+2x(1/4)+3x(1/8)+4x(1/16)+5x(1/32)... 04/01 04:07
3F：推 LPH66:那也是 2 啊 04/01 07:05
4F：→ LPH66:S = 上式则 S - S/2 = 1/2 + 1/4 + 1/8 + ... = 1 04/01 07:06
5F：→ LPH66:所以 S = 2 04/01 07:06
6F：→ shaopin:感谢tkcn, LPH66 04/01 12:56