430. Range flips
http://projecteuler.net/problem=430
將編號1到N的圓盤由左而右依序排成一列。
每個圓盤都是一面白色一面黑色，並且一開始都是白色那面朝上。
每一回合，由1到N隨機且等機率取出兩整數A和B（不一定相異）。
然後將由編號A到B的圓盤全部翻面。
下圖為N=8，在第一回合A=5、B=2以及第二回合A=4、B=6的範例。
http://projecteuler.net/project/images/p_430_flips.gif
令E(N,M)為這N個圓盤在經過M回合後，白色那面朝上的數目的期望值。
可以證明E(3,1) = 10/9、E(3,2) = 5/3、E(10,4) ≒ 5.157以及E(100,10) ≒ 51.893。
請求出E(10^10,4000)，並計算答案到小數後2位。
--
http://projecteuler.net/problem=430
將編號1到N的圓盤由左而右依序排成一列。
每個圓盤都是一面白色一面黑色，並且一開始都是白色那面朝上。
每一回合，由1到N隨機且等機率取出兩整數A和B（不一定相異）。
然後將由編號A到B的圓盤全部翻面。
下圖為N=8，在第一回合A=5、B=2以及第二回合A=4、B=6的範例。
http://projecteuler.net/project/images/p_430_flips.gif
令E(N,M)為這N個圓盤在經過M回合後，白色那面朝上的數目的期望值。
可以證明E(3,1) = 10/9、E(3,2) = 5/3、E(10,4) ≒ 5.157以及E(100,10) ≒ 51.893。
請求出E(10^10,4000)，並計算答案到小數後2位。
--
All Comments